常規的流水車間調度問題研究是在假設機器間緩沖區的存儲能力是無限的前提下進行的，而在大量的實際生產加工環境中，由于存儲設備（如存儲罐、中間庫存等）以及生產工藝在空間、時間等方面的限制，緩沖區的存儲能力往往是有限的，例如化工、鋼鐵和制藥等實際生產系統。因而，具有緩沖區限制的流水車間調度問題（Lｉｍｉｔｅｄ－Bｕｆｆｅｒ Ｆｌｏｗｓｈｏｐ Sｃｈｅｄｕｌｉｎｇ Pｒｏｂｌｅｍ， ＬＢＦＳＳＰ）更加符合實際應用背景，對該問題的研究具有重要的理論和實用價值。本文給出了ＬＢＦＳＳＰ問題的一般框架，依據大量的文獻總結了該領域的研究理論和方法并進行了分類，進一步討論了今后的研究方向。
１ ＬＢＦＳＳＰ問題的一般框架
１．１ 問題描述
ＬＢＦＳＳＰ問題可以描述如下：設存在n個工件（1，2，…，n）及m臺機器（1,2，…，m），該n個工件將依次在機器１至m上進行加工；在任一時刻，每個工件最多在一臺機器上加工，且每臺機器最多同時加工一個工件；在每兩臺相鄰的機器j和j - 1之間，存在大小為Bj的緩沖區；工件在每臺機器上的加工順序相同，即所有工件在緩沖區中均服從先入先出規則（ Ｆｉｒｓｔ Ｉｎ Ｆｉｒｓｔ Ｏｕｔ ， ＦＩＦＯ），工序不允許中斷。ＬＢＦＳＳＰ調度問題存在兩種特殊情況：（１） 當緩沖區為零時，該問題轉化成阻塞流水車間問題（ＢＦＳＳ）；（２） 當緩沖區為無窮時，該問題轉化成一般流水車間調度問題（ＦＳＳ）。
１．２ ＬＢＦＳＳＰ調度問題的模型
１．２．１ 一般數學模型
該調度問題通常以加工完成時間最小化為目標，即ｍａｋｅｓｐａｎ Cmax，則數學模型可表示為如下形式：
pij ―― 工件Ji在機器Mj上的加工時間；Sij ―― 工件Ji在機器Mj上的開工時間；Cij ―― 工件Ji在機器Mj上的完工時間；Bi ―― 工件Ji在兩階段間的緩沖區的大小；
min｛Sn，m + pn，m｝
≠ k），j∈J
２ ＬＢＦＳＳＰ問題的研究方法
對有緩沖區約束的流水車間調度問題的研究最早可以追溯到２０世紀７０年代，分別由Ｐｒａｂｈａｋａｒ在１９７４年，Ｄｕｔｔａ和Ｃｕｎｉｎｇｈａｍ在１９７５年提出。Ｄｕｔｔａ和Ｃｕｎｎｉｎｇｈａｍ以及Ｒｅｄｄｉ詳細地描述了有緩沖區約束的兩臺機器的流水車間調度問題的解法，但這一解法只能用于解決規模較小的問題。通過對大量文獻的分析，現有的調度算法以啟發式算法為主，與最優化方法相比較，啟發式算法在調度效果和計算時間之間折中，能夠在較短的時間獲得近優解或最優解。近年來，禁忌搜索算法（ＴＳ）、遺傳算法（ＧＡ）等都得到了廣泛的應用。
Ｐａｐａｄｉｍｉｔｒｉｏｕ和Ｋａｎｅｌｌａｋｉｓ在１９８０年證明了有緩沖區限制的兩階段流水車間調度問題是ＮＰ完全問題，并給出了有緩沖區限制的兩階段流水車間調度與兩階段無等待流水車間調度ｍａｋｅｓｐａｎ之間的關系： = 2b + 1 / b + 1。通過進一步研究當buffer = 1的情況，證明了與無緩沖區流水車間相比，完工時間可以減少１／３；同時證明了當m ≥ 4且緩沖區為零時，該問題是ＮＰ完全的。Ｇｕｐｔａ在１９８８年針對多階段的混合流水車間得到了相似的結論。在２０世紀９０年代，Ｉｎｄｅｒ Ｋｈｏｓｌａ研究了兩階段混合流水車間問題，其中第一階段多機并行，第二階段只有一臺機器，兩階段間存在一個有限緩沖區。作者針對該問題建立了一個混合整數線性規劃模型，以最小化加權完工時間為目標函數，利用拉格朗日及拉格朗日松弛算法給出了問題的下界，并提出了基于優先準則的啟發式算法。
Ｌｅｉｓｔｅｎ研究了目標函數為最小化ｍａｋｅｓｐａｎ的流水車間，將ＮＥＨ等啟發式算法分別應用在無緩沖區、無限緩沖區及有限緩沖區3種不同的情況，并進行了系統地分析。實驗結果表明：對于有限緩沖區的置換流水車間，Ｎａｗａｚ，ｅｔ ａｌ．提出的ＮＥＨ算法是最好的啟發式算法之一。Ａ．Ｂｅｎｌｏｇａｂ則基于對平均工作流和調度過程甘特圖的分析，提出了一種新的啟發式算法。Ｐａｃｃｉａｒｅｌｌｉ等在１９９７年研究了有緩沖區限制的兩階段批處理流水車間調度問題，證明了該問題是ＮＰ難的，并提出當批生產數量大于緩沖區限制時，目標函數為最小化ｍａｋｅｓｐａｎ的該問題將轉化為可用多項式時間解決的ＴＳＰ問題。
２．１ 鄰域搜索算法
鄰域搜索算法在ＬＢＦＳＳＰ問題中得到了廣泛的應用，主要集中在禁忌搜索算法、遺傳算法等。
2.1.1 禁忌搜索算法
ＴＳ 是Ｇｌｏｖｅｒ提出的模擬智能過程的一種具有記憶功能的全局逐步優化算法，對變動的排序在其可行解的所有空間中進行搜尋，通過設置禁忌表，避免陷入局部最優或重復過去的搜索，利用中、長期的存儲機制進行強化和多樣化搜索。
ＣｚｅｓＩａｗ在文獻［15］中針對兩階段的具有緩沖區限制的置換流水車間調度問題，提出了一種近似算法，該算法在禁忌搜索算法的基礎上減少了被搜索的鄰域，增加了在搜索軌跡上回跳的技術，提高了搜索的速度。對ＬＢＦＳＳ問題，Ｎｏｗｉｃｋｉ利用了問題中的結構性質，結合了局部搜索和禁忌搜索策略，提出了一種在流水車間中常用的消除阻塞的方法，這些性質應用在分支限界算法以及以局部搜索為基礎的近似算法中，尤其是在禁忌搜索算法中得到應用。Ｂｒｕｃｋｅｒ，ｅｔ ａｌ． 擴展了Ｎｏｗｉｃｋｉ的想法，研究了不同加工順序的情況，并在禁忌搜索算法的鄰域構造中結合了塊搜索方法。Ｎｏｒｍａｎ提出了一種禁忌搜索算法，用以解決帶有啟動時間和有限緩沖區的置換流水車間。由于禁忌搜索算法在計算緩沖區的大小與給定的作業排序是否相適應時所需要的時間較長，因此Ｗａｒｄｏｎｏ和 Ｆａｔｈｉ在研究多階段并行置換流水車間時，在第l階段利用矩陣（ I X）來表示解，這樣可以覆蓋整個解空間，并加快搜索速度。
2.1.２ 遺傳算法
文獻［20］提出了一種多搜索模式遺傳算法，算法使用多個交叉和變異操作進行解空間的探索和改良，并采用基于有向圖的鄰域結構來增強局部搜索。文獻［21］提出了一種混合遺傳算法，同時考慮了多階段的遺傳操作和基于模型的鄰域結構。文獻［22］針對多級并行機問題設計了一種基于遺傳算法和模擬退火算法的混合求解算法，該算法采用混合交叉算子和變異算子的策略對選擇算子進行了設計。
２．２ 其他理論和技術
近年來，一些新的算法被應用在這一研究領域。文獻［23］針對隨機有限緩沖區流水線調度問題提出了混合差分進化算法，其中差分進化用于執行全局搜索和局部搜索，最優計算量分配用于對有限計算量進行合理分配，從而保證優質解得到較多仿真計算量，并提高了在噪聲環境下獲得優質解的置信度。文獻［24］針對有限緩沖區流水線問題建立了數學模型，并利用文化算法和免疫算法相結合的混合進化算法對其進行求解，算法中將免疫算法納入文化算法的框架，組成基于免疫算法的群體空間和信念空間，兩空間具有各自群體并獨立并行演化。文獻［25］提出了一種混合蟻群算法用以解決有緩沖區限制的置換流水車間調度問題。
部分學者還研究了混合存儲策略。文獻［26］研究了含有混合中間存儲策略的模糊流水車間調度方法，考慮了無限中間產品存儲、有限中間產品存儲、無中間產品存儲3種策略同時存在的情況下對調度問題的影響，提出了一種基于模糊時間的含有混合中間存儲策略的流水車間調度模型，應用雙倍體遺傳算法對該問題進行優化求解。文獻［27］將緩沖區的4種情況（無等待、無緩沖區、有限緩沖區、無限緩沖區）在一個流水車間中進行考慮，分析這4種情況共存的結構優勢，通過借鑒ＮＥＨ算法，提出了一種用以解決ＣＢＦＳＳ問題的名為Ｌｉｕ�Ｋｏｚａｎ�ＢＩＨ的兩階段混合啟發式算法。
３ 對合理設置緩沖區的研究
在生產過程中，添加緩沖區是為了避免因工件無處暫放而滯留在設備上，造成加工過程的阻塞。但是，緩沖區域過大會浪費企業的資源，增大加工成本。鄭大鐘等［28］對串行生產線提出了比較完善的緩沖器的設置理論和方法，討論了有限緩沖器容量的串行生產線的狀態變化的數學依據。這種理論和方法是在消除阻塞的前提下調節緩沖器的大小，使加工過程不停機同時占用的緩沖器資源最少。但是，加工車間的緩沖器就是設備旁邊的區域，其面積不能隨意更改，即使自動化的生產線也不能隨便增減緩沖器的大小。因此，國內外的研究方向大都集中在如何合理設置緩沖區的大小上。文獻［29-31］研究了有限緩沖區的流水車間調度問題，并進一步指出，緩沖區的大小影響著生產車間的績效，但是績效會隨著緩沖區規模的增加而迅速的下降。文獻［32］指出最小化緩沖區是ＮＰ完全問題。文獻［33］研究了每階段之間具有相同大小緩沖區的流水車間調度問題，并用ＮＥＨ算法得到初始調度，再利用禁忌搜索進行改進。文獻［17］針對流水車間給出了與緩沖區大小相適應的可行調度的個數，并在此基礎上提出了一種禁忌搜索算法，且通過實驗證明了緩沖區的大小對算法的影響。
４ 存儲時間有限型緩沖區
與緩沖區空間受限相對應的是存儲時間受限的緩沖區。實際上，在化工生產過程中，每一道生產工序產品的處理時間、設備清洗時間、原材料或者中間產品的裝載時間等會使得處理時間不確定或產品存儲時間有限。由于某些產品在加工過程中存在不穩定性，所以在儲罐內進行存儲的時間達到某一有限值時，必須進入下一單元進行加工；如果下一單元正在加工產品，則必須考慮到延遲產品的開始加工時間。文獻［34］研究了具有優先約束及緩沖區約束的兩臺機器流水車間調度問題。區別于以往對緩沖區的研究，文獻中緩沖區的約束是指對處理時間的限制。該文獻證明了此問題是強ＮＰ難的，并進一步利用改進的分支限界算法和ＮＥＨ算法，給出了問題的4個下界和1個上界。文獻［35］基于模糊規劃理論，建立了有限型存儲時間的Ｆｌｏｗ Ｓｈｏｐ 調度模型，并結合改進模擬退火方法進行優化求解。文獻［25］針對該問題提出了一種混合粒子群算法，首先在一種新編碼方案的基礎上開發了隨機密鑰，然后以ＮＥＨ算法為基礎獲得具有一定質量和多樣性的初始種群，并設計了消除阻塞的局部搜索策略。
５ 問題討論與展望
具有緩沖區限制的流水車間廣泛存在，對其調度問題的研究具有重要的理論和實際意義，從上面的綜述可以看出：
（１） 現有算法中較少應用最優化算法，盡管啟發式算法存在著計算時間方面的優勢，但也存在著缺點：有時近優解不能令人滿意，與實際應用還相距較遠。因此，對混合算法的研究成為了一種趨勢。
（２） 緩沖區的大小對目標函數及算法的設計存在著很大的影響，目前大部分結論都是通過實驗數據得到的，缺乏更多的理論基礎，如何合理設置緩沖區需要進一步的研究。
（３） 在實際生產中，由于機器故障、緊急訂單等原因，使得生產處于動態環境中。因此，如何在系統受到擾動后，盡快重新安排生產，顯得尤為重要。
