现状分析：生产计划与调度研究

生产管理主要包括生产计划(production planning)和车间调度(shop-floor scheduling)， 二者之间密切相关， 计划的改变对车间的生产运行产生重要影响， 而车间的实际运行情况也会导致调度乃至计划的重新调整。 车间调度又分为静态调度和动态调度， 生产计划和静态调度是制造系统开始生产前完成的， 而动态调度及各类设备的实时控制是伴随着生产过程的进行而实时完成的。 生产计划的制订面向来自用户或预测的需求值， 主要解决的问题有： 根据客户需求或需求预测来确定计划周期内产品的类型和数量、 各产品的加工路径、 产品生产的优先权等； 调度面向车间生产， 是在满足约束的条件下对生产计划的细化分解， 同时尽可能地优化各种调度性能指标。

半导体生产制造问题是一系列复杂的系统性问题， 半导体制造过程涉及大量资源与行为的协调配合， 近些年来半导体制造系统生产管理得到许多研究人员的关注。 从研究内容上， 主要集中在生产计划、 动态调度方面， 如表1-1 所示； 从研究方法上， 基于运筹学的方法、 基于启发式规则、 基于人工智能的方法、 基于计算智能的方法以及基于群体智能的方法得到了广泛的研究， 具体研究如表1-2 所示：

表1-1　半导体研究内容

续表

表1-2　半导体研究方法分类

车间作业计划又常称为车间作业调度， 是一类特殊的调度问题。 调度问题的研究可以追溯到1954 年， Johnson 提出了两台机器的流水车间调度问题并进行了研究。 此后的近50 年， 调度问题得到了理论界和工程界研究人员的广泛关注和研究， 尤其是在运筹学、 工业工程和计算机科学等领域。 调度问题通常涉及四个基本要素： 任务、 资源、 时间和性能指标针对这四个要素， 调度的目的可简明地描述为： 将任务在资源和时间上进行合理的分派。 其中，“合理”程度的评价是以一个或一组性能指标为依据的。 调度问题所涉及的实际问题范围非常广泛， 如运输调度、 电力调度、 水资源调度、 操作系统运行调度、 人员调度、 项目调度、 制造系统生产调度等。 由于制造业在经济发展中占据举足轻重的地位， 使得制造系统的生产调度问题一直是最为引人关注的研究热点之一。 制造系统生产调度问题的核心即是车间作业调度， 或车间作业计划(Shop Scheduling)。 在经典的车间作业计划问题中， 任务通常是指工序级别的， 即零件的加工工序； 资源通常指加工设备或机器。 根据这两个要素， 通常可以对于车间作业计划类型进行如图1-1 中的划分。

图1-1　车间任务划分

单机调度问题是一类相对简单的车间作业计划问题。 该类问题中， 所有的操作都在单台机器上完成， 调度的主要任务是在机器上对所有操作进行排序。 相对地， 在多机调度问题中， 操作任务需要在多台机器上完成。 多平行机问题是多机调度问题中相对简单的一类。 在该类问题中， 每个任务(Job) 都只包括一个操作(Operation)， 操作可以在多台机器中选择任何一台进行加工， 不同机器加工同一任务的速度(或时耗)可以相同(同型平行机问题)或者不同(同类平行机问题和异类平行机问题)。 平行机问题的调度任务包括为操作合理指派加工机器和在机器上对操作进行排序两个方面。 在流水车间作业计划问题中， 包括多台机器， 每个任务包括多个操作， 所有任务所包括的操作的顺序是相同的(即相当于具有相同的工艺路线)。 若每台机器对任务的加工顺序都相同， 则退化为置换调度问题。 单件车间作业计划问题是最一般的调度问题：包括多台机器， 每个任务包括多个操作， 操作的顺序不尽相同。 显然， 单机调度问题、 平行机调度问题和流水车间作业计划问题均是单件车间作业计划问题的特例。

封装测试企业为典型的离散型制造生产企业， 其中相应的车间作业调度可以归于单件车间作业计划， 但更复杂， 人为影响因素以及存在站点组批(多卡)加工的工序站点。 因此， 以下对单件车间作业计划问题的研究与发展状况进行综述。 单件车间作业计划(Job-Shop Scheduling， JSS)问题由Muth 和Thompson 在1963 年第一次提出。 此后， JSS 问题就成了调度问题中与工业相关的一个标准类型的调度问题， 它具有非常重要的理论和实际研究价值， 引起了理论和工程界广泛的关注和研究。

