具有緩沖區(qū)約束的流水車間調度問題綜述

于艷輝 侯東亮

［摘要］ 首先介紹了具有緩沖區(qū)約束的流水車間調度問題的一般框架、算法及其分類，主要針對啟發(fā)式算法進行分析和總結，并進一步介紹了如何合理設置緩沖區(qū)以及存儲時間有限的情況，最后，探討了在此研究領域中的未來發(fā)展趨勢。

［關鍵詞］ 流水車間； 緩沖區(qū)限制； 啟發(fā)式； 存儲時間有限

doi : 10 . 3969 / j . issn . 1673 - 0194 . 2012 . 06. 029

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

常規(guī)的流水車間調度問題研究是在假設機器間緩沖區(qū)的存儲能力是無限的前提下進行的，而在大量的實際生產加工環(huán)境中，由于存儲設備（如存儲罐、中間庫存等）以及生產工藝在空間、時間等方面的限制，緩沖區(qū)的存儲能力往往是有限的，例如化工、鋼鐵和制藥等實際生產系統(tǒng)。因而，具有緩沖區(qū)限制的流水車間調度問題（Lｉｍｉｔｅｄ－Bｕｆｆｅｒ Ｆｌｏｗｓｈｏｐ Sｃｈｅｄｕｌｉｎｇ Pｒｏｂｌｅｍ， ＬＢＦＳＳＰ）更加符合實際應用背景，對該問題的研究具有重要的理論和實用價值。本文給出了ＬＢＦＳＳＰ問題的一般框架，依據大量的文獻總結了該領域的研究理論和方法并進行了分類，進一步討論了今后的研究方向。

１ＬＢＦＳＳＰ問題的一般框架

１．１問題描述

ＬＢＦＳＳＰ問題可以描述如下：設存在n個工件（1，2，…，n）及m臺機器（1,2，…，m），該n個工件將依次在機器１至m上進行加工；在任一時刻，每個工件最多在一臺機器上加工，且每臺機器最多同時加工一個工件；在每兩臺相鄰的機器j和j - 1之間，存在大小為Bj的緩沖區(qū)；工件在每臺機器上的加工順序相同，即所有工件在緩沖區(qū)中均服從先入先出規(guī)則（ Ｆｉｒｓｔ Ｉｎ Ｆｉｒｓｔ Ｏｕｔ ， ＦＩＦＯ），工序不允許中斷。ＬＢＦＳＳＰ調度問題存在兩種特殊情況：（１） 當緩沖區(qū)為零時，該問題轉化成阻塞流水車間問題（ＢＦＳＳ）；（２） 當緩沖區(qū)為無窮時，該問題轉化成一般流水車間調度問題（ＦＳＳ）。

１．２ＬＢＦＳＳＰ調度問題的模型

１．２．１一般數學模型

該調度問題通常以加工完成時間最小化為目標，即ｍａｋｅｓｐａｎ Cmax，則數學模型可表示為如下形式：

pij —— 工件Ji在機器Mj上的加工時間；Sij —— 工件Ji在機器Mj上的開工時間；Cij —— 工件Ji在機器Mj上的完工時間；Bi —— 工件Ji在兩階段間的緩沖區(qū)的大小；

min｛Sn，m + pn，m｝

≠ k），j∈J

２ＬＢＦＳＳＰ問題的研究方法

對有緩沖區(qū)約束的流水車間調度問題的研究最早可以追溯到２０世紀７０年代，分別由Ｐｒａｂｈａｋａｒ在１９７４年，Ｄｕｔｔａ和Ｃｕｎｉｎｇｈａｍ在１９７５年提出。Ｄｕｔｔａ和Ｃｕｎｎｉｎｇｈａｍ以及Ｒｅｄｄｉ詳細地描述了有緩沖區(qū)約束的兩臺機器的流水車間調度問題的解法，但這一解法只能用于解決規(guī)模較小的問題。通過對大量文獻的分析，現(xiàn)有的調度算法以啟發(fā)式算法為主，與最優(yōu)化方法相比較，啟發(fā)式算法在調度效果和計算時間之間折中，能夠在較短的時間獲得近優(yōu)解或最優(yōu)解。近年來，禁忌搜索算法（ＴＳ）、遺傳算法（ＧＡ）等都得到了廣泛的應用。

