緩沖區(qū)有限的兩階段置換流水車間調(diào)度問題性質(zhì)分析

于艷輝 李志華

［摘要］ 本文針對緩沖區(qū)有限的兩階段置換流水車間調(diào)度問題的基本性質(zhì)進行了分析，指出了緩沖區(qū)的大小對于問題最優(yōu)解的影響并證明了該問題的復雜性。通過對原問題及其特例在目標函數(shù)之間關系方面的研究，為算法獲得較好的初始解提供了依據(jù)。這些性質(zhì)為設計求解算法提供了理論依據(jù)。

［關鍵詞］ 置換流水車間； 緩沖區(qū)有限； 復雜性分析

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

［中圖分類號］F406.2［文獻標識碼］A［文章編號］1673 - 0194（2012）07- 0066- 03

０引言

傳統(tǒng)的流水車間調(diào)度模型通常假定各機器間的緩沖區(qū)無窮大，然而在許多實際生產(chǎn)過程中，由于受到緩沖區(qū)空間或存儲設備的限制（如中間庫存等），緩沖區(qū)的大小是有限的。緩沖區(qū)有限的流水車間調(diào)度問題（ＬＢＦＳＳ）廣泛存在于鋼鐵、化工、制藥等帶有中間存儲環(huán)節(jié)的生產(chǎn)系統(tǒng)中［1-2］。對于ＬＢＦＳＳ問題存在兩種特殊情況：當緩沖區(qū)大小為零時，該問題轉(zhuǎn)化為阻塞流水車間調(diào)度問題（Ｂｌｏｃｋｉｎｇ ＦＳＳ，ＢＦＳＳ）；當緩沖區(qū)大小為無窮時，該問題轉(zhuǎn)化為一般流水車間調(diào)度問題（ＦＳＳ）。

對于ＦＳＳ問題，當階段數(shù)為２時，Ｊｏｈｎｓｏｎ（１９５４）［3］提出了多項式優(yōu)化算法，當階段數(shù)為３及以上時，該問題是ＮＰ難問題［4］。作為另一特例的ＢＦＳＳ問題，已被證明當階段數(shù)為３時是ＮＰ難問題［5-6］，并且算法多為啟發(fā)式算法。目前對緩沖區(qū)有限的流水車間調(diào)度問題的研究較少。文獻［7］對緩沖區(qū)有限的兩階段流水車間調(diào)度問題的復雜性進行了分析，并給出了該問題與兩階段無等待流水車間調(diào)度ｍａｋｅｓｐａｎ之間的關系：C0* / Cb* = （2b + 1） / （b + 1），文獻［8］針對多階段的混合流水車間調(diào)度問題得到了相似的結(jié)論。文獻［9］提出了一種多搜索模式遺傳算法，算法使用多個交叉和變異操作進行解空間的探索和改良，并采用基于有向圖的鄰域結(jié)構(gòu)來增強局部搜索。文獻［10］針對隨機有限緩沖區(qū)流水線調(diào)度問題提出了混合差分進化算法，其中差分進化用于執(zhí)行全局搜索和局部搜索，最優(yōu)計算量分配用于對有限計算量進行合理分配，從而保證優(yōu)質(zhì)解得到較多仿真計算量，并提高了在噪聲環(huán)境下獲得優(yōu)質(zhì)解的置信度。

從已有研究來看，對具有緩沖區(qū)限制的流水車間調(diào)度問題的基本性質(zhì)的研究還不夠充分，其算法設計的理論基礎尚待完善。為此，本文針對該問題的基本情況——兩階段置換流水車間調(diào)度問題，在理論上探討了緩沖區(qū)的大小對問題最優(yōu)解的影響；是否存在基于排列排序的最優(yōu)解；該問題及其兩種特殊情況在目標函數(shù)之間的關系等基礎問題，旨在為進一步研究此類問題提供理論依據(jù)。

１問題模型

1.１問題描述

緩沖區(qū)有限的兩階段置換流水線調(diào)度問題可描述為：n個工件｛J1，J2，…，Jn｝依次經(jīng)過２個階段的加工，其中每個階段只有１臺機器。兩階段間存在緩沖區(qū)，緩沖區(qū)內(nèi)工件的個數(shù)不能超過上限，本文假定緩沖區(qū)上限為b。在每臺機器上，工件的加工順序均相同，即工件在緩沖區(qū)中均服從先進先出規(guī)則（ＦＩＦＯ），本文研究的調(diào)度問題以最小化最大完成時間（ｍａｋｅｓｐａｎ）為目標函數(shù)。應用Ｇｒａｈａｍ［11］提出的三元組表示法，此問題可表示為：F2 | Bi ≤ b|Cmax。

