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

于艳辉 李志华

［摘要］ 本文针对缓冲区有限的两阶段置换流水车间调度问题的基本性质进行了分析，指出了缓冲区的大小对于问题最优解的影响并证明了该问题的复杂性。通过对原问题及其特例在目标函数之间关系方面的研究，为算法获得较好的初始解提供了依据。这些性质为设计求解算法提供了理论依据。

［关键词］ 置换流水车间； 缓冲区有限； 复杂性分析

doi : 10 . 3969 / j . issn . 1673 - 0194 . 2012 . 07. 032

［中图分类号］F406.2［文献标识码］A［文章编号］1673 - 0194（2012）07- 0066- 03

０引言

传统的流水车间调度模型通常假定各机器间的缓冲区无穷大，然而在许多实际生产过程中，由于受到缓冲区空间或存储设备的限制（如中间库存等），缓冲区的大小是有限的。缓冲区有限的流水车间调度问题（ＬＢＦＳＳ）广泛存在于钢铁、化工、制药等带有中间存储环节的生产系统中［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 ——所有工件序号的集合，i∈I = ｛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 < +∞）。

不妨设工件数为4n + 1，缓冲区容量限制为2 ≤ b < +∞，且

A：p01 = 0，p02 = （b + 1/2）M

B：pi1 = 1/2 M，pi2 = ci，i = 1，…，3n

C：p3n + i，1 = bM，p3n + i，2 = （b + 1/2）M，i = 1，…，n - 1

D：p4n，1 = （b + 1/2）M，p4n，2 = 0

我们注意到，如果三划分问题有解当且仅当调度中各工件之间无空闲时间，即C*max = n（b + 3/2）M + （b + 1/2）M为工件分别在M1，M2上的加工时间之和。

2.１工件A最先加工

反证法：若工件A不是第一个加工，即A在Bi或Ci之后加工，显然会使M2上出现空闲，即Cmax > C*max，所以要三划分问题有解，工件A必须第一个加工。

2.２工件D最后加工

反证法：若工件D不是最后加工，有任意的C中的工件Ji在D之后加工，均有：Si2 = max｛C3n，2，Ci，1｝ = max｛C3n，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 < ci < M / 2，设工件集合B中的工件数为n，则nM / 4 < nci < nM / 2，若要满足调度中各工件之间无空闲时间，只有n = 3。

若排列在A和C中间的工件集合B中工件数是１，则，M1 ∶ t1 = 1/2 M + bM = （1/2 + b）M，M2 ∶ t2 = （b + １／２）M ＋ ci，故t2 - t1 = ci > 0，即Cmax > C*max。同理，工件集合B中工件数是２或者大于３时也会产生空闲时间，使得Cmax > C*max，因此工件集合B中工件数是３。

2.５紧邻B之后的工件是C，且B与C交替排列

反证法：若紧邻B之后的工件是B，则

M1 ∶ t1 = 1/2 M × 6 = 3M

M2 ∶ 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是集合Nk∈N（k = 1，…，n）中的工件，又因为调度中各工件之间没有空闲时间，因此有下列等式成立：

Cl2，1 = Cl1，1 + 1/2 M + 1/2 M + 1/2 M + bM = Cl1，1 + （b+ 3/2）M

Cl2，2 = Cl1，2 + ci1 + ci2 + ci3 + （b + 1/2）M

Cl2，2 = Cl2，1 + （b + 1/2）M

Cl1，2 = Cl1，1 + （b + 1/2）M

即：Cl2，1 + （b + 1/2）M = Cl1，2 + ci1 + ci2 + ci3 + （b + 1/2）M

Cl1，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ｗｏ－ａｎｄ Tｈｒｅｅ－Sｔａｇｅ Pｒｏｄｕｃｔｉｏｎ Sｃｈｅｄｕｌｅｓ ｗｉｔｈ Sｅｔｕｐ Tｉｍｅｓ Iｎｃｌｕｄｅｄ ［Ｊ］． Ｎａｖａｌ Ｒｅｓｅａｒｃｈ Ｌｏｇｉｓｔｉｃｓ Ｑｕａｒｔｅｒｌｙ， １９５４，１（1）：６１－６8．

［4］ Ｇａｒｅｙ Ｍ Ｒ， Ｊｏｈｎｓｏｎ Ｄ Ｓ， Ｓｅｔｈｉ Ｒ． Ｔｈｅ Cｏｍｐｌｅｘｉｔｙ ｏｆ Fｌｏｗｓｈｏｐ ａｎｄ Jｏｂｓｈｏｐ Sｃｈｅｄｕｌｉｎｇ ［Ｊ］． Ｍａｔｈｅｍａｔｉｃｓ ｏｆ Ｏｐｅｒａｔｉｏｎｓ Ｒｅｓｅａｒｃｈ，１９７６，１（２）：１１７－１２９ ．