Ｐａｐａｄｉｍｉｔｒｉｏｕ和Ｋａｎｅｌｌａｋｉｓ在１９８０年證明了有緩沖區(qū)限制的兩階段流水車間調度問題是ＮＰ完全問題，并給出了有緩沖區(qū)限制的兩階段流水車間調度與兩階段無等待流水車間調度ｍａｋｅｓｐａｎ之間的關系： = 2b + 1 / b + 1。通過進一步研究當buffer = 1的情況，證明了與無緩沖區(qū)流水車間相比，完工時間可以減少１／３；同時證明了當m ≥ 4且緩沖區(qū)為零時，該問題是ＮＰ完全的。Ｇｕｐｔａ在１９８８年針對多階段的混合流水車間得到了相似的結論。在２０世紀９０年代，Ｉｎｄｅｒ Ｋｈｏｓｌａ研究了兩階段混合流水車間問題，其中第一階段多機并行，第二階段只有一臺機器，兩階段間存在一個有限緩沖區(qū)。作者針對該問題建立了一個混合整數線性規(guī)劃模型，以最小化加權完工時間為目標函數，利用拉格朗日及拉格朗日松弛算法給出了問題的下界，并提出了基于優(yōu)先準則的啟發(fā)式算法。

Ｌｅｉｓｔｅｎ研究了目標函數為最小化ｍａｋｅｓｐａｎ的流水車間，將ＮＥＨ等啟發(fā)式算法分別應用在無緩沖區(qū)、無限緩沖區(qū)及有限緩沖區(qū)3種不同的情況，并進行了系統(tǒng)地分析。實驗結果表明：對于有限緩沖區(qū)的置換流水車間，Ｎａｗａｚ，ｅｔ ａｌ．提出的ＮＥＨ算法是最好的啟發(fā)式算法之一。Ａ．Ｂｅｎｌｏｇａｂ則基于對平均工作流和調度過程甘特圖的分析，提出了一種新的啟發(fā)式算法。Ｐａｃｃｉａｒｅｌｌｉ等在１９９７年研究了有緩沖區(qū)限制的兩階段批處理流水車間調度問題，證明了該問題是ＮＰ難的，并提出當批生產數量大于緩沖區(qū)限制時，目標函數為最小化ｍａｋｅｓｐａｎ的該問題將轉化為可用多項式時間解決的ＴＳＰ問題。

２．１鄰域搜索算法

鄰域搜索算法在ＬＢＦＳＳＰ問題中得到了廣泛的應用，主要集中在禁忌搜索算法、遺傳算法等。

2.1.1禁忌搜索算法

ＴＳ 是Ｇｌｏｖｅｒ提出的模擬智能過程的一種具有記憶功能的全局逐步優(yōu)化算法，對變動的排序在其可行解的所有空間中進行搜尋，通過設置禁忌表，避免陷入局部最優(yōu)或重復過去的搜索，利用中、長期的存儲機制進行強化和多樣化搜索。

ＣｚｅｓＩａｗ在文獻［15］中針對兩階段的具有緩沖區(qū)限制的置換流水車間調度問題，提出了一種近似算法，該算法在禁忌搜索算法的基礎上減少了被搜索的鄰域，增加了在搜索軌跡上回跳的技術，提高了搜索的速度。對ＬＢＦＳＳ問題，Ｎｏｗｉｃｋｉ利用了問題中的結構性質，結合了局部搜索和禁忌搜索策略，提出了一種在流水車間中常用的消除阻塞的方法，這些性質應用在分支限界算法以及以局部搜索為基礎的近似算法中，尤其是在禁忌搜索算法中得到應用。Ｂｒｕｃｋｅｒ，ｅｔ ａｌ． 擴展了Ｎｏｗｉｃｋｉ的想法，研究了不同加工順序的情況，并在禁忌搜索算法的鄰域構造中結合了塊搜索方法。Ｎｏｒｍａｎ提出了一種禁忌搜索算法，用以解決帶有啟動時間和有限緩沖區(qū)的置換流水車間。由于禁忌搜索算法在計算緩沖區(qū)的大小與給定的作業(yè)排序是否相適應時所需要的時間較長，因此Ｗａｒｄｏｎｏ和 Ｆａｔｈｉ在研究多階段并行置換流水車間時，在第l階段利用矩陣（ I X）來表示解，這樣可以覆蓋整個解空間，并加快搜索速度。

2.1.２遺傳算法

