1.4　等待时间受限的紧凑调度研究进展

在具有高温连续生产或中间产品性质不稳定的流程工业，由于生产的高度紧凑性，要求尽可能地减少工件在阶段间的停留时间。对于这类生产连续性方面的特殊要求，在调度领域，最初是通过设定无等待（No-wait）约束来加以考虑的。无等待的约束虽然能够保证工件的连续加工，但由于工件的等待时间被严格限定为0，延长了生产时间，增加了生产成本并降低了设备利用率。针对这种情况，1995年，Yang和Chern[65]首先提出了更为贴近生产实际的具有等待时间上限的调度问题。

1.4.1　无等待车间调度问题

所谓无等待是指被加工的工件不允许在两台相邻的机器间等待，即等待时间严格为0。这是具有等待时间上限的流水车间调度问题的一种极端情况，也是大多数研究所聚焦的问题。

（1）无等待调度问题的性质特征

无等待调度问题是调度领域的一类经典问题，相关研究最早可追溯到20世纪60年代。在流水车间的环境下，该调度问题具有一种典型特征，即调度可行解必然是排列排序，换言之，在无等待的条件下，流水车间调度与排列排序问题是等价的[80]。

对于最小化Makespan的无等待流水车间调度问题，Piehler[81]于1960年指出，此问题等价于一类特殊的TSP问题[82，83]；对于两机情况，采用Gilmore和Gomory[84]针对特殊TSP问题提出的多项式最优算法可以获得最优解[82]；但不少于三台机器时，Röck[85]证明了问题是“强NP-难”的。

对于工件具有单位加工时间的情况，Srisk和Ladet[86]指出，目标为Makespan的各类车间调度问题均是多项式时间可解的。Dileepan[87]针对最小化最大延误的两机无等待流水车间调度问题，给出了能够采用EDD规则获得问题最优解的两种特殊情况。

对于无等待调度的问题特征，Spieksma和Woeginger[88]讨论了无等待调度问题中的一种矛盾现象，即提高机器的处理速度、减少工件的加工时间反而可能会增加调度解的Makespan值，并对速度与Makespan的变化比率进行了分析；Kalczynski等[89]给出了以Makespan为目标的无等待流水车间调度和无空闲流水车间调度的网络计划图，在此基础上证明了这两类问题互为对偶问题。

（2）无等待调度问题的求解算法

无等待调度问题的方法研究集中于流水车间调度环境，多采用启发式算法或智能搜索算法等近似算法求解。

在启发式算法方面，对于以Makespan为目标的无等待流水车间调度问题，Reddi和Ramamoorthy[82]、Wismer[90]率先对这类问题展开研究，探讨了问题特征，在此基础上，Bonney和Gundry[17]、King和Spachis[91]分别提出了启发式求解算法；在20世纪90年代，Gangadharan和Rajendran[92]、Rajendran[93]设计了两种新的启发式算法，根据加工时间对工件分类进而获得初始调度，并采用不同的调度解构建方法改进初始解，实验结果表明，这两种新算法明显优于前两种算法。Framinan等[94]提出了一种基于TSP问题类比的启发式算法，并将其与已有的启发式算法及不同的调度解构建方法进行比较，实验结果表明，此算法优于已有的启发式算法，且对于调度解的构建策略而言，NEH算法所采用的工件插入方法与Rajendran[93]提出的优化方法相比，具有更明显的优势。针对优化目标为总加权拖期的无等待流水车间调度问题，吴会江等[95]对各种调度规则的适用情况进行了研究，证明了SPT求解性能最好，SWPT求解性能最差。

在智能搜索算法研究领域，潘全科等对以Makespan为目标的无等待流水车间调度问题分别采用离散粒子群优化算法[96]、变邻域搜索算法[97]、差异进化和变邻域搜索算法，以及二者的多种结合等算法[98]实现问题求解。Wang Jing等[99]从问题特征出发，提出了一种基于变邻域搜索的组合变邻域算法。Allahverdi和Aldowaisan[100]对同时考虑Makespan和最大延误的多目标无等待流水车间调度问题，提出了混合模拟退火算法和混合遗传算法，并给出了基于工件优先关系（Dominance Relation）的DR算法和分支定界算法。Pan等[101]分别针对Makespan和总完工时间两个优化目标，设计了离散粒子群优化算法，提出了一种新的离散工件的粒子群表示方法和位置更新公式，同时在算法中嵌入变邻域搜索改进解的质量。Wang等[102]对于以最大延误为优化目标的无等待流水车间调度问题，提出了快速禁忌搜索算法，利用问题特征，降低了禁忌搜索算法中插入新工件、确定插入邻域和交换邻域这三类主要过程的复杂度，提高了算法的计算效率。宋存利等[103]提出了利用相邻工件间完工时间距离求最小化完工时间的方法，通过研究工件插入和工件对的交换对最小化完工时间的影响，设计了一种邻域迭代搜索算法。

