李傳鵬，王桂從，崔煥勇

(濟(jì)南大學(xué)機(jī)械工程學(xué)院，濟(jì)南 250022)

柔性作業(yè)車間調(diào)度問題研究現(xiàn)狀及發(fā)展趨勢(shì)*

李傳鵬，王桂從，崔煥勇

(濟(jì)南大學(xué)機(jī)械工程學(xué)院，濟(jì)南 250022)

文章描述了柔性作業(yè)車間調(diào)度問題，并根據(jù)目標(biāo)、約束、批量等不同的分類標(biāo)準(zhǔn)對(duì)其進(jìn)行了分類，總結(jié)了柔性作業(yè)車間調(diào)度問題建模方法及優(yōu)化算法的研究現(xiàn)狀，最后通過現(xiàn)存問題的分析探討了發(fā)展趨勢(shì)。

柔性車間調(diào)度;建模;優(yōu)化算法;發(fā)展趨勢(shì)

0 引言

隨著改革步伐的加快和現(xiàn)代工業(yè)的發(fā)展，企業(yè)的生產(chǎn)正朝著多品種、小批量、有著不同完工時(shí)間和產(chǎn)品要求的方向發(fā)展。在這種生產(chǎn)方式下，產(chǎn)品生產(chǎn)品種多、規(guī)模小，造成生產(chǎn)作業(yè)過程中信息復(fù)雜，從而使得企業(yè)的生產(chǎn)作業(yè)計(jì)劃安排工作難度加大，難以控制。容易造成不能按期交貨、產(chǎn)品質(zhì)量不能保證、經(jīng)濟(jì)效益降低等問題。

柔性作業(yè)車間調(diào)度問題(Flexible Job Shop Scheduling Problem，F(xiàn)JSP)是傳統(tǒng)作業(yè)車間生產(chǎn)調(diào)度問題(Job Shop Scheduling Problem，JSP)的擴(kuò)展，是先進(jìn)制造系統(tǒng)運(yùn)籌技術(shù)、管理技術(shù)與優(yōu)化技術(shù)發(fā)展的核心［1］。FJSP 是 Bruker和 Schlies［2］在 1990 年首次提出的，該問題除了要解決JSP中確定加工順序外，還要解決各工序分配到哪臺(tái)機(jī)器上加工的問題，使問題更加復(fù)雜。有關(guān)資料表明，制造過程中95%的時(shí)間消耗在非切削過程中［3］，有效的柔性作業(yè)車間調(diào)度方法的研究，對(duì)提高生產(chǎn)效率和實(shí)現(xiàn)先進(jìn)制造企業(yè)的現(xiàn)代化具有重要意義。

1 FJSP的描述

柔性作業(yè)車間調(diào)度問題描述如下:一個(gè)加工系統(tǒng)有m臺(tái)機(jī)器，要加工n種工件，每個(gè)工件由一道或多道工序組成，各工序有先后約束關(guān)系，且可在m臺(tái)機(jī)器中的一臺(tái)或多臺(tái)機(jī)器上加工，每臺(tái)機(jī)器可加工工件的若干工序，且在不同的機(jī)器上加工的工序集可以不同。調(diào)度的目標(biāo)是將工件合理的安排到各機(jī)器上，并合理安排工件的加工次序和加工時(shí)間，使約束條件被滿足，同時(shí)優(yōu)化一些性能指標(biāo)。

為了方便簡(jiǎn)化問題，F(xiàn)JSP經(jīng)常作出一些條件的假設(shè)［4-5］。例如:①零時(shí)刻所有工件都能被加工;②所有機(jī)器在零時(shí)刻都可用;③每臺(tái)設(shè)備一次只能加工一個(gè)工件;④工序一旦進(jìn)行不能中斷;⑤工件間優(yōu)先級(jí)相同;⑥對(duì)每個(gè)操作均允許等待。

2 FJSP的分類

柔性車間調(diào)度問題的分類方法很多，根據(jù)不同的分類標(biāo)準(zhǔn)可將其劃分為不同的類型。