文獻［20］提出了一種多搜索模式遺傳算法，算法使用多個交叉和變異操作進行解空間的探索和改良，并采用基于有向圖的鄰域結構來增強局部搜索。文獻［21］提出了一種混合遺傳算法，同時考慮了多階段的遺傳操作和基于模型的鄰域結構。文獻［22］針對多級并行機問題設計了一種基于遺傳算法和模擬退火算法的混合求解算法，該算法采用混合交叉算子和變異算子的策略對選擇算子進行了設計。

２．２其他理論和技術

近年來，一些新的算法被應用在這一研究領域。文獻［23］針對隨機有限緩沖區(qū)流水線調度問題提出了混合差分進化算法，其中差分進化用于執(zhí)行全局搜索和局部搜索，最優(yōu)計算量分配用于對有限計算量進行合理分配，從而保證優(yōu)質解得到較多仿真計算量，并提高了在噪聲環(huán)境下獲得優(yōu)質解的置信度。文獻［24］針對有限緩沖區(qū)流水線問題建立了數學模型，并利用文化算法和免疫算法相結合的混合進化算法對其進行求解，算法中將免疫算法納入文化算法的框架，組成基于免疫算法的群體空間和信念空間，兩空間具有各自群體并獨立并行演化。文獻［25］提出了一種混合蟻群算法用以解決有緩沖區(qū)限制的置換流水車間調度問題。

部分學者還研究了混合存儲策略。文獻［26］研究了含有混合中間存儲策略的模糊流水車間調度方法，考慮了無限中間產品存儲、有限中間產品存儲、無中間產品存儲3種策略同時存在的情況下對調度問題的影響，提出了一種基于模糊時間的含有混合中間存儲策略的流水車間調度模型，應用雙倍體遺傳算法對該問題進行優(yōu)化求解。文獻［27］將緩沖區(qū)的4種情況（無等待、無緩沖區(qū)、有限緩沖區(qū)、無限緩沖區(qū)）在一個流水車間中進行考慮，分析這4種情況共存的結構優(yōu)勢，通過借鑒ＮＥＨ算法，提出了一種用以解決ＣＢＦＳＳ問題的名為Ｌｉｕ–Ｋｏｚａｎ–ＢＩＨ的兩階段混合啟發(fā)式算法。

３對合理設置緩沖區(qū)的研究

在生產過程中，添加緩沖區(qū)是為了避免因工件無處暫放而滯留在設備上，造成加工過程的阻塞。但是，緩沖區(qū)域過大會浪費企業(yè)的資源，增大加工成本。鄭大鐘等［28］對串行生產線提出了比較完善的緩沖器的設置理論和方法，討論了有限緩沖器容量的串行生產線的狀態(tài)變化的數學依據。這種理論和方法是在消除阻塞的前提下調節(jié)緩沖器的大小，使加工過程不停機同時占用的緩沖器資源最少。但是，加工車間的緩沖器就是設備旁邊的區(qū)域，其面積不能隨意更改，即使自動化的生產線也不能隨便增減緩沖器的大小。因此，國內外的研究方向大都集中在如何合理設置緩沖區(qū)的大小上。文獻［29-31］研究了有限緩沖區(qū)的流水車間調度問題，并進一步指出，緩沖區(qū)的大小影響著生產車間的績效，但是績效會隨著緩沖區(qū)規(guī)模的增加而迅速的下降。文獻［32］指出最小化緩沖區(qū)是ＮＰ完全問題。文獻［33］研究了每階段之間具有相同大小緩沖區(qū)的流水車間調度問題，并用ＮＥＨ算法得到初始調度，再利用禁忌搜索進行改進。文獻［17］針對流水車間給出了與緩沖區(qū)大小相適應的可行調度的個數，并在此基礎上提出了一種禁忌搜索算法，且通過實驗證明了緩沖區(qū)的大小對算法的影響。

４存儲時間有限型緩沖區(qū)