1.4.2　具有等待时间上限的调度问题

Yang和Chern于1995年[65]提出了具有等待时间上限的流水车间调度问题，拉开了针对等待时间上限这一特殊约束的调度研究的序幕，而关于这一问题的研究则集中于近15年。由于问题较新，目前对于具有等待上限的调度问题的研究成果不多，从目前掌握的参考文献来看，有些研究者已经开始关注这类问题。

（1）问题的性质特征

Yang和Chern[65]通过将子集和问题（Sum of Subsets，SOS）归结为具有等待时间上限的两机流水车间调度问题，证明了问题的“NP-难”特性，并对于以下两种特殊情况给出了最优解和最优值：

第一，当且时，（J_i∗，S）为问题的最优调度，对应的最优值为，其中，S是不包含J_i∗的任意工件序列。

第二，当且时，（S，J_i∗）为问题的最优调度，对应的最优值为。

李铁克等[104]证明了当等待时间上限不超过最小加工时间的倍数（ ）时，具有等待时间上限的流水车间调度问题的可行解一定是排列排序；并指出排列排序下，最小化Makespan等价于式（1-5）：

其中，∏为所有排列排序解的集合，r_{π（i），π（i+1）}为第i+1个加工工件相对于其紧前工件的偏移量，有：r_{π（i），π（i+1）}=C_{π（i+1），1}-C_{π（i），1}-p_{π（i+1），1}。

对于仅存在无等待工件（即α_ij=0）和一般工件（即α_ij→∞）两种工件类型的特殊情况，Finke等[105]指出，当同时存在至少一个无等待工件和一个一般工件时，两机流水车间调度问题即使只考虑排列排序也是“强NP-难”的。Bouquard[106]针对只存在无等待工件和一般工件的两机流水车间调度问题F2｜reg+nwt｜C_max，指出排列排序的最优解不一定是原问题的最优解，证明了其排列排序问题是“强NP-难”的，并分析了两类特殊问题的复杂性：当一般工件的数量上限为常量时，即F2｜reg+nwt，n_R≤q，prmu｜C_max，问题存在多项式最优算法；若无等待工件的数量上限为常量时，即使常量为1，即F2｜reg+nwt，n_NW=1｜C_max，问题也是“NP-难”的。

（2）问题的调度方法

对于具有等待时间上限的置换流水车间问题（即排列排序问题），Yang和Chern[65]采用分支定界法对两机环境下的置换流水车间调度问题求解，利用Johnson规则设计分支定界的下界值；李铁克等[104]分析了等待时间上限与可行调度的解析关系及目标函数的特殊性质，在排列排序基础上提出了基于贪婪插入思想的启发式算法。首先，采用贪婪插入思想生成具有较小Makespan的初始调度，然后，利用插入算法搜索更优的调度解，在求解过程中，采用递归回溯解消等待时间上限的冲突。王晶等[107]提出了一种结合交换邻域、变邻域和禁忌搜索的动态变邻域搜索算法，算法采用工件对比较和贪婪插入规则构建初始调度，通过嵌入3-opt和2-opt实现动态变邻域搜索，并在迭代过程中加入动态禁忌策略。对于不限于排列排序的流水车间调度问题，尹兆涛等[108]采用嵌入约束满足和变邻域搜索技术的混合遗传算法求解，算法基于约束满足思想，通过递归回溯和约束传播获得满足等待时间上限约束的工件开工时间，根据回溯工件的位置信息设计遗传算法的交叉算子和变异算子，利用变邻域搜索技术增强算法的收敛性。

对于具有其他特殊约束的流水车间调度问题，Su[109]针对第一阶段为批处理机的两机流水车间环境，以最小化Makespan为优化目标，建立了问题的混合整数规划模型，并提出了一种启发式算法。

Li Tieke等[110]将问题进一步扩展到混合流水车间调度，针对等待时间上限约束，通过启发式算法求解，应用NEH算法形成工件初始排序。尹兆涛等[111]考虑了具有交货期及等待时间上限要求的混合流水车间调度问题，提出一种结合了递归回溯、启发式修复与邻域搜索的混合求解算法。Gicquel等[112]针对阶段间无缓冲区的情况，基于离散时间表示法和整数规划模型，提出了一种精确算法；轩华[113]采用基于工件解耦的分解策略应用拉格朗日（Lagrangian）松弛算法进行求解，使得总加权完成时间和工件等待惩罚之和最小；Attar等[114]针对存在变速平行机的情况，提出了一种基于生物地理学的优化算法（Biogeography-based Optimization，BBO）；Cheng等[115]建立了问题的约束满足优化模型，并设计了嵌入局域搜索的约束满足优化算法；常晓坤和董明[116]针对产品需求时间及机器加工时间不确定的动态环境，建立了两阶段随机规划模型，并开发了L型切面的求解算法。此外，林晨和张志英[117]从分段涂装作业中提炼出一类存在等待时间限制和运输能力约束两阶段批处理混合流水车间调度问题，设计了混合多种启发式规则的差分进化算法。