根據(jù)目標(biāo)劃分，F(xiàn)JSP有單目標(biāo)和多目標(biāo)之分。在FJSP中常見的目標(biāo)有最大完工時(shí)間最小、總加工時(shí)間最小、最大負(fù)荷機(jī)器負(fù)荷最小、提前/拖期懲罰最小、成本最低、設(shè)備利用率最高等。單目標(biāo)FJSP只是針對(duì)其中一個(gè)目標(biāo)進(jìn)行優(yōu)化，比較常見的是最大完工時(shí)間最?。?-8］。但優(yōu)化單個(gè)目標(biāo)很難滿足實(shí)際的生產(chǎn)需要，通常需要同時(shí)考慮多個(gè)目標(biāo)，即在不損壞其他目標(biāo)性能的情況下盡量提高任何一個(gè)目標(biāo)的性能。目前許多學(xué)者開始研究多目標(biāo)FJSP［9-12］，比較常見的是將最大完工時(shí)間最小、最大機(jī)器負(fù)荷最小、總加工時(shí)間最小三個(gè)目標(biāo)同時(shí)考慮。

根據(jù)約束劃分，F(xiàn)JSP常見的約束條件有生產(chǎn)資源(能量、原料、設(shè)備等)、緩存容量、產(chǎn)品交貨期、產(chǎn)品工藝流程、批量大小、成本限制等。Zribi［13］研究了FJSP中資源約束情況下機(jī)器資源的使用;Rossi［14］考慮安裝時(shí)間、增加運(yùn)輸時(shí)間的車間實(shí)際生產(chǎn)情況，利用蟻群算法對(duì)FJSP進(jìn)行求解;張維存［15］等人以能力約束下的FJSP，提出一種主、從遞階結(jié)構(gòu)的蟻群遺傳求解算法。實(shí)際生產(chǎn)中，往往需要同時(shí)考慮多個(gè)約束條件，隨著約束條件的增多，F(xiàn)JSP的求解會(huì)更加復(fù)雜。

根據(jù)批量劃分，F(xiàn)JSP有小批量和中小批量之分。分批就是將作業(yè)的加工方式由串行轉(zhuǎn)換成并行，Low［16］已經(jīng)驗(yàn)證了分批處理可以使機(jī)器利用率得到提高。分批調(diào)度的關(guān)鍵是如何確定最佳子批數(shù)量，子批數(shù)量過少，分批的有效性會(huì)降低，機(jī)器空閑時(shí)間增加;子批數(shù)量過多，增加了調(diào)度的復(fù)雜性，且增大了工作的準(zhǔn)備時(shí)間所帶來的時(shí)間消耗。白俊杰［17］提出可以根據(jù)機(jī)床負(fù)荷將工件分為具有柔性批量的適當(dāng)子批量的粒子群的算法，同時(shí)優(yōu)化了子批的工藝路錢及加工順序。

根據(jù)系統(tǒng)的性能劃分，有靜態(tài)問題和動(dòng)態(tài)問題之分。靜態(tài)調(diào)度是指所有需要生產(chǎn)資源都在初始時(shí)刻到達(dá)，且加工任務(wù)的信息完備可預(yù)知。動(dòng)態(tài)調(diào)度是指調(diào)度的環(huán)境和任務(wù)存在不可預(yù)測(cè)的擾動(dòng)情況下的調(diào)度，不僅依賴于事前調(diào)度環(huán)境和任務(wù)，而且與當(dāng)前的狀態(tài)有關(guān)［18］?，F(xiàn)在車間調(diào)度類型通常是動(dòng)態(tài)的。楊紅紅［19］根據(jù)建立的動(dòng)態(tài)數(shù)據(jù)庫(kù)管理模塊和遺傳算法模塊，引入約束解決機(jī)制，對(duì)動(dòng)態(tài)環(huán)境下的調(diào)度問題進(jìn)行研究。吳秀麗［20］采用事件驅(qū)動(dòng)和周期驅(qū)動(dòng)相結(jié)合的調(diào)度策略，提出了基于多目標(biāo)免疫遺傳算法的動(dòng)態(tài)調(diào)度優(yōu)化模型，設(shè)計(jì)了面向交貨期性能最優(yōu)的柔性作業(yè)車間調(diào)度算法。

3 FJSP的建模方法

FJSP具有復(fù)雜性、多約束性、多目標(biāo)性、動(dòng)態(tài)隨機(jī)性等特點(diǎn)。車間調(diào)度問題都是對(duì)具體的生產(chǎn)環(huán)境中復(fù)雜動(dòng)態(tài)、多目標(biāo)、多約束調(diào)度問題的一種抽象和簡(jiǎn)化，其首要問題是對(duì)制造系統(tǒng)進(jìn)行建模。目前建模方法有很多，主要包括以下三大類:第一類是數(shù)學(xué)規(guī)劃法，第二類是圖與網(wǎng)絡(luò)方法，第三類是仿真法。