與緩沖區(qū)空間受限相對應的是存儲時間受限的緩沖區(qū)。實際上，在化工生產過程中，每一道生產工序產品的處理時間、設備清洗時間、原材料或者中間產品的裝載時間等會使得處理時間不確定或產品存儲時間有限。由于某些產品在加工過程中存在不穩(wěn)定性，所以在儲罐內進行存儲的時間達到某一有限值時，必須進入下一單元進行加工；如果下一單元正在加工產品，則必須考慮到延遲產品的開始加工時間。文獻［34］研究了具有優(yōu)先約束及緩沖區(qū)約束的兩臺機器流水車間調度問題。區(qū)別于以往對緩沖區(qū)的研究，文獻中緩沖區(qū)的約束是指對處理時間的限制。該文獻證明了此問題是強ＮＰ難的，并進一步利用改進的分支限界算法和ＮＥＨ算法，給出了問題的4個下界和1個上界。文獻［35］基于模糊規(guī)劃理論，建立了有限型存儲時間的Ｆｌｏｗ Ｓｈｏｐ 調度模型，并結合改進模擬退火方法進行優(yōu)化求解。文獻［25］針對該問題提出了一種混合粒子群算法，首先在一種新編碼方案的基礎上開發(fā)了隨機密鑰，然后以ＮＥＨ算法為基礎獲得具有一定質量和多樣性的初始種群，并設計了消除阻塞的局部搜索策略。

５問題討論與展望

具有緩沖區(qū)限制的流水車間廣泛存在，對其調度問題的研究具有重要的理論和實際意義，從上面的綜述可以看出：

（１） 現(xiàn)有算法中較少應用最優(yōu)化算法，盡管啟發(fā)式算法存在著計算時間方面的優(yōu)勢，但也存在著缺點：有時近優(yōu)解不能令人滿意，與實際應用還相距較遠。因此，對混合算法的研究成為了一種趨勢。

（２） 緩沖區(qū)的大小對目標函數及算法的設計存在著很大的影響，目前大部分結論都是通過實驗數據得到的，缺乏更多的理論基礎，如何合理設置緩沖區(qū)需要進一步的研究。

（３） 在實際生產中，由于機器故障、緊急訂單等原因，使得生產處于動態(tài)環(huán)境中。因此，如何在系統(tǒng)受到擾動后，盡快重新安排生產，顯得尤為重要。

主要參考文獻

［１］ Ｓｍｕｔｎｉｃｋｉ Ｃ． Ｂｌｏｃｋ Aｐｐｒｏａｃｈ ｆｏｒ Flｏｗ－Sｈｏｐ Sｃｈｅｄｕｌｉｎｇ ｗｉｔｈ Sｔｏｒａｇｅ Cｏｎｓｔｒａｉｎｔｓ［J］． Ｚｅｓｚｙｔｙ Ｎａｕｋｏｗｅ Ｐｏｌｉｔｅｃｈｎｉｋｉ Ｓｌａｓｋｉｅｊ Ｓｅｒ Ａｕｔｏｍａｔｙｋａ，１９８６，８４（２）：２３-３３．

［2］ Ｓｍｕｔｎｉｃｋｉ Ｃ．Ａ Tｗｏ－Mａｃｈｉｎｅ Pｅｒｍｕｔａｔｉｏｎ Flｏｗ－Sｈｏｐ Sｃｈｅｄｕｌｉｎｇ ｗｉｔｈ Bｕｆｆｅｒｓ［J］． ＯＲ Ｓｐｅｃｔｒｕｍ，１９９８，２０（4）：2２９-2３５．

［3］ Ｎｏｗｉｃｋｉ Ｅ． Ｔｈｅ Pｅｒｍｕｔａｔｉｏｎ FlｏｗSｈｏｐ ｗｉｔｈ Bｕｆｆｅｒｓ：A Tａｂｕ Sｅａｒｃｈ Aｐｐｒｏａｃｈ［J］． Ｅｕｒｏｐｅａｎ Ｊｏｕｒｎａｌ ｏｆ Ｏｐｅｒａｔｉｏｎａｌ Ｒｅｓｅａｒｃｈ，１９９９，１１６（２０）：５-１９．

［4］ Ｓhaohua LI， Ｌixin ＴＡＮＧ． Ａ Tａｂｕ Sｅａｒｃｈ Aｌｇｏｒｉｔｈｍ Bａｓｅｄ ｏｎ Nｅｗ Bｌｏｃｋ Pｒｏｐｅｒｔｉｅｓ ａｎｄ Sｐｅｅｄ－ｕｐ Mｅｔｈｏｄ ｆｏｒ Pｅｒｍｕｔａｔｉｏｎ Flｏｗ－Sｈｏｐ ｗｉｔｈ Fiｎｉｔｅ Iｎｔｅｒｍｅｄｉａｔｅ Sｔｏｒａｇｅ［J］． Ｊｏｕｒｎａｌ ｏｆ Ｉｎｔｅｌｌｉｇｅｎｔ Ｍａｎｕｆａｃｔｕｒｉｎｇ，２００５，１６（4/5）：４６３-４７７．