1.２數(shù)學模型

為便于描述，定義符號和變量如下：

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在兩階段間的緩沖區(qū)的大小；

b ——緩沖區(qū)上限；

π = ｛π（1），π（2），…，π（n）｝ —— 可行加工順序。

緩沖區(qū)有限的兩階段置換流水線調(diào)度問題的數(shù)學模型如下：

其中，式（１）表示目標函數(shù)：最小化最大完成時間；式（３）表示工件在加工時不允許中斷； 式（４）、式（５）表示不同情況下工件的開工時間；式（６）表示變量的取值約束。

２問題復雜性

在流水車間調(diào)度問題中，當每臺機器上加工工件順序相同時，稱為排列排序。在一般流水車間調(diào)度問題中，我們已經(jīng)知道當階段數(shù)為２時，可以通過基于排列排序的Ｊｏｈｎｓｏｎ規(guī)則在多項式時間得到最優(yōu)解。但是當兩階段間緩沖區(qū)的大小變?yōu)橛邢迺r，問題的性質(zhì)將發(fā)生根本性改變。

定理１對于F2 | Bi ≤ b | Cmax問題，當b = 1時，在任一可行調(diào)度中，兩臺機器上工件的加工順序必然相同。

證明（反證法）：不失一般性，設在任一可行調(diào)度中M1上工件i在工件j之前加工，在M2上工件j在工件i之前加工，由于工件j必須要在M1上完成加工之后才能進入M2加工，并且工件i在工件j之前加工，因此工件i和工件j均需進入緩沖區(qū)，與b = 1的條件相矛盾。因此，兩臺機器上工件的加工順序必然相同。

根據(jù)定理１，我們可以得到以下推論：

推論１對于F2 | Bi = 1 | Cmax問題，最優(yōu)調(diào)度必然存在于排列排序中。

推論１表明，當存在緩沖區(qū)限制并且上限為１時，仍然存在基于排列排序的最優(yōu)解。進一步，當2 ≤ b ≤ +∞時，我們給出該問題的復雜性分析。

定理２具有最大緩沖區(qū)限制的兩階段置換流水車間調(diào)度問題F2 | Bi ≤ b | Cmax是強NP難的（2 ≤ b < +∞）。

不妨設工件數(shù)為4n + 1，緩沖區(qū)容量限制為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

我們注意到，如果三劃分問題有解當且僅當調(diào)度中各工件之間無空閑時間，即C*max = n（b + 3/2）M + （b + 1/2）M為工件分別在M1，M2上的加工時間之和。

2.１工件A最先加工

反證法：若工件A不是第一個加工，即A在Bi或Ci之后加工，顯然會使M2上出現(xiàn)空閑，即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出現(xiàn)空閑，Cmax > C*max。因此要保證得到最優(yōu)調(diào)度，D必須最后加工。若B中有工件在D之后加工，情況相同。

2.３緊鄰A之后的工件必須是B中的工件

反證法：若緊鄰A之后的工件是C中的工件Ji（i = 3n + 1，…，4n - 1），則Ji在第一階段M1上會產(chǎn)生長度為M/2的空閑時間，即Cmax > C*max，所以緊鄰A之后的工件必須是B中的工件。

2.４工件集合B中的工件數(shù)為３

因為M / 4 < ci < M / 2，設工件集合B中的工件數(shù)為n，則nM / 4 < nci < nM / 2，若要滿足調(diào)度中各工件之間無空閑時間，只有n = 3。

若排列在A和C中間的工件集合B中工件數(shù)是１，則，M1 ∶ t1 = 1/2 M + bM = （1/2 + b）M，M2 ∶ t2 = （b + １／２）M ＋ ci，故t2 - t1 = ci > 0，即Cmax > C*max。同理，工件集合B中工件數(shù)是２或者大于３時也會產(chǎn)生空閑時間，使得Cmax > C*max，因此工件集合B中工件數(shù)是３。

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上會出現(xiàn)（t2 - t1）時間的阻塞。

若緊鄰C之后的工件是C，顯然會在M1上出現(xiàn)長度至少為M的空閑。所以緊鄰B之后的工件是C，且B與C交替排列。

設Ji1、Ji2、Ji3是集合Nk∈N（k = 1，…，n）中的工件，又因為調(diào)度中各工件之間沒有空閑時間，因此有下列等式成立：

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，因此，具有最大緩沖區(qū)限制的兩階段置換流水車間調(diào)度問題是強NP難的。

由此可知，當緩沖區(qū)b = 1時，滿足排列排序要求的任一工件加工序列均可構(gòu)成可行調(diào)度，而最優(yōu)調(diào)度必存在于排列排序中；當b ≥ 2時，問題F2 | Bi ≤ b | Cmax具有強ＮＰ難 的復雜性，下面將通過該問題與其特例在目標函數(shù)方面的分析，考慮其可行解的情況。