3.1 數(shù)學(xué)規(guī)劃法

數(shù)學(xué)規(guī)劃法是用數(shù)學(xué)關(guān)系表達(dá)式表達(dá)所研究系統(tǒng)變量之間的相互關(guān)系。龐哈利［21］研究了柔性作業(yè)車間計(jì)劃與調(diào)度問題，建立了兩層混合整數(shù)規(guī)劃模型，綜合運(yùn)用門檻接受算法、遺傳算法和啟發(fā)式規(guī)則，提出了混合啟發(fā)式求解算法。Parviz Fattahi［22］對(duì)柔性車間調(diào)度問題建立了一個(gè)數(shù)學(xué)線性規(guī)劃模型，用模擬退火啟發(fā)式和禁忌搜索啟發(fā)式方法分別提出了兩種遺傳算法。該方法所建模型有較強(qiáng)的邏輯性，并能實(shí)現(xiàn)系統(tǒng)的優(yōu)化，是車間調(diào)度問題中應(yīng)用較多的一種建模方法。

3.2 圖和網(wǎng)絡(luò)方法

圖和網(wǎng)絡(luò)方法主要有活動(dòng)循環(huán)圖、關(guān)鍵路徑法、組合網(wǎng)絡(luò)、Petri網(wǎng)、GRAI網(wǎng)等。其中Petri網(wǎng)具有直觀的圖形表示方式和嚴(yán)密的數(shù)學(xué)基礎(chǔ)，系統(tǒng)描述手段豐富，行為分析技術(shù)成熟，被作為柔性制造系統(tǒng)的建模、分析、控制與調(diào)度的重要技術(shù)手段。主要有:樂曉波［23］以帶有約束條件的Petri網(wǎng)為動(dòng)態(tài)車間調(diào)度問題建模，同時(shí)提出一種針對(duì)動(dòng)態(tài)車間調(diào)度問題的編碼粒子群算法，對(duì)調(diào)度序列進(jìn)行優(yōu)化;廖偉志［24］針對(duì)具有混雜特征的柔性制造系統(tǒng)調(diào)度問題，建立了柔性制造系統(tǒng)的一階混雜Petri網(wǎng)模型，提出了用于求解柔性制造系統(tǒng)調(diào)度最優(yōu)解的免疫算法。圖和網(wǎng)絡(luò)方法存在的不足是節(jié)點(diǎn)語義單一，不能攜帶足夠的系統(tǒng)信息量;且重用性差，當(dāng)作業(yè)需求和工藝稍作變動(dòng)，模型結(jié)構(gòu)就需要改動(dòng)。

3.3 仿真法

仿真法就是建立描述系統(tǒng)行為規(guī)律的系統(tǒng)模型，再將其轉(zhuǎn)化為計(jì)算機(jī)仿真程序。與數(shù)學(xué)規(guī)劃法相比較，仿真法直觀且形象化，較為常見仿真語言及軟件如 Witness、SIMSCRIP、ECSL等，其中 witness軟件提供了多種建模元素、優(yōu)化模塊、虛擬現(xiàn)實(shí)模塊等方便于離散事件系統(tǒng)的仿真。陳彩麗［25］針對(duì)車間調(diào)度問題建立了基于Witness的仿真模型，對(duì)實(shí)時(shí)數(shù)據(jù)進(jìn)行了分析和評(píng)價(jià)，并優(yōu)化相關(guān)指標(biāo)和參數(shù)，最后將結(jié)果反饋給仿真系統(tǒng)實(shí)施控制。陳勇［26］等人基于元胞自動(dòng)機(jī)建立了大型零件生產(chǎn)車間動(dòng)態(tài)柔性調(diào)度的仿真模型，將系統(tǒng)劃分為工位元胞、緩存元胞、移動(dòng)粒子、局部自組織演化規(guī)則4部分，最終實(shí)現(xiàn)了通過局域演化對(duì)宏觀工件流加工過程的模擬。仿真法的缺點(diǎn)也很明顯，成本高、建模周期長(zhǎng)、只能給出問題的特解而不是給出問題的通解。

4 FJSP的優(yōu)化方法