［5］ Ｄｕｔｔａ Ｓ Ｋ， Ｃｕｎｎｉｎｇｈａｍ Ａ Ａ． Ｓｅｑｕｅｎｃｉｎｇ Tｗｏ－Mａｃｈｉｎｅ Flｏｗ－Sｈｏｐｓ ｗｉｔｈ Fiｎｉｔｅ Iｎｔｅｒｍｅｄｉａｔｅ Sｔｏｒａｇｅ［J］． Ｍａｎａｇｅｍｅｎｔ Ｓｃｉｅｎｃｅ， １９７５， ２１（９）：9８９-99６．

［6］ Ｒｅｄｄｉ Ｓ Ｓ． Note——Ｓｅｑｕｅｎｃｉｎｇ ｗｉｔｈ Fiｎｉｔｅ Iｎｔｅｒｍｅｄｉａｔｅ Sｔｏｒａｇｅ［J］． Ｍａｎａｇｅｍｅｎｔ Ｓｃｉｅｎｃｅ，１９７６， ２３（2）：２１６-21７．

［7］ Ｐａｐａｄｉｍｉｔｒｉｏｕ Ｃ Ｈ， Ｋａｎｅｌｌａｋｉｓ Ｐ Ｃ． Ｆｌｏｗ Sｈｏｐ Sｃｈｅｄｕｌｉｎｇ ｗｉｔｈ Lｉｍｉｔｅｄ Tｅｍｐｏｒａｒｙ Sｔｏｒａｇｅ［J］． Ｊｏｕｒｎａｌ ｏｆ Asｓｏｃｉａｔｉｏｎ ｏｆ Ｃｏｍｐｕｔｉｎｇ Ｍａｃｈｉｎｅｒｙ， １９８０， ２７（3）．

［8］ Ｇｕｐｔａ Ｊ Ｎ Ｄ． Ｔｗｏ－Sｔａgｅ， Hｙｂｒｉｄ Flｏｗｓｈｏｐ Sｃｈｅｄｕｌｉｎｇ Pｒｏｂｌｅｍ［J］． Ｊｏｕｒｎａｌ ｏｆ ｔｈｅ Ｏｐｅｒａｔｉｏｎａｌ Ｒｅｓｅａｒｃｈ Ｓｏｃｉｅｔｙ， １９８８，３９（4）：３５９-３６４．

［9］ Ｉｎｄｅｒ Ｋｈｏｌｓａ． Ｔｈｅ Sｃｈｅｄｕｌｉｎｇ Pｒｏｂｌｅｍ Wｈｅｒｅ Mｕｌｔｉｐｌｅ Mａｃｈｉｎｅｓ Cｏｍｐｅｔｅ ｆｏｒ ａ Cｏｍｍｏｎ Lｏｃａｌ Bｕｆｆｅｒ［J］． Ｅｕｒｏｐｅａｎ Ｊｏｕｒｎａｌ ｏｆ Ｏｐｅｒａｔｉｏｎａｌ Rｅｓｅａｒｃｈ， １９９５，８４（2）：３３０－３４２．

［10］ Ｌｅｉｓｔｅｎ Ｒ． Ｆｌｏｗ Sｈｏｐ Sｅｑｕｅｎｃｉｎｇ Pｒｏｂｌｅｍｓ ｗｉｔｈ Lｉｍｉｔｅｄ Bｕｆｆｅｒ Sｔｏｒａｇｅ［J］． Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｊｏｕｒｎａｌ ｏｆ Ｐｒｏｄｕｃｔｉｏｎ Ｒｅｓｅａｒｃｈ，１９９０，２８（11）： 20８５-2１００．

［１1］ Ｎａｗａｚ Ｍ，Ｅｎｓｃｏｒｅ Ｅ，Ｈａｍ Ｉ． Ａ Hｅｕｒｉｓｔｉｃ Aｌｇｏｒｉｔｈｍ ｆｏｒ ｔｈｅ ｍ－Mａｃｈｉｎｅ，ｎ－Jｏｂ Flｏｗ－ｓｈｏｐ Sｅｑｕｅｎｃｉｎｇ Pｒｏｂｌｅｍ［J］．Ｏｍｅｇａ， １９８３，１１（1）：9１-9５．

