第2章　具有等待时间上限的流水车间调度性质

2.1　引言

等待时间上限约束广泛存在于高温连续作业或中间产品性质不稳定的流程工业，如钢铁生产、玻璃制造、食品加工等。由于生产过程的高度连续性，往往要求工件在相邻阶段的等待时间不超过一定的时间上限，从而产生了具有等待时间上限的流水车间调度问题。

在流水车间调度领域，关于调度方法的研究多以排列排序为基础，因此有必要对具有等待时间上限的流水车间调度问题的基本性质展开研究，为以排列排序为基础的调度方法提供理论依据。

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

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

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

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

其中，∏为所有排列排序解的集合，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-难”的。

由以上研究可以看出，目前对于具有等待时间上限的流水车间调度问题的基本性质研究还不够充分，算法设计的理论基础尚待完善。本章针对此问题，在理论上分析等待时间上限这一特殊约束下流水车间调度问题的复杂性，探讨基于排列排序的算法实现问题求解的可行性和有效性，旨在为进一步开展对此类问题的方法研究提供理论依据。