1.2　流水车间调度概述

1.2.1　流水车间调度问题

流水车间调度问题（Flowshop Scheduling Problem）是一类重要的生产调度问题，也是许多实际流水线生产调度的简化模型，具有较强的工程背景，因而成为目前研究最广泛的典型调度问题之一。流水车间调度可以描述为：n个工件{J₁，J₂，…，J_n}以相同次序经过m个阶段{M₁，M₂，…，M_m}的加工，其中，每个阶段只有一台机器，工件在各台机器上的加工时间是确定且非负的，要确定每台机器上工件的加工顺序及完工时间，使得优化目标最小化。在流水车间调度中经常考虑的目标有最小化最大完工时间（Makespan）、总完工时间、最大延误等关于完工时间的正则目标。

大多数的流水车间调度问题都是“NP-难”的，其中，仅考虑以下约束的问题是最基本的一类调度问题，也称为一般流水车间调度问题[2]：①每个工件在同一时刻只能在一台机器上加工；②每台机器在同一时刻只能加工一个工件；③工件的加工过程不允许中断，即工件一旦在机器上开始加工，未满足规定的加工时间，则不允许离开机器；④工件之间是无关的，且工件释放时间为0；⑤工件在机器上的安装时间与序列无关，可以将其并入加工时间；⑥机器持续可用，不考虑检修或故障情况；⑦对工件在阶段间停留的时间和数量不作限制，若工件待加工的机器被其他工件占用，则允许工件排队等待。

对于以Makespan为目标的一般流水车间调度问题Fm‖C_max，早在1954年，Johnson[3]就提出了求解两机情况的最优多项式算法，而对于三台机器及以上的流水车间调度问题直到1976年才被证明是“强NP-难”的[4]。Fm‖C_max问题具有以下性质：

性质1-1　Fm‖C_max问题至少存在一个最优调度，其最前两台机器M₁、M₂上的工件顺序相同，且最后两台机器M_m-1、M_m上的工件顺序也相同[5]。

由性质1-1可得，当机器数小于4时，问题必然存在一个最优解，使得所有机器上的工件加工顺序均相同。在流水车间调度领域，具有这种工件序列特征的调度称为排列排序（Permutation Schedule）。若将问题的解限定在排列排序内，可能的工件排序方案为n!，对于不限于排列排序的流水车间调度问题而言，需要考虑不同机器上的工件序列，解空间为（n!）m，远远大于排列排序问题的解。由于排列排序比流水车间调度问题更易于求解，且由性质1-1可知，排列排序的最优解可以作为原问题的近优解或最优解，尤其是在两台机器的情况下，采用基于排列排序的Johnson规则可以在多项式时间内得到最优解。因此，排列排序在流水车间调度中具有重要意义，一般流水车间调度问题的算法研究大多是以排列排序为基础进行的[6-8]。

1.2.2　流水车间调度策略与算法

对于流水车间调度问题，目前主要的求解方法包括精确算法（Exact Algorithm）和近似算法（Approximation Algorithm）[9]。

精确算法包括枚举法、分支定界法[10]、动态规划法[11]等，其目标是获得问题的最优解，但由于计算量和存储量随问题规模呈指数增长趋势，大规模的问题求解存在困难[12]。

近似算法寻求解的质量和计算时间之间的折中，与精确算法不同，近似算法并不是要得到最优解，而是致力于在短时间内得到可接受的满意解。近似算法可以进一步分为启发式算法和智能搜索算法。

启发式算法也称为构造启发式算法（Constructive Heuristic），Lourenço[13]将其定义如下：

定义1-1（构造启发式算法，Constructive Heuristic）　对于能够生成工件加工序列的算法，若每次执行过程中得到的工件序列都是相同的，则称之为构造启发式算法。

智能搜索算法是基于邻域搜索策略发展起来的调度求解方法，包括禁忌搜索、遗传算法、蚁群算法等，由于算法本身具有一定的启发式特征，且多采用构造启发式生成算法的初始解，也被称为元启发式（Meta Heuristic）算法。

由构造启发式算法和元启发式算法构成的近似算法也称为广义的启发式算法，而一般意义上的启发式算法则是指构造启发式算法。随着调度优化算法的不断完善和发展，在流水车间调度领域已经形成了系统化的用以指导算法开发的调度策略。