［１2］ Ａ Ｂｅｎｌｏｇａｂ， Ｂ Ｄｅｓｃｏｔｅｓ． Sequencｉｎｇ Fｌｏｗ Sｈｏｐｓ ｗｉｔｈ Aｒｂｉｔｒａｒｙ Iｎｔｅｒｍｅｄｉａｔｅ Sｔｏｒａｇｅ［C］． Proceedings of IEEE Ｉｎｔｅｒ－ｎａｔｉｏｎａｌ Ｓｙｍｐｏｓｌｕｍ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｃｏｎｔｒｏｌ，１９９４，１9６－200．

［13］ Ａ Ａｇｎｅｔｉｓ， Ｄ Ｐａｃｃｉａｒｅｌｌｉ， Ｆ Ｒｏｓｓｉ． Ｂａｔｃｈ Sｃｈｅｄｕｌｉｎｇ ｉｎ ａ Tｗｏ－Mａｃｈｉｎｅ Fｌｏｗ Sｈｏｐ ｗｉｔｈ Lｉｍｉｔｅｄ Bｕｆｆｅｒ［J］． Ｄｉｓｃｒｅｔｅ Ａｐｐｌｉｅｄ Ｍａｔｈｅｍａｔｉｃｓ， １９９７，７２（3）：２４３－２６０．

［１4］ Ｇｌｏｖｅｒ Ｆ． Ｔａｂｕ Sｅａｒｃｈ Ｐａｒｔ Ⅰ［Ｊ］． ＯＲＳＡ Ｊｏｕｒｎａｌ ｏｎ Ｃｏｍｐｕｔｉｎｇ，１９８９， １（３）：１９０－２０６ ．

［１5］ ＣｚｅｓＩａｗ Ｓｍｕｔｎｉｃｋｉ． Ａ Tｗｏ－Mａｃｈｉｎｅ Pｅｒｍｕｔａｔｉｏｎ Fｌｏｗ Sｈｏｐ Sｃｈｅｄｕｌｉｎｇ Pｒｏｂｌｅｍ ｗｉｔｈ Bｕｆｆｅｒｓ［J］． ＯＲ Ｓｐｅｋｔｒｕｍ，１９９８，２０（4）：２２９－２３５．

［１6］ Ｎｏｗｉｃｋｉ Ｅ． Ｔｈｅ Pｅｒｍｕｔａｔｉｏｎ Flｏｗ Sｈｏｐ ｗｉｔｈ Bｕｆｆｅｒｓ： A Tａｂｕ Sｅａｒｃｈ Aｐｐｒｏａｃｈ［J］． Ｅｕｒｏｐｅａｎ Ｊｏｕｒｎａｌ ｏｆ Ｏｐｅｒａｔｉｏｎａｌ Ｒｅｓｅａｒｃｈ， １９９９，１１６（1）：２０５-2１９．

［１7］ Ｂｒｕｃｋｅｒ Ｐ， Ｈｅｉｔｍａｎｎ Ｓ， Ｈｕｒｉｎｋ Ｊ． Ｆｌｏｗ－Sｈｏｐ Pｒｏｂｌｅｍｓ ｗｉｔｈ Iｎｔｅｒｍｅｄｉａｔｅ Bｕｆｆｅｒｓ［J］． ＯＲ Ｓｐｅｃｔｒｕｍ，２００３，２５（４）：５４9-5７４．

［１8］ Ｎｏｒｍａｎ Ｂ Ａ． Ｓｃｈｅｄｕｌｉｎｇ Flｏｗ Sｈｏｐｓ ｗｉｔｈ Fiｎｉｔｅ Bｕｆｆｅｒｓ ａｎｄ Sｅｑｕｅｎｃｅ－Dｅｐｅｎｄｅｎｔ Sｅｔｕp Tｉｍｅｓ［J］． Ｃｏｍｐｕｔｅｒｓ ａｎｄ Ｉｎｄｕｓｔｒｉａｌ Ｅｎｇｉｎｅｅｒｉｎｇ， １９９９，３６（１）：1６３-1７７．