對(duì)車間制造系統(tǒng)建立數(shù)學(xué)模型后，就要構(gòu)造相應(yīng)的調(diào)度算法進(jìn)行問題的求解。隨著各種新的相關(guān)科學(xué)與優(yōu)化技術(shù)的建立與發(fā)展，在車間調(diào)度領(lǐng)域也出現(xiàn)了許多新的優(yōu)化方法。解決FJSP的方法主要分為兩類:精確方法和近似方法。

4.1 精確方法

基于運(yùn)籌學(xué)的方法，是將調(diào)度問題簡(jiǎn)化為數(shù)學(xué)模型，規(guī)定一個(gè)目標(biāo)函數(shù)來解決調(diào)度最優(yōu)化或次優(yōu)化問題。主要有整數(shù)規(guī)劃、分枝定界法等。Torabi等人［27］建立了一個(gè)混合0-1規(guī)劃模型，并用枚舉的方法進(jìn)行求解FJSP中的批量調(diào)度問題。宋曄［28］為解決對(duì)精度和實(shí)時(shí)性要求較高的調(diào)度問題，提出了基于分枝定界和神經(jīng)網(wǎng)絡(luò)的實(shí)時(shí)調(diào)度策略。基于運(yùn)籌學(xué)方法能夠保證任務(wù)分配和排序的全局性，但對(duì)于復(fù)雜問題，存在求解空間大和計(jì)算困難等問題限制了它的使用。

4.2 近似方法

近似方法可以很快地得到問題的解，雖不能保證得到的解是最優(yōu)的，但可以較好的滿足實(shí)際問題的需求，適用于大規(guī)模問題。近似方法主要有分派規(guī)則法、基于人工智能的方法、鄰域搜索法等。

分派規(guī)則法是最早的近似方法。Panwalkar和Iskander［29］總結(jié)了113條規(guī)則，并將它們分為三類:簡(jiǎn)單規(guī)則、復(fù)合規(guī)則、啟發(fā)式規(guī)則，比較常用的規(guī)則有SPT、LPT、EDD、FCFS等。分派規(guī)則法一般適用于求解數(shù)學(xué)規(guī)劃法的建模，但采用該方法求解多目標(biāo)FJSP的研究較少，因?yàn)槭褂脝我坏膬?yōu)先規(guī)則得到的解不能滿足要求，如何把多個(gè)規(guī)則進(jìn)行融合，得到一個(gè)合理的滿意度值是該方法研究的方向。主要有:Ho和Tay［30］利用進(jìn)化算法對(duì)分派規(guī)則進(jìn)行組合并應(yīng)用于FJSP。

人工智能是指模擬人類智能活動(dòng)進(jìn)行優(yōu)化的方法。主要包括:約束滿足、專家系統(tǒng)及神經(jīng)網(wǎng)絡(luò)等。約束滿足是通過運(yùn)用限制選擇變量的次序和變量值排序的約束來減少搜索空間的有效規(guī)模。專家系統(tǒng)是將傳統(tǒng)的調(diào)度方法與基于知識(shí)的調(diào)度評(píng)價(jià)相結(jié)合，根據(jù)給定的優(yōu)化目標(biāo)和系統(tǒng)當(dāng)前狀態(tài)，對(duì)知識(shí)庫(kù)進(jìn)行有效的啟發(fā)式搜索和并行模糊推理，避開繁瑣的計(jì)算，選擇最優(yōu)的調(diào)度方案。神經(jīng)網(wǎng)絡(luò)優(yōu)化法主要是利用其并行計(jì)算能力和學(xué)習(xí)能力進(jìn)行優(yōu)化，最終實(shí)現(xiàn)可行的調(diào)度策略。目前僅見到神經(jīng)網(wǎng)絡(luò)求解FJSP的少量研究，Xu［31］設(shè)計(jì)一種離散神經(jīng)網(wǎng)絡(luò)結(jié)合瞬時(shí)混沌方法進(jìn)行求解FJSP。把神經(jīng)網(wǎng)絡(luò)和其他啟發(fā)式算法結(jié)合將是該方法的研究熱點(diǎn)。