JSS 问题的研究涉及多个学科和领域， 如运筹学、 优化理论、图论、 人工智能、 系统科学、 离散数学、 管理科学、 计算机科学、工程领域知识等， 被认为是最为困难的调度问题之一。 1976 年，Rinnooy Kan 和Garey M.R. 等均证明了JSS 问题为典型的NP-困难问题。 1995 年， Werner 等指出： JSS 问题不仅为NP-困难问题， 而且是“最坏的”NP-困难问题之一。

50 多年来， 国内外对于JSS 问题的诸多研究可以归结为两个方面： JSS 问题的建模和JSS 问题算法设计与分析。 JSS 问题建模的主要目的是根据理论研究的需要或根据实际生产系统的特点提出一个或一类JSS 问题的子问题， 并以一定的形式对其进行描述， 主要包括： 问题的语义描述、 问题中各要素的描述、 问题的符号表示、 问题的公式化描述、 问题的图论描述等， 它是JSS 问题算法设计与分析的基础。 JSS 问题算法设计的目的是对建立的模型进行求解， 获得优化的调度解。 而算法分析的目的则是对算法正确性进行验证、 对调度结果进行评估与预测、 对算法的时间复杂度及空间复杂度进行分析等。

经典的(或基本的)JSS 问题模型一般定义如下： 有n 个工件，每个工件包含一定数量的工序， 同工件的各工序之间存在一定的工艺约束(即工艺路线或加工路径)， 不同工件所包含的工序数量及工艺路线不尽相同； 这些工序需要在m 台机器上进行加工， 各道工序有一定的加工时间。 要求将所有这些工序以一定的时间分派到相应的机器上， 并在工艺约束的前提下， 使某一个或一组性能指标达到优化。 除工艺约束之外， 经典的JSS 问题还包括以下假设：(1)所有工件在零时刻同时到达； (2)每一工件在同一时间只能在一台机器上加工； (3)工序加工不可抢占(non-preemptable)， 即若一道工序在一台机器上加工， 必须加工完毕， 才能加入另一道工序； (4)一台机器在同一时间只能加工一个工件； (5)工序的加工时间是一个事先确定的点值， 且蕴含装设时间和转移工序时间；(6)每一工件的加工路线是固定的。 每一道工序只能被唯一指定的机器加工； (7)工件的加工允许等待； (8)整个加工过程中， 机器连续可用， 无故障； (9)工序间的缓冲器容量充分大。 近几十年来， 在经典JSS 问题模型的基础上， 在理论研究意义和实际应用需求的驱动下， 国内外研究者提出了许多JSS 的特殊问题和扩展问题模型， 通过对这些模型进行分析和总结， 可以将其归类如下：

1. 从任务属性的角度分类

车间作业计划中的任务主要涉及“工件”和“工序”两个级别。与作业计划相关的工件的属性主要包括工件的投放期、 交货期、 工艺路线和优先级(或权值)， 相关的工序的属性主要是工序的加工工时。

(1)工件投放时间不为零时刻的JSS 问题。 工件的第一道工序可以开始的时间通常称为工件的投放时间(也称为工件的准备时间)。 经典JSS 问题中所有工件的投放时间均为零时刻。 然而， 实际生产中， 情况往往并非如此。 为此， 有些学者研究了工件投放时间为非零时刻的JSS 问题， 主要集中于两方面： 一是在指定的非零投放时间约束下， 以最大完工时间等为目标的车间作业计划的优化问题； 二是在交货期约束下， 以投放时间为优化目标的车间作业计划优化问题。

(2)工件具有指定交货期的JSS 问题。 经典JSS 问题中没有考虑工件的交货期， 然而， 在大多数制造企业， 特别是在订货型生产企业， 工件是具有交货期的， 而对交货期的考虑从不同的角度又可以进一步分为： 交货日期(due-date) 问题和交货期窗口(duewindow)问题， 确定交货期(specified due-date/specified due-window)问题和模糊交货(fuzzy due-date/fuzzy due-window)问题， 单独交货期(distinct due-date/distinct due-window)问题和公共交货期(common due-date/common due-window)问题。 可以看出， 在以上三组分类中， 前者均可看作是后者的应用特例， 如交货日期问题可以看作是窗口“宽度”为零的交货期窗口问题。

