０ 引 言
傳統的流水車間調度模型通常假定各機器間的緩沖區無窮大，然而在許多實際生產過程中，由于受到緩沖區空間或存儲設備的限制（如中間庫存等），緩沖區的大小是有限的。緩沖區有限的流水車間調度問題（ＬＢＦＳＳ）廣泛存在于鋼鐵、化工、制藥等帶有中間存儲環節的生產系統中［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均可在多項式時間內得到最優解，因此，原問題可利用Ｇｉｌｍｏｒｅ－Ｇｏｍｏｒｙ算法獲得較好的初始調度。