Framinan等[14]对流水车间调度算法进行了归类，提出了由三个阶段构成的问题求解框架，试图涵盖包括构造启发式和元启发式在内的所有调度算法。文中指出，对于大部分的流水车间调度问题的近似算法，其求解过程至少由以下一个阶段构成：①工件排序阶段（Index Development）；②调度解构建阶段（Solution Construction）；③调度解改进阶段（Solution Improvement）。其中，构造启发式对应于工件排序阶段或调度解构建阶段；元启发式则包含调度解改进阶段。下面将基于Framinan等在文献中的研究，对调度算法在这三个阶段的开发策略进行说明。

（1）工件排序策略

所谓工件排序，是指根据流水车间调度问题的实例数据，如工件加工时间等，设计工件的初始序号来指导调度解生成，由此获得的工件序列可以作为最终的调度解，也可以作为其他阶段的初始序列。

对于流水车间调度问题，常用的工件排序策略有排序类比（Sorting Analogy）和问题类比（Problem Analogy）等。

排序类比（Sorting Analogy）通过定义工件的指标函数来排列工件，如Palmer[15]提出的Palmer算法针对以Makespan为目标的一般流水车间调度问题，定义了工件J_i的优先因子π_i，如式（1-1）：

工件按照优先因子非增的顺序排序，进而得到工件序列。

基于排序类比的其他调度算法有Gupta[16]提出的Gupta算法、Bonney和Gundry[17]提出的启发式算法等。

问题类比（Problem Analogy）是利用调度问题的实例数据构建关于其他问题的实例，通过求解构建的类比问题，将解转化为关于原问题的工件序列。在采用问题类比方法时，需要考虑以下两个问题：①类比问题的复杂性，即构建的类比问题是否多项式可解，或是否存在有效的求解算法？②类比问题的解与原调度问题解的关联关系，即能否保证由类比问题获得的解是原问题的近优解或最优解？

对于以Makespan为目标的一般流水车间调度，问题类比方式主要有F2‖C_max问题类比和旅行商问题（Travelling Salesman Problem，TSP）类比。

其一，F2‖C_max问题类比。将Fm‖C_max问题类比为其他流水车间调度问题时，经常采用机器聚集（Machine Aggregation）的方法，通过对工件加工时间的处理，将由m台机器构成的流水车间转换为机器数为m′（m′<m）的流水车间，来简化问题的求解难度。通常选用的类比问题为F2‖C_max，这是因为F2‖C_max问题存在多项式最优算法，能够采用Johnson规则在O（nlogn）时间内获得最优解；而当m≥3时，流水车间调度问题具有“强NP-难”的复杂性，换言之，机器数大于2的流水车间调度问题具有同等的求解难度，彼此间的问题转换并不能简化问题的求解过程。

采用F2‖C_max问题类比的一个经典算法是Campbell等[18]提出的CDS算法，算法通过式（1-2），定义了工件J_i（∀i∈{1，2，…，n}）在类比问题F2‖C_max中的加工时间P_i1，P_i2，并采用Johnson规则获得工件加工序列，如式（1-2）：

其中，k的取值为{1，2，…，m-1}，因此能够得到m-1个调度解，从中选择最优者作为算法最终解。

Johnson规则也称为SPT-LPT规则，具体步骤如下[5]：

步骤一　把工件按加工时间分成两个子集φ₁={J_i｜p_i1<p_i2}和φ₂={J_i｜p_i1>p_i2}；对于满足p_i1=p_i2的工件可以分在两个子集中的任一个。

步骤二　先将集合φ₁中的工件按p_i1非减排序［最短加工时间优先规则（Shortest Processing Time first，SPT）］，再将集合φ₂中的工件按p_i2不增排序［最长加工时间优先规则（Longest Processing Time first，LPT）］，得到工件加工序列。

Dannenbring[19]、Röck和Schmidt[20]、Selim和Al-Turki[21]、Lai[22]等也提出了基于F2‖C_max问题类比的若干算法，这些算法的求解思路相仿，只是定义F2‖C_max问题的工件加工时间的方法不同。