(3)工件具有不同优先级的JSS 问题。 经典JSS 问题中所有工件都是具有等同优先级的。 而实际生产系统中， 工件常常具有不同的优先级。 这种优先级主要体现在两个方面： 一是与工件需求的紧急程度相关的优先级， 如为急件、 重要零件等设置较高优先级； 另一个是与工件之间的工艺约束(如装配顺序)相关的优先级。 前者表现出优先级的“并行性”， 即存在优先级相同的工件； 后者则表现出优先级的“串行性”， 即一个从大到小的优先序列。 显然， 工件的优先级对调度过程和结果存在重要影响。 文献研究了前一类优先级别的相关问题， 对后者进行了研究。

(4)工序加工时间非确定点值的JSS 问题。 经典JSS 问题中工序的加工时间是一个事先确定的点值， 且蕴含工序的装设时间和转移程序的时间。 实际生产系统中加工工时常常是模糊的、 机器相关的或服从一定的分布。 文献研究了模糊加工时间的JSS 问题； 研究了机器相关(或机器依赖)的加工时间的JSS 问题； 研究了加工时间服从指数分布的问题； 研究了考虑与加工顺序相关的装设时间的JSS 问题； 文献中将工件按其特性进行成批分类， 同批零件之间不考虑装设所花费的时间。

(5)柔性工艺方案的JSS 问题。 经典JSS 问题中工件的加工工艺方案是唯一的、 线性的。 事实上， 一个工件的加工往往有多种可行的方案(即所谓柔性工艺方案)。 充分考虑工件的柔性对于更合理地利用资源、 避免资源瓶颈、 应对机器故障等意外事件、 缩短交货期等具有重要的实际意义。 对于这一类问题的研究通常可分为三个方面： 工序加工机器的柔性、 工艺路线的柔性和整体的柔性(即同时考虑机器的柔性和路线的柔性)。 在考虑机器柔性时， 通常同时考虑工序的加工工时和加工费用随机器的不同而不同。 由于工艺规划与车间作业计划密切联系， 在对这类问题进行研究时， 常将工艺规划集中起来统一考虑。

2. 从机器属性的角度分类

就已有的相关研究资料看， 对与车间作业计划相关的机器属性的考虑主要包括三方面： 机器的数量、 机器的准备时间和机器的可用性(或故障性)。

(1)固定机器数量的JSS 问题。 经典JSS 问题模型中对机器数量的描述是“m 台机器”。 显然， 固定机器数量的JSS 问题属于经典JSS 问题中的一类特例问题。 如单机调度问题、 双机调度问题等。其中对单机调度问题的研究最为广泛。 分析其原因主要有以下几方面： ①单机调度问题的相对简单性。 问题中只有一台机器， 因而所有工件也均只有单工序， 尽管许多单机调度问题也是NP-hard 问题， 但相对来说， 这类问题的研究和求解比一般的JSS 问题要简单； ②问题本身的理论和实际意义。 单机调度问题可以在实际问题域中找到不少相应的实例； ③单机调度问题的研究结果和研究方法对于一般调度问题的研究具有重要的参考和借鉴价值； 有些复杂的调度问题还可以分解转化为相应的单机调度子问题。

(2)机器准备时间为非零的JSS 问题。 经典JSS 问题中， 所有机器都是零时刻即可用的， 即机器的准备时间为零。 这种情况只是对一个理想的生产初始状态来说是吻合的。 实际情况中， 由于一些原因， 比如机器开工前的预防性维护， 上一阶段作业计划分派在机器上尚未完工的工件的加工等， 使得机器往往存在一个准备时间。

(3)考虑机器停机和故障的JSS 问题。 经典JSS 问题中， 所有机器不仅都是零时刻即可用的， 而且不考虑机器的故障， 即机器任意时刻都是可用的。 这显然只是一种理想状态， 实际生产中机器可能由于停电或操作工的原因等产生停机， 机器的故障也是不可避免的。

经典JSS 问题中， 一台机器一次只能加工一个工件， 实际生产中， 却往往存在一台机器加工几个相同或相似的工件情况。

3. 从机器性能指标的角度分类

