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

于艷輝 侯東亮

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

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

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

［中圖分類號(hào)］F273；F406.2［文獻(xiàn)標(biāo)識(shí)碼］A［文章編號(hào)］1673 - 0194（2012）06- 0061- 03

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

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

１．１問題描述

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

１．２ＬＢＦＳＳＰ調(diào)度問題的模型

１．２．１一般數(shù)學(xué)模型

該調(diào)度問題通常以加工完成時(shí)間最小化為目標(biāo)，即ｍａｋｅｓｐａｎ Cmax，則數(shù)學(xué)模型可表示為如下形式：

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

min｛Sn，m + pn，m｝

≠ k），j∈J

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

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

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

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

２．１鄰域搜索算法

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

2.1.1禁忌搜索算法

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

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

2.1.２遺傳算法

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

２．２其他理論和技術(shù)

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

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

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

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

４存儲(chǔ)時(shí)間有限型緩沖區(qū)

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

５問題討論與展望

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

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

（２） 緩沖區(qū)的大小對(duì)目標(biāo)函數(shù)及算法的設(shè)計(jì)存在著很大的影響，目前大部分結(jié)論都是通過實(shí)驗(yàn)數(shù)據(jù)得到的，缺乏更多的理論基礎(chǔ)，如何合理設(shè)置緩沖區(qū)需要進(jìn)一步的研究。

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

主要參考文獻(xiàn)

［１］ Ｓｍｕｔｎｉｃｋｉ Ｃ． Ｂｌｏｃｋ 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ū)流水線調(diào)度的多搜索模式遺傳算法［J］． 計(jì)算機(jī)集成制造系統(tǒng)，２００５，１１（７）：１０４１－ １０４６．

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

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

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

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

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

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

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

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

［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］ 鄭璐， 顧幸生．不確定條件下的含存儲(chǔ)時(shí)間有限的Fｌｏｗ Sｈｏｐ生產(chǎn)調(diào)度［J］． 系統(tǒng)工程理論方法應(yīng)用， ２００３， １２（１）：９１－９６．