鄰域搜索法包括遺傳算法、蟻群算法、禁忌搜索算法、粒子群算法等，用其求解數(shù)學(xué)規(guī)劃法、圖和網(wǎng)絡(luò)方法建模的FJSP問題都有大量研究。它的思想是對(duì)調(diào)度問題的解進(jìn)行編碼，編碼與問題的調(diào)度方案一一對(duì)應(yīng)，從任意有效的編碼開始對(duì)其鄰域的不斷搜索，并對(duì)當(dāng)前序列進(jìn)行替換來實(shí)現(xiàn)優(yōu)化，通常用于規(guī)模較大、傳統(tǒng)方法難以求解的問題。其中遺傳算法在求解很多組合優(yōu)化問題時(shí)，不需要有很多技巧和對(duì)問題深入了解;且與其他啟發(fā)式算法有較好的兼容性，能發(fā)揮各自優(yōu)勢(shì)來提高求解能力。孫艷豐［32］提出將遺傳算法與禁忌搜索混合策略，加快了收斂速度，提高了遺傳算法的局部搜索能力;高杰等人［33］設(shè)計(jì)了一種結(jié)合遺傳算法和變鄰域下降算法的綜合算法。蟻群算法最初是用于解決TSP問題的，具有通用性和魯莽性的隨機(jī)試探法，近年來已滲透到車間調(diào)度領(lǐng)域。Silva［34］通過研究得出蟻群算法更適合動(dòng)態(tài)調(diào)度問題;Yu等［35］提出使用經(jīng)過突變處理的蟻群優(yōu)化算法，使其不容易陷入局部最優(yōu)，通過這種蟻群算法解決動(dòng)態(tài)車間調(diào)度的緊急訂單插入重調(diào)度問題。禁忌搜索算法對(duì)求解的問題、目標(biāo)函數(shù)及搜索空間沒有特殊的要求，且計(jì)算速度較快，受到了許多學(xué)者的重視。李俊青［36］提出了帶有Pareto檔案集的混合禁忌搜索算法，保證了解的多樣性，并引入基于關(guān)鍵塊結(jié)構(gòu)的插入鄰域和交換鄰域操作，縮小了搜索空間。賈兆紅［37］在粒子群算法應(yīng)用上做了大量工作，利用混沌對(duì)算法的參數(shù)進(jìn)行自適應(yīng)優(yōu)化，提出了一種混合的粒子群算法，提高搜索能力。Ghasem Moslehi等［38］設(shè)計(jì)了粒子群優(yōu)化算法和鄰域搜索算法相結(jié)合的Pareto算法來求解多目標(biāo)FJSP問題。

除此之外，還有很多種方法對(duì)FJSP進(jìn)行求解，如模糊數(shù)學(xué)理論、多代理方法等。各種調(diào)度算法都不同程度地存在著優(yōu)缺點(diǎn)，除傳統(tǒng)組合的啟發(fā)式規(guī)則外，近年來，人們把各種近似算法的組合應(yīng)用研究作為熱點(diǎn)，以彌補(bǔ)各自的缺點(diǎn)，發(fā)揮各自優(yōu)勢(shì)，達(dá)到高度次優(yōu)化的目標(biāo)。

5 FJSP的發(fā)展趨勢(shì)

雖然我們對(duì)FJSP已有大量的研究，但要形成一套系統(tǒng)的理論和方法還有很長(zhǎng)的路要走，理論研究與實(shí)際應(yīng)用存在的差距還是很大的。主要存在以下幾個(gè)方面的問題:

(1)用數(shù)學(xué)規(guī)劃的方法描述調(diào)度問題能夠使用各種優(yōu)化算法進(jìn)行優(yōu)化求解，由于描述方法的限制，忽略了很多實(shí)際因素;用Petri網(wǎng)的建模方法能夠較好的考慮系統(tǒng)的實(shí)際因素，但它們對(duì)調(diào)度多用啟發(fā)式規(guī)則而沒有尋求一些全局最優(yōu)的方法，都有待發(fā)展。

(2)多目標(biāo)柔性作業(yè)車間調(diào)度問題的討論僅僅局限在所有工件的目標(biāo)均相同的情況下，關(guān)于各種工件目標(biāo)不同的調(diào)度問題研究不夠成熟，對(duì)工件生產(chǎn)批量不同的問題研究更少。

(3)單一的優(yōu)化算法存在局限性，比如:遺傳算法、禁忌搜索、模擬退火等。多種方法混合使用可以平衡算法搜索的廣泛性和集中性，避免早熟，避免陷入局部最優(yōu)。

(4)對(duì)于動(dòng)態(tài)調(diào)度的研究相對(duì)較少，一般都采用基于事件的重調(diào)度或者周期調(diào)度，而對(duì)于重調(diào)度后的效果如何的研究較少，需要進(jìn)一步研究。