对于其他车间调度问题，王朝晖等[118]针对最小化工件延误时间的加权平方和的优化目标，采用Lagrangian松弛法结合动态规划求得问题的解。Chen和Yang[119]对不同生产环境的具有等待时间上限的调度问题的建模机制进行了研究，具体包括开放车间、作业车间、流水车间和流水车间排列排序这四类问题。

1.4.3　具有等待时间上下限的调度问题

在具有等待时间下限和等待时间上限的调度问题的研究基础上，研究者们进一步考虑了同时具有等待时间上下限的调度问题。

（1）具有等待时间上下限的流水车间排列排序问题

自2006年起，Fondrevelle、Oulamara和Portmann三位学者致力于研究具有等待时间上下限的流水车间排列排序问题，在问题复杂性和算法求解方面均取得了一定成果。

2006年，Fondrevelle等[120]研究了以Makespan为优化目标的具有等待时间上下限的流水车间排列排序问题。在问题的复杂性方面，证明了当上限严格大于下限时（β_i<α_i），即使所有工件具有相同的上限值和下限值，其两机问题也是“强NP-难”的；而当上限等于下限时，即β_i=α_i（∀i∈{1，…，n}），采用Gilmore和Gomory[84]提出的算法即可获得两机情况下的最优解。在问题求解方面，设计了分支定界法，并提出了四种下界计算方法和两种上界计算方法，通过数据实验对各种上下界对于算法求解性能的影响进行了分析。

2008年，Fondrevelle等[121]针对工件在阶段间的等待时间具有上下限约束的流水车间排列排序问题，考虑了最小化加权总机器完工时间（Weighted Sum of Machine Completion Times）的优化目标。机器完工时间定义为最后离开该机器的工件完工时间，该目标可以用来衡量机器空闲时间，提高设备利用率。针对此问题，分析了在两机和三机情况下各类问题的复杂性，并采用分支定界法求解。

2009年，Fondrevelle等[122]考虑了一类等待时间严格等于定值的流水车间排列排序问题，即上限值与下限值相等的情况。以最小化最大延误为目标，对问题中工件可能存在的类型进行了分析，给出了采用EDD规则能够获得最优解的特殊情况，并针对两机环境给出了工件优先关系（DR），在此基础上，设计了分支定界法求解。

此外，Dhouib等[123]以最小化总拖期工件数为目标，建立了混合整数规划模型，并采用模拟退火算法求解。Hamdi等[124]考虑了最小化总拖期目标，基于拉格朗日松弛探讨了问题的上下界。

（2）具有等待时间上下限的Job Shop调度问题

Caumond等[125]考虑了工件在阶段间的开工时间具有等待时间上下限的Job Shop调度问题，创建了目标为Makespan的问题模型，设计了一种算法求解框架，该框架以析取图和Memetic算法为基础，采用析取图对问题建模，并应用Memetic算法进行机器指派，确定工件的加工机器及各机器上的工件加工顺序。

Artigues等[126]针对以Makespan为目标的具有等待时间上下限的Job Shop调度问题，创建了约束满足优化模型，分析了以工序为节点和以时间为节点的析取图表示方式，在此基础上设计了一种析取约束传播的方法，并将其嵌入分支定界算法进行求解；此外，还提出了一种基于工件插入思想的启发式算法；最后，通过基于Benchmark的数据实验验证了上述两种算法的有效性。

1.4.4　研究现状总结

从上述文献分析中可以看出，虽然等待时间受限的紧凑调度问题广泛存在于流程工业的生产管理过程，但是相关研究尚处于初步探索阶段，无论是问题的基本性质还是求解方法都缺乏系统、深入的研究：

第一，在问题性质方面，需要进一步明确问题的复杂性，探讨基于排列排序设计调度算法的可行性和有效性，为算法开发提供理论基础。

第二，在求解策略方面，需要深入研究能够指导算法开发的问题特征，以及这些特征在算法设计中的应用方式，以此为基础研究问题的求解策略，为进一步开发高效的核心算法提供指导。

第三，在调度算法方面，对于近似算法，尤其是在结合问题特征的近似算法研发方面，有必要针对问题的特点开发能够在短时间获得问题满意解的快速近似算法，使其能够有效求得大规模调度问题的解，满足实际生产的需要。

1.2节和1.3节对流水车间调度和紧凑调度研究现状的总结，特别是对一般流水车间调度问题在设计求解算法时惯用的经典调度策略的分析，对于探索等待时间受限的紧凑型流水车间调度可能存在的问题特征、研究等待时间约束下的算法构造策略、扩展和改进已有的流水车间调度算法、利用问题性质开发符合问题特征的新调度方法等方面具有重要的指导意义。