０ 引 言
傳統(tǒng)的流水車(chē)間調(diào)度模型通常假定各機(jī)器間的緩沖區(qū)無(wú)窮大，然而在許多實(shí)際生產(chǎn)過(guò)程中，由于受到緩沖區(qū)空間或存儲(chǔ)設(shè)備的限制（如中間庫(kù)存等），緩沖區(qū)的大小是有限的。緩沖區(qū)有限的流水車(chē)間調(diào)度問(wèn)題（ＬＢＦＳＳ）廣泛存在于鋼鐵、化工、制藥等帶有中間存儲(chǔ)環(huán)節(jié)的生產(chǎn)系統(tǒng)中［1-2］。對(duì)于ＬＢＦＳＳ問(wèn)題存在兩種特殊情況：當(dāng)緩沖區(qū)大小為零時(shí)，該問(wèn)題轉(zhuǎn)化為阻塞流水車(chē)間調(diào)度問(wèn)題（Ｂｌｏｃｋｉｎｇ ＦＳＳ，ＢＦＳＳ）；當(dāng)緩沖區(qū)大小為無(wú)窮時(shí)，該問(wèn)題轉(zhuǎn)化為一般流水車(chē)間調(diào)度問(wèn)題（ＦＳＳ）。
對(duì)于ＦＳＳ問(wèn)題，當(dāng)階段數(shù)為２時(shí)，Ｊｏｈｎｓｏｎ（１９５４）［3］提出了多項(xiàng)式優(yōu)化算法，當(dāng)階段數(shù)為３及以上時(shí)，該問(wèn)題是ＮＰ難問(wèn)題［4］。作為另一特例的ＢＦＳＳ問(wèn)題，已被證明當(dāng)階段數(shù)為３時(shí)是ＮＰ難問(wèn)題［5-6］，并且算法多為啟發(fā)式算法。目前對(duì)緩沖區(qū)有限的流水車(chē)間調(diào)度問(wèn)題的研究較少。文獻(xiàn)［7］對(duì)緩沖區(qū)有限的兩階段流水車(chē)間調(diào)度問(wèn)題的復(fù)雜性進(jìn)行了分析，并給出了該問(wèn)題與兩階段無(wú)等待流水車(chē)間調(diào)度ｍａｋｅｓｐａｎ之間的關(guān)系：C0* / Cb* = （2b + 1） / （b + 1），文獻(xiàn)［8］針對(duì)多階段的混合流水車(chē)間調(diào)度問(wèn)題得到了相似的結(jié)論。文獻(xiàn)［9］提出了一種多搜索模式遺傳算法，算法使用多個(gè)交叉和變異操作進(jìn)行解空間的探索和改良，并采用基于有向圖的鄰域結(jié)構(gòu)來(lái)增強(qiáng)局部搜索。文獻(xiàn)［10］針對(duì)隨機(jī)有限緩沖區(qū)流水線調(diào)度問(wèn)題提出了混合差分進(jìn)化算法，其中差分進(jìn)化用于執(zhí)行全局搜索和局部搜索，最優(yōu)計(jì)算量分配用于對(duì)有限計(jì)算量進(jìn)行合理分配，從而保證優(yōu)質(zhì)解得到較多仿真計(jì)算量，并提高了在噪聲環(huán)境下獲得優(yōu)質(zhì)解的置信度。
從已有研究來(lái)看，對(duì)具有緩沖區(qū)限制的流水車(chē)間調(diào)度問(wèn)題的基本性質(zhì)的研究還不夠充分，其算法設(shè)計(jì)的理論基礎(chǔ)尚待完善。為此，本文針對(duì)該問(wèn)題的基本情況――兩階段置換流水車(chē)間調(diào)度問(wèn)題，在理論上探討了緩沖區(qū)的大小對(duì)問(wèn)題最優(yōu)解的影響；是否存在基于排列排序的最優(yōu)解；該問(wèn)題及其兩種特殊情況在目標(biāo)函數(shù)之間的關(guān)系等基礎(chǔ)問(wèn)題，旨在為進(jìn)一步研究此類(lèi)問(wèn)題提供理論依據(jù)。
?。?問(wèn)題模型
1.１ 問(wèn)題描述
緩沖區(qū)有限的兩階段置換流水線調(diào)度問(wèn)題可描述為：n個(gè)工件｛J1，J2，…，Jn｝依次經(jīng)過(guò)２個(gè)階段的加工，其中每個(gè)階段只有１臺(tái)機(jī)器。兩階段間存在緩沖區(qū)，緩沖區(qū)內(nèi)工件的個(gè)數(shù)不能超過(guò)上限，本文假定緩沖區(qū)上限為b。在每臺(tái)機(jī)器上，工件的加工順序均相同，即工件在緩沖區(qū)中均服從先進(jìn)先出規(guī)則（ＦＩＦＯ），本文研究的調(diào)度問(wèn)題以最小化最大完成時(shí)間（ｍａｋｅｓｐａｎ）為目標(biāo)函數(shù)。應(yīng)用Ｇｒａｈａｍ［11］提出的三元組表示法，此問(wèn)題可表示為：F2 | Bi ≤ b|Cmax。
1.２ 數(shù)學(xué)模型
為便于描述，定義符號(hào)和變量如下：
i ――工件序號(hào)，Ji表示第i個(gè)工件；
I ――所有工件序號(hào)的集合，i∈I = ｛1，2，…｝；
j ――階段序號(hào)，Mj表示第j階段的機(jī)器，j = 1 ，2；
pij ――工件Ji在機(jī)器Mj上的加工時(shí)間；
Sij ――工件Ji在機(jī)器Mj上的開(kāi)工時(shí)間；
Cij ――工件Ji在機(jī)器Mj上的完工時(shí)間；
Bi ――工件Ji在兩階段間的緩沖區(qū)的大?。?
b ――緩沖區(qū)上限；
π = ｛π（1），π（2），…，π（n）｝ ―― 可行加工順序。
緩沖區(qū)有限的兩階段置換流水線調(diào)度問(wèn)題的數(shù)學(xué)模型如下：
其中，式（１）表示目標(biāo)函數(shù)：最小化最大完成時(shí)間；式（３）表示工件在加工時(shí)不允許中斷； 式（４）、式（５）表示不同情況下工件的開(kāi)工時(shí)間；式（６）表示變量的取值約束。
?。?問(wèn)題復(fù)雜性
在流水車(chē)間調(diào)度問(wèn)題中，當(dāng)每臺(tái)機(jī)器上加工工件順序相同時(shí)，稱(chēng)為排列排序。在一般流水車(chē)間調(diào)度問(wèn)題中，我們已經(jīng)知道當(dāng)階段數(shù)為２時(shí)，可以通過(guò)基于排列排序的Ｊｏｈｎｓｏｎ規(guī)則在多項(xiàng)式時(shí)間得到最優(yōu)解。但是當(dāng)兩階段間緩沖區(qū)的大小變?yōu)橛邢迺r(shí)，問(wèn)題的性質(zhì)將發(fā)生根本性改變。
定理１ 對(duì)于F2 | Bi ≤ b | Cmax問(wèn)題，當(dāng)b = 1時(shí)，在任一可行調(diào)度中，兩臺(tái)機(jī)器上工件的加工順序必然相同。
證明（反證法）：不失一般性，設(shè)在任一可行調(diào)度中M1上工件i在工件j之前加工，在M2上工件j在工件i之前加工，由于工件j必須要在M1上完成加工之后才能進(jìn)入M2加工，并且工件i在工件j之前加工，因此工件i和工件j均需進(jìn)入緩沖區(qū)，與b = 1的條件相矛盾。因此，兩臺(tái)機(jī)器上工件的加工順序必然相同。
根據(jù)定理１，我們可以得到以下推論：
推論１ 對(duì)于F2 | Bi = 1 | Cmax問(wèn)題，最優(yōu)調(diào)度必然存在于排列排序中。
推論１表明，當(dāng)存在緩沖區(qū)限制并且上限為１時(shí)，仍然存在基于排列排序的最優(yōu)解。進(jìn)一步，當(dāng)2 ≤ b ≤ +∞時(shí)，我們給出該問(wèn)題的復(fù)雜性分析。
定理２ 具有最大緩沖區(qū)限制的兩階段置換流水車(chē)間調(diào)度問(wèn)題F2 | Bi ≤ b | Cmax是強(qiáng)NP難的（2 ≤ b < +∞）。
不妨設(shè)工件數(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
我們注意到，如果三劃分問(wèn)題有解當(dāng)且僅當(dāng)調(diào)度中各工件之間無(wú)空閑時(shí)間，即C*max = n（b + 3/2）M + （b + 1/2）M為工件分別在M1，M2上的加工時(shí)間之和。
2.１ 工件A最先加工
反證法：若工件A不是第一個(gè)加工，即A在Bi或Ci之后加工，顯然會(huì)使M2上出現(xiàn)空閑，即Cmax > C*max，所以要三劃分問(wèn)題有解，工件A必須第一個(gè)加工。
2.２ 工件D最后加工
反證法：若工件D不是最后加工，有任意的C中的工件Ji在D之后加工，均有：Si2 = max｛C3n，2，Ci，1｝ = max｛C3n，2，C4n，1 + bM｝，因?yàn)镃3n，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上會(huì)產(chǎn)生長(zhǎng)度為M/2的空閑時(shí)間，即Cmax > C*max，所以緊鄰A之后的工件必須是B中的工件。
2.４ 工件集合B中的工件數(shù)為３
因?yàn)镸 / 4 < ci < M / 2，設(shè)工件集合B中的工件數(shù)為n，則nM / 4 < nci < nM / 2，若要滿(mǎn)足調(diào)度中各工件之間無(wú)空閑時(shí)間，只有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ù)是２或者大于３時(shí)也會(huì)產(chǎn)生空閑時(shí)間，使得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上會(huì)出現(xiàn)（t2 - t1）時(shí)間的阻塞。
若緊鄰C之后的工件是C，顯然會(huì)在M1上出現(xiàn)長(zhǎng)度至少為M的空閑。所以緊鄰B之后的工件是C，且B與C交替排列。
設(shè)Ji1、Ji2、Ji3是集合Nk∈N（k = 1，…，n）中的工件，又因?yàn)檎{(diào)度中各工件之間沒(méi)有空閑時(shí)間，因此有下列等式成立：
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
綜上所述，當(dāng)2 ≤ b ≤ +∞時(shí)，三劃分問(wèn)題可以歸約為問(wèn)題F2 | Bi ≤ b | Cmax，因此，具有最大緩沖區(qū)限制的兩階段置換流水車(chē)間調(diào)度問(wèn)題是強(qiáng)NP難的。
由此可知，當(dāng)緩沖區(qū)b = 1時(shí)，滿(mǎn)足排列排序要求的任一工件加工序列均可構(gòu)成可行調(diào)度，而最優(yōu)調(diào)度必存在于排列排序中；當(dāng)b ≥ 2時(shí)，問(wèn)題F2 | Bi ≤ b | Cmax具有強(qiáng)ＮＰ難 的復(fù)雜性，下面將通過(guò)該問(wèn)題與其特例在目標(biāo)函數(shù)方面的分析，考慮其可行解的情況。
?。?目標(biāo)函數(shù)的關(guān)系
具有最大緩沖區(qū)限制的流水車(chē)間調(diào)度問(wèn)題存在以下兩種特例：當(dāng)緩沖區(qū)為零時(shí)，該問(wèn)題轉(zhuǎn)化為阻塞流水車(chē)間調(diào)度問(wèn)題；當(dāng)緩沖區(qū)上限趨于無(wú)窮時(shí)，該問(wèn)題轉(zhuǎn)化為一般流水車(chē)間調(diào)度問(wèn)題。
下面將討論F2 | Bi ≤ b | Cmax與兩階段阻塞流水車(chē)間調(diào)度問(wèn)題和兩階段流水車(chē)間調(diào)度問(wèn)題目標(biāo)函數(shù)之間的關(guān)系。
設(shè)F2 | Bi ≤ b | Cmax的最優(yōu)目標(biāo)值為Cmax（LBFSS），與之相對(duì)應(yīng)的阻塞問(wèn)題最優(yōu)目標(biāo)值為Cmax（BFSS），一般問(wèn)題的最優(yōu)目標(biāo)值為Cmax（FSS），則三者之間存在以下關(guān)系：
定理３ 對(duì)于F2 | Bi ≤ b | Cmax問(wèn)題，存在Cmax（LBFSS） ≥ Cmax（FSS）成立。
證明：設(shè)π為F2 | Bi ≤ b | Cmax的任一可行解，在F2 || Cmax中相應(yīng)的存在一個(gè)π′，與其具有相同的加工順序。在π′中若存在不滿(mǎn)足最大緩沖區(qū)限制約束的工件，則需要將開(kāi)工時(shí)間向右移動(dòng)，以滿(mǎn)足B的要求，如圖２所示。 因而Cmax（π） ≥ Cmax（π′），又因π為F2 | Bi ≤ b | Cmax為問(wèn)題的任一可行解，因此Cmax（LBFSS） ≥ Cmax（FSS）。
定理４ 對(duì)于F2 | Bi ≤ b | Cmax問(wèn)題，存在Cmax（LBFSS） ≤ Cmax（BFSS）成立。
證明：設(shè)π為F2 | BFSS | Cmax的最優(yōu)解，由于阻塞流水車(chē)間不存在緩沖區(qū)，因此對(duì)于在M1上完成加工的工件只能停留在M1上，直到M2上空閑時(shí)才能繼續(xù)加工。與之相對(duì)應(yīng)的問(wèn)題F2 | Bi ≤ b | Cmax，存在解π′，當(dāng)緩沖區(qū)有空閑時(shí)，在M1上完成加工的工件可進(jìn)入緩沖區(qū)等待，在滿(mǎn)足緩沖區(qū)限制的條件下，可以將工件的開(kāi)工時(shí)間適當(dāng)提前，如圖３所示，因此，Cmax（LBFSS） ≤ Cmax（BFSS）。
?。蹋拢疲樱訂?wèn)題的兩個(gè)特例在兩階段的情況下都存在基于排列排序的最優(yōu)啟發(fā)式算法：F2 || Cmax可采用Ｊｏｈｎｓｏｎ規(guī)則，F(xiàn)2 | BFSS | Cmax可采用Ｇｉｌｍｏｒｅ和Ｇｏｍｏｒｙ［12］提出的Ｇｉｌｍｏｒｅ－Ｇｏｍｏｒｙ算法，均可在多項(xiàng)式時(shí)間內(nèi)得到最優(yōu)解。通過(guò)上述定理３和定理４對(duì)F2 | Bi ≤ b | Cmax問(wèn)題上、下界的探討，可以看出，當(dāng)Cmax（FSS） = Cmax（BFSS）時(shí)，F(xiàn)2 | Bi ≤ b | Cmax問(wèn)題的邊界值就是最優(yōu)目標(biāo)值，并可將Ｇｉｌｍｏｒｅ－Ｇｏｍｏｒｙ算法得到的最優(yōu)解作為原問(wèn)題較好的初始解。
?。?結(jié) 論
在許多流程工業(yè)中，都會(huì)出現(xiàn)緩沖區(qū)有限的要求。本文對(duì)緩沖區(qū)有限的兩階段置換流水車(chē)間調(diào)度問(wèn)題的基本性質(zhì)進(jìn)行了研究，得出以下結(jié)論：當(dāng)緩沖區(qū)上限約束比較緊時(shí)，該問(wèn)題存在著基于排列排序的最優(yōu)調(diào)度，當(dāng)緩沖區(qū)b ≥ 2時(shí)，問(wèn)題具有強(qiáng)ＮＰ難的復(fù)雜性，進(jìn)一步通過(guò)對(duì)原問(wèn)題與其特殊情況三者之間在目標(biāo)函數(shù)方面的分析，可知：Cmax（BFSS）和Cmax（FSS）可分別作為原問(wèn)題目標(biāo)函數(shù)值的上界和下界，并且由于F2 || Cmax和F2 | BFSS | Cmax均可在多項(xiàng)式時(shí)間內(nèi)得到最優(yōu)解，因此，原問(wèn)題可利用Ｇｉｌｍｏｒｅ－Ｇｏｍｏｒｙ算法獲得較好的初始調(diào)度。