综合所研究的各类JSS 问题， 性能指标可分为四大类： 基于作业交货期的性能指标、 基于作业完成时间的性能指标、 基于库存的性能指标及混合性能指标。

(1)基于作业交货期的性能指标。 这一类性能指标主要有： 最小化工件最大延期、 最小化工件平均延期、 最小化工件总延期、 最小化工件延期均方差、 最小化工件总拖期、 最小化加权工件总拖期， 等等。

(2)基于作业完成时间的性能指标。 这一类性能指标主要有：最小化最大机器完工时间(或最大工件流经时间)、 最小化平均机器完工时间(或平均工件流经时间)、 最小化机器完工时间(或工件流经时间)均方差等。

(3)基于库存的性能指标。 基于库存的性能指标主要有： 平均待加工工件数量、 平均未完成工件数量、 平均已完成工件数量、 平均机器空闲时间、 最大机器空闲时间等。

(4)综合性能指标。 混合性能指标往往是上述几个基本性能指标的综合。 如makespan 与总拖期的综合， 流经时间与总拖期的综合、 E/T 指标等。

4. 从JSS 问题属于组合优化问题分类

自从JSS 问题提出以来， 研究者们提出了各种求解算法。 总体来说， 这些算法可分为两大类： 精确算法和近似算法。 其中， 精确算法包括解析法、 枚举法； 近似算法包括构造性方法、 邻域搜索方法和人工智能方法。 更具体的分类如下：

(1)解析法。 指针对简单小规模调度问题的解析求解算法， 如Moore 算法、 Johnson 算法。 这类算法只适用于一些特殊类型的单机调度问题和双机Flow-Shop 调度问题， 如n/1/F 最优调度问题、maxn/1/L 最优调度问题、 maxn/2/F/F 调度问题等。

(2)枚举法(enumerative methods)。 该类算法同样只对很小规模问题比较有效， 对大规模问题计算量和存储量难以承受。 如回溯法(backtracking)、 分支定界法(bound and branch)、 整数规划法、混合整数规划法、 分解方法、 代理对偶方法、 Lagrangian 松弛方法等。

(3)构造性方法(constructive method)。 该类方法能够快速建立问题的解， 但通常情况下解的质量相对较差， 但对于实际生产系统中复杂的、 大规模的JSS 问题来说具有很大的优越性。 如优先调度规则(priority dispatch rule) 算法、 基于瓶颈的启发式方法(bottleneck based heuristics)、 插入方法(insertion algorithm)等。

(4)邻域搜索方法(local search method)。 该类算法从一个(或一组)初始解出发， 通过邻域函数生成解的邻域， 再在邻域中搜索出更优的解来替换当前解， 通过不断的迭代过程实现解的优化。 其调度解的质量通常要优于构造性方法， 但算法的耗时却要多得多。属于该类的算法主要有： 迭代改进法(iterative improvement)、 模拟退火法( simulated annealing， SA)、 进化计算( evolutionary computation， EC)、 禁忌搜索法(tabu search， TS)、 变邻域搜索(variable neighborhood search， VNS)等。

(5)人工智能方法(artificial intelligence)。 该类方法利用人工智能的原理和技术进行搜索， 将优化过程转化为智能系统动态的演化过程， 基于系统动态的演化来实现优化。 如神经网络(neural network， NN)、 蚁群系统(ant system， AS)等。

在上述各种算法中， 研究较多的主要有： 优先调度规则算法、遗传算法、 模拟退火法、 禁忌搜索法、 神经网络法及各种混合算法。 其中， 考虑到实际生产系统中车间作业计划问题的复杂性和规模， 目前最为实用且有效的算法仍然是优先调度规则算法。 这类算法虽然在调度解的优化性能方面欠佳， 但求解速度快， 容易得到满意的甚至最优调度解， 这对实际生产系统的车间管理来说已基本能够满足要求。 尤其是对于生产车间制造企业来说， 其生产系统动态多变， 车间调度的关键是调度的快速和响应的敏捷性， 因此， 优先调度规则算法仍是目前的首选算法。 此外， 由于具有并行性和鲁棒性的优点， 遗传算法在车间作业计划研究中也受到非常广泛的青睐， 相比于优先调度规则算法， 它可以得到更为优化的调度解， 且对于中小规模的实际问题来说， 其调度时间也基本是可以接受的。