［１9］ Ｗａｒｄｏｎｏ Ｂ， Ｆａｔｈｉ Ｙ． Ａ Tａｂｕ Sｅａｒｃｈ Aｌｇｏｒｉｔｈｍ ｆｏｒ ｔｈｅ Mｕｌｔｉ－Sｔａｇe Pａｒａｌｌｅｌ Mａｃｈｉｎｅ Pｒｏｂｌｅｍ ｗｉｔｈ Lｉｍｉｔｅｄ Bｕｆｆｅｒ Cａｐａｃｉｔｉｅｓ［J］． Ｅｕｒｏｐｅａｎ Ｊｏｕｒｎａｌ ｏｆ Ｏｐｅｒａｔｉｏｎａｌ Ｒｅｓｅａｒｃｈ， ２００４；１５５（２）：３８０-４０１．

［20］ 王凌，張亮． 有限緩沖區(qū)流水線調度的多搜索模式遺傳算法［J］． 計算機集成制造系統(tǒng)，２００５，１１（７）：１０４１－ １０４６．

［2１］ Ｗａｎｇ Ｌ， Ｚｈａｎｇ Ｌ， Ｚｈｅｎｇ Ｄ Ｚ． Ａｎ Eｆｆｅｃｔｉｖｅ Hｙｂｒｉｄ Gｅｎｅｔｉｃａｌ Gｏｒｉｔｈｍ Fｏｒ Flｏｗ Sｈｏｐ Sｃｈｅｄｕｌｉｎｇ ｗｉｔｈ Lｉｍｉｔｅｄ Bｕｆｆｅｒｓ［J］． Ｃｏｍｐｕｔｅｒ ａｎｄ Ｏｐｅｒａｔｉｏｎｓ Ｒｅｓｅａｒｃｈ， ２００６，３３（10）：２９６０-29７１．

［22］ 王炳剛，饒運清，等． 帶有限中間緩沖區(qū)的多級并行機問題的求解［J］． 華中科技大學學報：自然科學版，２００９，３７（５）：８６－８９．

［23］ 胡蓉，錢斌． 一種求解隨機有限緩沖區(qū)流水線調度的混合差分進化算法［J］． 自動化學報， ２００９，３５（１２）：１５８０－１５８６．

［24］ 曹俊杰，侍洪波． 基于混合進化算法的有限緩沖區(qū)流水線調度［J］． 中南大學學報：自然科學版， ２００９（z1）．

［25］ Ｂｏ Ｌｉｕ， Ｌｉｎｇ Ｗａｎｇ， Ｙｉ－Ｈｕｉ Ｊｉｎ． Ａｎ Eｆｆｅｃｔｉｖｅ Hｙｂｒｉｄ ＰＳＯ－Bａｓｅｄ Aｌｇｏｒｉｔｈｍ ｆｏｒ Flｏｗ Sｈｏｐ Sｃｈｅｄｕｌｉｎｇ ｗｉｔｈ Lｉｍｉｔｅｄ Bｕｆｆｅｒｓ［J］． Ｃｏｍｐｕｔｅｒｓ ａｎｄ Ｏｐｅｒａｔｉｏｎｓ Ｒｅｓｅａｒｃｈ， ２００８，３５（9）：２７９１-２８０６．

［26］ 王萬良，宋璐，等． 含有混合中間存儲策略的模糊流水車間調度方法［J］． 計算機集成制造系統(tǒng)， ２００６（１２）：２０６７－２０７３．

［27］ ＳｈｉＱｉａｎｇ Ｌｉｕ， Ｅｒｈａｎ Ｋｏｚａｎ． Ｓｃｈｅｄｕｌｉｎｇ ａ Flｏｗ Sｈｏｐ ｗｉｔｈ Cｏｍｂｉｎｅｄ Bｕｆｆｅｒ Cｏｎｄｉｔｉｏｎｓ［J］． International Journal of Ｐｒｏｄｕｃｔｉｏｎ Ｅｃｏｎｏｍｉｃｓ， ２００９， １１７（2）：３７１-３８０．

［28］ 鄭大鐘， 趙千川． 離散事件動態(tài)系統(tǒng)［Ｍ］． 北京：清華大學出版社， ２００１：１６８－１８８．

［29］ Ｒ Ｃｏｎｗａｙ， Ｗ Ｍａｘｗｅｌｌ，et al． Ｔｈｅ Rｏｌｅ ｏｆ Wｏｒｋ－Iｎ－Pｒｅｓｓ Iｎｖｅｎｔｏｒｙ ｉｎ Sｅｒｉａｌ Pｒｏｄｕｃｔｉｏｎ Lｉｎｅｓ［J］． Ｏｐｅｒａｔｉｏｎｓ Ｒｅｓｅａｒｃｈ，１９８８，３６（2）：２２９－２４１．