［1］朱星輝，朱金福，姜濤.作業(yè)車間調(diào)度問題的幾種模型之比較［J］. 統(tǒng)計(jì)與決策，2007，23:174-176.

［2］BRUKER P，SCHLIC R.Job Shop Scheduling with MultipurposeMachines［J］.Computing，1990，4(2):369-375.

［3］何霆，劉飛，馬玉林，等.車間生產(chǎn)調(diào)度問題研究［J］.機(jī)械工程學(xué)報(bào)，2000，36(5):97-103.

［4］吳秀麗，孫樹棟，楊展，等.多目標(biāo)柔性Job Shop調(diào)度問題的技術(shù)現(xiàn)狀和發(fā)展趨勢(shì)［J］.計(jì)算機(jī)應(yīng)用研究，2007，24(3):1-5.

［5］王銳.應(yīng)用多種群遺傳算法求解動(dòng)態(tài)車間調(diào)度問題［D］.大連:大連理工大學(xué)，2009.

［6］KACEM I.Genetic Algorithm for the Flexible Job-Shop Scheduling Problem［J］.IEEE International Conference on Systems，Man and Cybernetics，2003，4:3464-3469.

［7］YAZDANI M，AMIRI M，ZANDIEH M.Flexible job-shop scheduling with parallel variable neighborhood search algorithm［J］.Expert Systems with Applications，2010，37:678-687.

［8］ZHANG G H，GAO L，SHI Y.An effective genetic algorithm for the flexible job-shop scheduling problem［J］.Expert Systems with Applications，2011，38:3563-3573.

［9］潘全科，朱劍英.多工藝路線多資源多目標(biāo)的作業(yè)調(diào)度優(yōu)化［J］. 中國(guó)機(jī)械工程，2005，16(20):1821-1825.

［10］ADIBI M A，ZANDIEH M，AMIRI M.Multi-objective scheduling of dynamic job shop using variable neighborhood search［J］.Expert Systems with Applications，2010，37:282-287.

［11］XIA W，WU Z.An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problems［J］.Computers and Industrial Engineering，2005，48(2):409-425.

［12］VILCOT G，BILLAUT J C，ESSWEIN C.A genetic algorithm for a bicriteria flexible job shop scheduling problems［J］.Internation Conference on Service Systems and Service Management，2006，2:1240-1244.

［13］ZRIBI N，BORNE P.Hybrid genetic algorithm for the flexible job-shop problem under maintenance constraints［J］.LNCS，2005，3612:259-268.

［14］ROSSI A，DINI G.Flexible job-shop scheduling with routing flexibility and separable setup times using ant colony optimization method［J］.Robotics and Computer-Integrated Manufacturing，2007，23:503-516.

［15］張維存，鄭丕諤，吳曉丹.蟻群遺傳算法求解能力約束的柔性作業(yè)車間調(diào)度問題［J］.計(jì)算機(jī)集成制造系統(tǒng)，2007，13(2):333-347.

［16］LOW C Y，HSU C M，HUANG K I.Benefits of lot splitting in Job-Shop scheduling［J］.International Journal of Advanced Manufacturing Technology，2004，24(9/10):773-780.

［17］白俊杰，龔毅光，王寧生，等.多目標(biāo)柔性作業(yè)車間分批優(yōu)化調(diào)度［J］.計(jì)算機(jī)集成制造系統(tǒng)，2010，16(2):396-403.

［18］王萬良，吳啟迪.生產(chǎn)調(diào)度智能算法及其應(yīng)用［M］.北京:科學(xué)出版社，2007.

［19］楊紅紅，吳智銘.基于自適應(yīng)遺傳算法的柔性動(dòng)態(tài)調(diào)度研究［J］. 中國(guó)機(jī)械工程，2002，13(21):1845-1848.

［20］吳秀麗.柔性作業(yè)車間動(dòng)態(tài)調(diào)度問題研究［J］.系統(tǒng)仿真學(xué)報(bào)，2008，20(14):3828-3832.

［21］龐哈利.柔性Job Shop集成化計(jì)劃調(diào)度模型及其求解算法［J］. 控制與決策，2003，18(1):34-39.

［22］PARVIZ F，ALIREZA F.Dynamic scheduling in flexible job shop systems by considering simultaneously efficiency and stability［J］.CIRP Journal of Manufacturing Science and Technology，2010(2):114-123.

