缓冲区有限的两阶段置换流水车间调度问题性质分析.doc

缓冲区有限的两阶段置换流水车间调度问题性质分析摘 要 本文针对缓冲区有限的两阶段置换流水车间调度问题的基本性质进行了分析，指出了缓冲区的大小对于问题最优解的影响并证明了该问题的复杂性。通过对原问题及其特例在目标函数之间关系方面的研究，为算法获得较好的初始解提供了依据。这些性质为设计求解算法提供了理论依据。关键词 置换流水车间； 缓冲区有限； 复杂性分析 引 言传统的流水车间调度模型通常假定各机器间的缓冲区无穷大，然而在许多实际生产过程中，由于受到缓冲区空间或存储设备的限制（如中间库存等），缓冲区的大小是有限的。缓冲区有限的流水车间调度问题（）广泛存在于钢铁、化工、制药等带有中间存储环节的生产系统中1-2。对于问题存在两种特殊情况：当缓冲区大小为零时，该问题转化为阻塞流水车间调度问题（ ，）；当缓冲区大小为无穷时，该问题转化为一般流水车间调度问题（）。对于问题，当阶段数为时，（）3提出了多项式优化算法，当阶段数为及以上时，该问题是难问题4。作为另一特例的问题，已被证明当阶段数为时是难问题5-6，并且算法多为启发式算法。目前对缓冲区有限的流水车间调度问题的研究较少。文献7对缓冲区有限的两阶段流水车间调度问题的复杂性进行了分析，并给出了该问题与两阶段无等待流水车间调度之间的关系：c0* / cb* = （2b + 1） / （b + 1），文献8针对多阶段的混合流水车间调度问题得到了相似的结论。文献9提出了一种多搜索模式遗传算法，算法使用多个交叉和变异操作进行解空间的探索和改良，并采用基于有向图的邻域结构来增强局部搜索。文献10针对随机有限缓冲区流水线调度问题提出了混合差分进化算法，其中差分进化用于执行全局搜索和局部搜索，最优计算量分配用于对有限计算量进行合理分配，从而保证优质解得到较多仿真计算量，并提高了在噪声环境下获得优质解的置信度。从已有研究来看，对具有缓冲区限制的流水车间调度问题的基本性质的研究还不够充分，其算法设计的理论基础尚待完善。为此，本文针对该问题的基本情况两阶段置换流水车间调度问题，在理论上探讨了缓冲区的大小对问题最优解的影响；是否存在基于排列排序的最优解；该问题及其两种特殊情况在目标函数之间的关系等基础问题，旨在为进一步研究此类问题提供理论依据。 问题模型1. 问题描述缓冲区有限的两阶段置换流水线调度问题可描述为：n个工件j1，j2，jn依次经过个阶段的加工，其中每个阶段只有台机器。两阶段间存在缓冲区，缓冲区内工件的个数不能超过上限，本文假定缓冲区上限为b。在每台机器上，工件的加工顺序均相同，即工件在缓冲区中均服从先进先出规则（），本文研究的调度问题以最小化最大完成时间（）为目标函数。应用11提出的三元组表示法，此问题可表示为：f2 | bi b|cmax。1. 数学模型为便于描述，定义符号和变量如下：i 工件序号，ji表示第i个工件；i 所有工件序号的集合，ii = 1，2，；j 阶段序号，mj表示第j阶段的机器，j = 1 ，2；pij 工件ji在机器mj上的加工时间；sij 工件ji在机器mj上的开工时间；cij 工件ji在机器mj上的完工时间；bi 工件ji在两阶段间的缓冲区的大小；b 缓冲区上限； = （1），（2），（n） 可行加工顺序。缓冲区有限的两阶段置换流水线调度问题的数学模型如下：其中，式（）表示目标函数：最小化最大完成时间；式（）表示工件在加工时不允许中断； 式（）、式（）表示不同情况下工件的开工时间；式（）表示变量的取值约束。 问题复杂性在流水车间调度问题中，当每台机器上加工工件顺序相同时，称为排列排序。在一般流水车间调度问题中，我们已经知道当阶段数为时，可以通过基于排列排序的规则在多项式时间得到最优解。但是当两阶段间缓冲区的大小变为有限时，问题的性质将发生根本性改变。定理 对于f2 | bi b | cmax问题，当b = 1时，在任一可行调度中，两台机器上工件的加工顺序必然相同。证明（反证法）：不失一般性，设在任一可行调度中m1上工件i在工件j之前加工，在m2上工件j在工件i之前加工，由于工件j必须要在m1上完成加工之后才能进入m2加工，并且工件i在工件j之前加工，因此工件i和工件j均需进入缓冲区，与b = 1的条件相矛盾。因此，两台机器上工件的加工顺序必然相同。根据定理，我们可以得到以下推论：推论 对于f2 | bi = 1 | cmax问题，最优调度必然存在于排列排序中。推论表明，当存在缓冲区限制并且上限为时，仍然存在基于排列排序的最优解。进一步，当2 b +时，我们给出该问题的复杂性分析。定理 具有最大缓冲区限制的两阶段置换流水车间调度问题f2 | bi b | cmax是强np难的（2 b c*max，所以要三划分问题有解，工件a必须第一个加工。2. 工件d最后加工反证法：若工件d不是最后加工，有任意的c中的工件ji在d之后加工，均有：si2 = maxc3n，2，ci，1 = maxc3n，2，c4n，1 + bm，因为c3n，2 = c4n，1，所以si，2 = ci，1 c3n，2，即m2出现空闲，cmax c*max。因此要保证得到最优调度，d必须最后加工。若b中有工件在d之后加工，情况相同。2. 紧邻a之后的工件必须是b中的工件反证法：若紧邻a之后的工件是c中的工件ji（i = 3n + 1，4n - 1），则ji在第一阶段m1上会产生长度为m/2的空闲时间，即cmax c*max，所以紧邻a之后的工件必须是b中的工件。2. 工件集合b中的工件数为因为m / 4 0，即cmax c*max。同理，工件集合b中工件数是或者大于时也会产生空闲时间，使得cmax c*max，因此工件集合b中工件数是。2. 紧邻b之后的工件是c，且b与c交替排列反证法：若紧邻b之后的工件是b，则m1 t1 = 1/2 m 6 = 3mm2 t2 = （b + ）m 3ci 5/2 m + 3 1/4 m = 13/4 m 3 m即t2 t1，则在m1上会出现（t2 - t1）时间的阻塞。若紧邻c之后的工件是c，显然会在m1上出现长度至少为m的空闲。所以紧邻b之后的工件是c，且b与c交替排列。设ji1、ji2、ji3是集合nkn（k = 1，n）中的工件，又因为调度中各工件之间没有空闲时间，因此有下列等式成立：cl2，1 = cl1，1 + 1/2 m + 1/2 m + 1/2 m + bm = cl1，1 + （b+ 3/2）mcl2，2 = cl1，2 + ci1 + ci2 + ci3 + （b + 1/2）mcl2，2 = cl2，1 + （b + 1/2）mcl1，2 = cl1，1 + （b + 1/2）m即：cl2，1 + （b + 1/2）m = cl1，2 + ci1 + ci2 + ci3 + （b + 1/2）mcl1，1 + （b+ 3/2）m + （b + 1/2）m = cl1，1 + （b + 1/2）m + ci1 + ci2 + ci3 + （b + 1/2）m得ci1 + ci2 + ci3 = m综上所述，当2 b +时，三划分问题可以归约为问题f2 | bi b | cmax，因此，具有最大缓冲区限制的两阶段置换流水车间调度问题是强np难的。由此可知，当缓冲区b = 1时，满足排列排序要求的任一工件加工序列均可构成可行调度，而最优调度必存在于排列排序中；当b 2时，问题f2 | bi b | cmax具有强难 的复杂性，下面将通过该问题与其特例在目标函数方面的分析，考虑其可行解的情况。 目标函数的关系具有最大缓冲区限制的流水车间调度问题存在以下两种特例：当缓冲区为零时，该问题转化为阻塞流水车间调度问题；当缓冲区上限趋于无穷时，该问题转化为一般流水车间调度问题。下面将讨论f2 | bi b | cmax与两阶段阻塞流水车间调度问题和两阶段流水车间调度问题目标函数之间的关系。设f2 | bi b | cmax的最优目标值为cmax（lbfss），与之相对应的阻塞问题最优目标值为cmax（bfss），一般问题的最优目标值为cmax（fss），则三者之间存在以下关系：定理 对于f2 | bi b | cmax问题，存在cmax（lbfss） cmax（fss）成立。证明：设为f2 | bi b | cmax的任一可行解，在f2 | cmax中相应的存在一个，与其具有相同的加工顺序。在中若存在不满足最大缓冲区限制约束的工件，则需要将开工时间向右移动，以满足b的要求，如图所示。 因而cmax（） cmax（），又因为f2 | bi b | cmax为问题的任一可行解，因此cmax（lbfss） cmax（fss）。定理 对于f2 | bi b | cmax问题，存在cmax（lbfss） cmax（bfss）成立。证明：设为f2 | bfss | cmax的最优解，由于阻塞流水车间不存在缓冲区，因此对于在m1上完成加工的工件只能停留在m1上，直到m2上空闲时才能继续加工。与之相对应的问题f2 | bi b | cmax，存在解，当缓冲区有空闲时，在m1上完成加工的工件可进入缓冲区等待，在满足缓冲区限制的条件下，可以将工件的开工时间适当提前，如图所示，因此，cmax（lbfss） cmax（bfss）。问题的两个特例在两阶段的情况下都存在基于排列排序的最优启发式算法：f2 | cmax可采用规则，f2 | bfss | cmax可采用和12提出的算法，均可在多项式时间内得到最优解。通过上述定理和定理对f2 | bi b | cmax问题上、下界的探讨，可以看出，当cmax（fss） = cmax（bfss）时，f2 | bi b | cmax问题的边界值就是最优目标值，并可将算法得到的最优解作为原问题较好的初始解。 结 论在许多流程工业中，都会出现缓冲区有限的要求。本文对缓冲区有限的两阶段置换流水车间调度问题的基本性质进行了研究，得出以下结论：当缓冲区上限约束比较紧时，该问题存在着基于排列排序的最优调度，当缓冲区b 2时，问题具有强难的复杂性，进一步通过对原问题与其特殊情况三者之间在目标函数方面的分析，可知：cmax（bfss）和cmax（fss）可分别作为原问题目标函数值的上界和下界，并且由于f2 | cmax和f2 | bfss | cmax均可在多项式时间内得到最优解，因此，原问题可利用算法获得较好的初始调度。主要参考文献1 ， r a r- h f s f i b ，（）：2 ， ， e h g a f s l b ，（）：3 t ts p s s t i ， ，（1）：84