３目標函數(shù)的關系

具有最大緩沖區(qū)限制的流水車間調(diào)度問題存在以下兩種特例：當緩沖區(qū)為零時，該問題轉(zhuǎn)化為阻塞流水車間調(diào)度問題；當緩沖區(qū)上限趨于無窮時，該問題轉(zhuǎn)化為一般流水車間調(diào)度問題。

下面將討論F2 | Bi ≤ b | Cmax與兩階段阻塞流水車間調(diào)度問題和兩階段流水車間調(diào)度問題目標函數(shù)之間的關系。

設F2 | Bi ≤ b | Cmax的最優(yōu)目標值為Cmax（LBFSS），與之相對應的阻塞問題最優(yōu)目標值為Cmax（BFSS），一般問題的最優(yōu)目標值為Cmax（FSS），則三者之間存在以下關系：

定理３對于F2 | Bi ≤ b | Cmax問題，存在Cmax（LBFSS） ≥ Cmax（FSS）成立。

證明：設π為F2 | Bi ≤ b | Cmax的任一可行解，在F2 || Cmax中相應的存在一個π′，與其具有相同的加工順序。在π′中若存在不滿足最大緩沖區(qū)限制約束的工件，則需要將開工時間向右移動，以滿足B的要求，如圖２所示。 因而Cmax（π） ≥ Cmax（π′），又因π為F2 | Bi ≤ b | Cmax為問題的任一可行解，因此Cmax（LBFSS） ≥ Cmax（FSS）。

定理４對于F2 | Bi ≤ b | Cmax問題，存在Cmax（LBFSS） ≤ Cmax（BFSS）成立。

證明：設π為F2 | BFSS | Cmax的最優(yōu)解，由于阻塞流水車間不存在緩沖區(qū)，因此對于在M1上完成加工的工件只能停留在M1上，直到M2上空閑時才能繼續(xù)加工。與之相對應的問題F2 | Bi ≤ b | Cmax，存在解π′，當緩沖區(qū)有空閑時，在M1上完成加工的工件可進入緩沖區(qū)等待，在滿足緩沖區(qū)限制的條件下，可以將工件的開工時間適當提前，如圖３所示，因此，Cmax（LBFSS） ≤ Cmax（BFSS）。

ＬＢＦＳＳ問題的兩個特例在兩階段的情況下都存在基于排列排序的最優(yōu)啟發(fā)式算法：F2 || Cmax可采用Ｊｏｈｎｓｏｎ規(guī)則，F(xiàn)2 | BFSS | Cmax可采用Ｇｉｌｍｏｒｅ和Ｇｏｍｏｒｙ［12］提出的Ｇｉｌｍｏｒｅ－Ｇｏｍｏｒｙ算法，均可在多項式時間內(nèi)得到最優(yōu)解。通過上述定理３和定理４對F2 | Bi ≤ b | Cmax問題上、下界的探討，可以看出，當Cmax（FSS） = Cmax（BFSS）時，F(xiàn)2 | Bi ≤ b | Cmax問題的邊界值就是最優(yōu)目標值，并可將Ｇｉｌｍｏｒｅ－Ｇｏｍｏｒｙ算法得到的最優(yōu)解作為原問題較好的初始解。

４結(jié)論

在許多流程工業(yè)中，都會出現(xiàn)緩沖區(qū)有限的要求。本文對緩沖區(qū)有限的兩階段置換流水車間調(diào)度問題的基本性質(zhì)進行了研究，得出以下結(jié)論：當緩沖區(qū)上限約束比較緊時，該問題存在著基于排列排序的最優(yōu)調(diào)度，當緩沖區(qū)b ≥ 2時，問題具有強ＮＰ難的復雜性，進一步通過對原問題與其特殊情況三者之間在目標函數(shù)方面的分析，可知：Cmax（BFSS）和Cmax（FSS）可分別作為原問題目標函數(shù)值的上界和下界，并且由于F2 || Cmax和F2 | BFSS | Cmax均可在多項式時間內(nèi)得到最優(yōu)解，因此，原問題可利用Ｇｉｌｍｏｒｅ－Ｇｏｍｏｒｙ算法獲得較好的初始調(diào)度。

主要參考文獻

［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ｃｈｅｄｕｌｉｎｇ ［Ｊ］． Ｍａｔｈｅｍａｔｉｃｓ ｏｆ Ｏｐｅｒａｔｉｏｎｓ Ｒｅｓｅａｒｃｈ，１９７６，１（２）：１１７－１２９ ．