［23］樂曉波，秦娜，劉武.基于Petri網(wǎng)和PSO算法的動(dòng)態(tài)分類車間調(diào)度［J］.長(zhǎng)沙理工大學(xué)學(xué)報(bào)，2008，5(2):72-76.

［24］廖偉志，古天龍，王汝涼，等.基于混雜Petri網(wǎng)的柔性制造系統(tǒng)免疫調(diào)度算法［J］.系統(tǒng)仿真學(xué)報(bào)，2010，22(1):205-209.

［25］陳彩麗，王加興.基于Witness的汽輪機(jī)葉片車間仿真優(yōu)化方法研究［J］. 輕工機(jī)械，2010，28(4):116-122.

［26］陳勇，阮幸聰，魯建廈.基于元胞自動(dòng)機(jī)的大型零件生產(chǎn)車間動(dòng)態(tài)柔性調(diào)度仿真建模［J］.中國(guó)機(jī)械工程，2010，21(21):2603-2608.

［27］Torabi S A，Karimi B，F(xiàn)atemi S M T.The common cycle economic lot scheduling in flexible job shops:the finite horizon case［J］.Int J.Production Economics，2005，97(1):52-65.

［28］宋曄，楊根科.基于分支定界和神經(jīng)網(wǎng)絡(luò)的實(shí)時(shí)調(diào)度策略［J］. 計(jì)算機(jī)仿真，2008，25(12):321-324.

［29］PANWALKER S，WAFIK I.A Survey of Scheduling［J］.OPS.Res.2003，25(1):45-61.

［30］HO N B，TAY J C.Genace:an efficient cultural algorithm solving the flexible job shop problem:proceedings of Congress on Evolutionary Computation［C］.2004:1759-1766.

［31］XU X L，GUAN Q，WANG W L，et al.Transient chaotic discrete neural network for flexible job-shop scheduling［J］.LNCS，2005，3496:762-769.

［32］孫艷豐.基于遺傳算法和禁忌搜索算法的混合策略及應(yīng)用［J］. 北京工業(yè)大學(xué)學(xué)報(bào)，2006，32(3):258-262.

［33］GAO J，SUN L Y，GEN M.A hybrid genetic and variable neighborhood descent algorithm for flexible job shop scheduling problem［J］.Computers＆ Operations Research，2008，35:2892-2907.

［34］SILVA C A，SOUSA J M C，RUNKLER T A.Rescheduling and optimization of logistic processes using GA and ACO［J］.Engineering Applications of Artificial Intelligence，2008，21(3):343-352.

［35］YU Y H，YAN J Q.Flow shop rescheduling problem under rush orders［J］.Journal of Zhejiang University，2005，10:1040-1046.

［36］李俊青，潘全科，王玉亭.多目標(biāo)柔性車間調(diào)度的Pareto混合禁忌搜索算法［J］.計(jì)算機(jī)集成制造系統(tǒng)，2010，16(7):1419-1425.

［37］賈兆紅，陳華平，孫耀暉.多目標(biāo)粒子群優(yōu)化算法在柔性車間調(diào)度中的應(yīng)用［J］.小型微型計(jì)算機(jī)系統(tǒng)，2008，5(5):885-889.

［38］GHASEM M，MEHDI M.A pareto approach to multi-objective flexible job-shop scheduling problem using particle swarm optimization and local search［J］.International Journal of Production Economics，2011，129:14-22.

Research Status and Development Trend of Flexible Job Shop Scheduling Problem

LI Chuan-peng，WANG Gui-cong，CUI Huan-yong
(School of Mechanical Engineering，University of Jinan，Jinan 250022，China)

This paper describes the flexible job shop scheduling problem，classifies according to the different classification criteria of objectives，constraints，batches and so on，and summarizes research status of flexible job shop scheduling problem’s modeling methods and optimization algorithm，finally through the analysis of the existing problems，discusses the development trend.

flexible job shop scheduling problem;modeling;optimization algorithm;development trend

TH162;TP273

A

1001-2265(2012)11-0109-04

2012-04-16

山東省優(yōu)秀中青年科學(xué)家科研獎(jiǎng)勵(lì)基金(BS2009ZZ013)

李傳鵬(1987—)，男，山東榮成人，濟(jì)南大學(xué)機(jī)械工程學(xué)院碩士研究生，研究方向?yàn)橹圃煜到y(tǒng)工程及其信息集成，(E-mail)lcp87292006@126.com

(編輯 李秀敏)