其二，TSP问题类比。TSP问题是一类典型的组合优化问题，目前已有很多研究成果，其中，不乏经典有效的求解算法。将Fm‖C_max问题类比为TSP问题的求解策略首先由Gupta[23]提出，算法中定义了由n个节点{J₁，J₂，…，J_n}组成的TSP问题，节点J_i、J_k间的距离d_ik计算如式（1-3）、式（1-4）：

其中，

进而，Stinson和Smith[24]、Widmer和Hertz[25]、Moccellin[26]等根据流水车间调度问题的完工时间特征，提出了不同的距离计算公式，通过对生成的TSP问题求解，获得相应的工件可行序列。Widmer和Hertz[25]、Moccellin[26]将其作为初始序列，进一步采用禁忌搜索方法改进调度解。

（2）调度解构建策略

调度解构建策略是将未调度的一个或多个工件插入由已调度工件构成的部分调度解（Partial Schedule）的一个或多个位置，进而得到重新排列后的工件序列。采用此策略求解的一个经典算法是由Nawaz等[27]提出的NEH算法，算法采用最大总加工时间优先规则生成初始序列，通过依次选取初始序列中的工件，尝试插入部分调度解的所有可能位置，择其优者作为选定工件的插入位置，进而得到最终的工件加工序列。已有研究表明，NEH算法是目前对以最小化Makespan为目标的一般流水车间调度问题求解效果最好的构造启发式算法[28]。针对NEH算法在其他调度问题中的扩展应用，很多研究者根据具体问题的性质对其进行了改进，得到了一系列NEH扩展算法[29-31]。

由调度解构建方法可以看出，该过程由两个子问题构成：工件选择（Job Selection）问题和工件插入（Job Insertion）问题。

第一是工件选择问题，即如何选择待插入的工件，通常有两种选择策略。

策略一：根据工件的某种指标值来确定待插入的工件，例如，NEH算法根据工件在初始序列中的顺序依次选取待插入的工件。

策略二：选取若干未调度的工件尝试插入部分调度解，择其优者取之。对于以Makespan为目标的调度问题而言，经常选用的衡量指标有Makespan和机器空闲时间（Machine Idle Time），例如，Woo和Yim[32]提出的算法在选择工件时以Makespan为评价指标，McCormick等[33]选用的是机器空闲时间，Gupta和Maykut[34]、Sarin和Lefoka[35]则只考虑了最末机器的空闲时间。

第二是工件插入问题，即对于选定的插入工件，如何确定工件在部分调度解中的插入位置。与工件选择类似，存在以下两种插入策略。

策略一：将选定的工件插入部分调度解的指定位置，通常是将选定工件作为部分调度解最末工件的紧后工件插入，如Gupta和Maykut[34]、Mc-Cormick等[33]。

策略二：将选定的工件尝试插入部分调度解的若干位置，择其优者作为最终插入位置，例如，NEH算法将工件插入部分调度解的所有可能位置，Rajendran[36]提出的算法则是尝试将工件插入部分调度解的后半段可能插入的位置，通常选用的衡量指标为问题所考虑的目标函数。

需要指出的是，基于工件选择和工件插入的调度解构建策略，每次选择和插入过程只考虑了部分调度解的相关信息，因此，无法保证得到的最终解优于初始序列对应的调度解，即使对于最极端的情况，即选择所有未调度的工件尝试插入部分调度解中所有可能插入的位置，获得的最好解也不一定优于初始调度解。

（3）调度解改进策略

调度解改进策略是对已有的调度解进行优化改进的过程，此过程具有两个主要特征：①调度解改进过程是建立在初始解的基础之上，即该过程不能独立存在，必须有生成初始解的阶段；②改进后的调度解不劣于初始解。

一般情况下，主要应用元启发式算法实现调度解改进策略。元启发式算法也称为智能搜索算法，是基于邻域搜索策略发展起来的智能优化方法，主要有禁忌搜索、模拟退火、遗传算法、粒子群优化算法、蚁群算法等，在解决大规模的组合优化问题时具有较好的求解性能，近年来在流水车间调度领域得到广泛应用。