［30］ Ｆ Ｓ Ｈｉｌｌｉｅｒ， Ｋ Ｃ Ｓｏ． Ｏｎ ｔｈｅ Sｉｍｕｌｔａｎｅｏｕｓ Oｐｔｉｍｉｚａｔｉｏｎ ｏｆ Sｅｒｖｅｒ ａｎｄ Wｏｒｋ Aｌｌｏｃａｔｉｏｎｓ ｉｎ Pｒｏｄｕｃｔｉｏｎ Lｉｎｅ Sｙｓｔｅｍｓ ｗｉｔｈ Vａｒｉａｂｌｅ Pｒｏｃｅｓｓｉｎｇ Tｉｍｅｓ． Ｏｐｅｒａｔｉｏｎｓ Ｒｅｓｅａｒｃｈ， １９９６，４４（3）： ４３５－４４３．

［31］ Ｇ Ａ Ｖｏｕｒｏｓ， Ｈ Ｔ Ｐａｐａｄｏｐｏｕｌｏｓ． Ｂｕｆｆｅｒ Aｌｌｏｃａｔｉｏｎ ｉｎ Uｎｒｅｌｉａｂｌｅ Pｒｏｄｕｃｔｉｏｎ Lｉｎｅｓ Uｓｉｎｇ ａ Kｎｏｗｌｅｄｇｅ Bａｓｅｄ Sｙｓｔｅｍ［J］．Ｃｏｍｐｕｔｅｒｓ ａｎｄ Ｏｐｅｒａｔｉｏｎｓ Ｒｅｓｅａｒｃｈ， １９９８，２５（12）：１０５５－１０６７．

［32］ Ｌｉ Ｍｉｎｇ． Ｄｅｔｅｒｍｉｎａｔｉｏｎ ｏｆ Ｏｐｔｉｍａｌ Ｂｕｆｆｅｒ Ｓｉｚｅｓ ｉｎ Ｓｔａｔｉｃ Ｂｕｆｆｅｒ Ｍａｎａｇｅｍｅｎｔ［C］． Proceedings of ＩＥＥＥ Region 10 Conference on Computer，Communication，Control and Power，1993：479-486．

［33］ Ｍｉｃｈａｅｌ Ｘ Ｗｅｎｇ． Simulation in Production Scheduling : Ｓｃｈｅｄｕｌｉｎｇ Fｌｏｗ－Sｈｏｐｓ ｗｉｔｈ Lｉｍｉｔｅｄ Bｕｆｆｅｒ Sｐａｃｅｓ［C］． Ｐｒｏｃｅｄｉｎｇｓ ｏｆ ｔｈｅ ２０００ Wｉｎｔｅｒ Sｉｍｕｌａｔｉｏｎ Cｏｎｆｅｒｅｎｃｅ，2000，Vol.2：1359-1363．

［34］ Ｆｅｎｇ-Ｃｈｅｎｇ Ｌｉｎａ， Ｊｅｎ-Ｓｈｉｎ Ｈｏｎｇ， Ｂｅｒｔｒａｎｄ Ｍ Ｔ Ｌｉｎ． Ａ Tｗｏ－Mａｃｈｉｎｅ Flｏｗ Sｈｏｐ Pｒｏｂｌｅｍ ｗｉｔｈ Pｒｏｃｅｓｓｉｎｇ Tｉｍｅ－Dｅｐｅｎｄｅｎｔ Bｕｆｆｅｒ Cｏｎｓｔｒａｉｎｔｓ-Ａｎ Aｐｐｌｉｃａｔｉｏｎ ｉｎ Mｕｌｔｉｍｅｄｉａ Pｒｅｓｅｎｔａｔｉｏｎｓ［J］． Ｃｏｍｐｕｔｅｒｓ ａｎｄ Ｏｐｅｒａｔｉｏｎｓ Ｒｅｓｅａｒｃｈ， ２００９， ３６（4）：１１５８–１１７５．

［35］ 鄭璐， 顧幸生．不確定條件下的含存儲時間有限的Fｌｏｗ Sｈｏｐ生產調度［J］． 系統(tǒng)工程理論方法應用， ２００３， １２（１）：９１－９６．