禁忌搜索（Tabu Search，TS）由Golver和Hansen[37-39]提出，是邻域搜索算法的一种扩展，通过设计记忆近期操作的禁忌表来判定是否禁止当前操作。应用禁忌搜索算法解决调度问题的研究集中在初始解的选择、邻域的构造、禁忌表的选取，以及使用并行搜索结构提高算法的有效性等方面。在流水车间调度领域，Eksioglu等[40]以Makespan为目标，提出了一种禁忌搜索算法，算法定义了三种不同的邻域结构，通过对这三种邻域结构的组合，求得问题的有效解。

模拟退火（Simulated Annealing，SA）的思想由Metropolis等[41]于1953年首次提出，可以解释为通过慢慢冷却解，使得问题取得尽可能低的目标值。1983年，Kirpartrick等[42]将模拟退火思想成功应用于组合优化问题，其实质是一种综合梯度下降和启发式随机搜索算法。针对流水车间调度问题，Mokotoff[43]以Makespan和总完工时间为优化目标，设计了多目标模拟退火算法，并通过数据实验验证了算法的有效性。

遗传算法（Genetic Algorithm，GA）由Holand[44]提出，其本质是一个反复迭代的过程，通过一个可以接受的解组向更好的解组的移动来进行搜索。解组也称作种群，在每一次迭代中，都通过复制、交叉和变异操作产生新一代候选解，反复该过程直到满足某种收敛条件为止。Nagano等[45]针对以Makespan为目标的流水车间排列排序问题，提出了一种构造遗传算法（Constructive Genetic Algorithm，CGA），利用NEH算法和局域搜索定义适应值函数，并采用实验设计方法确定算法参数。

粒子群优化算法（Particle Swarm Optimization，PSO）是由Kennedy和Eberhart[46]提出的一种并行随机搜索算法。该算法是基于种群的进化方法，种群中的个体称为粒子，算法搜索寻优的过程其实就是粒子位置的更新过程。在流水车间调度领域，Kuo等[47]以最小化Makespan为目标，设计了一种混合粒子群算法，该算法以粒子群算法为主体，采用随机编码模式来加强算法的全局搜索能力，采用个体增强模式来加强粒子的局域搜索能力。

蚁群算法（Ant Colony Optimization，ACO）是Dorigo于1992年在博士论文[48]中提出的一种随机搜索算法，是对自然界中蚂蚁觅食时通过信息素进行信息传递和反馈获得最佳路径的模仿[49，50]。Yagmahan和Yenisey[51]考虑了以Makespan和总完工时间为目标的双目标流水车间调度问题，提出了一种多目标蚁群算法，将蚁群算法和局域搜索策略相结合，求得问题的解。

上述方法均存在优势与不足，随着调度问题研究的深入，国内外许多学者开始采用混合方法来解决流水车间调度问题。混合方法通常集中了几种算法的优点，具有比单一算法更强的搜索性能，可以有效解决较为复杂的调度问题。Zobolas等[52]针对以Makespan为目标的流水车间排列排序问题，提出了一种结合遗传算法和变邻域搜索（Variable Neighborhood Search，VNS）的混合元启发式算法，该算法基于贪婪随机构造启发式方法生成初始解，采用遗传算法改进调度解，并利用变邻域搜索改进种群。

（4）调度策略总结

综上所述，流水车间调度问题的求解策略可以采用三阶段求解框架来表示，其中，各阶段策略及要点内容如图1-1所示。

上述流水车间调度求解策略具有以下特点：

第一，各阶段的求解过程是相对独立的，不依赖其他阶段所采用的方法。例如，对于调度解的改进阶段而言，只要求有初始解的输入，而至于初始解是由工件排序阶段还是调度解构建阶段获取，以及具体采用什么方法生成，则与改进过程无关。

第二，在算法设计时，一般包含至少一个阶段，每个阶段得到的调度解都可以作为最终解输入，且阶段间允许跳跃。例如，工件排序阶段生成的调度解可以不经过构建阶段，而直接作为改进阶段的初始解进行优化。

基于流水车间调度问题的求解策略，我们可以对已有的调度算法进行细致归类，对于灵活组合和扩展已有算法，以及针对不同调度问题的自身特征设计新算法都具有重要的指导意义。