柔性作業(yè)車間的成套訂單調(diào)度問(wèn)題

徐震浩， 周 暢， 張凌波， 顧幸生

（華東理工大學(xué)化工過(guò)程先進(jìn)控制和優(yōu)化技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室，上海 200237）

隨著產(chǎn)品定制服務(wù)的出現(xiàn)，客戶對(duì)產(chǎn)品的定制需求正朝著多品種、小批量、成套性方向發(fā)展。成套訂單問(wèn)題具有廣泛的實(shí)際背景，有相當(dāng)一部分企業(yè)采用定制生產(chǎn)方式，如大型工程、船舶制造等。對(duì)于某些大型機(jī)械，其工件定制通常具有配套性以滿足產(chǎn)品模塊化組裝的要求，企業(yè)的競(jìng)爭(zhēng)力不再局限于生產(chǎn)的高效率和快速性，并且延伸到了工件交付的準(zhǔn)時(shí)性和成套性。雖然成套訂單的生產(chǎn)調(diào)度問(wèn)題是加工制造業(yè)面臨和亟待解決的難點(diǎn)，但與一般的makespan最小化問(wèn)題相比，具有加權(quán)訂單成套率難以提高的特點(diǎn)。如何跳出局部最優(yōu)，提高加權(quán)訂單成套率是成套訂單調(diào)度問(wèn)題的難點(diǎn)和關(guān)鍵。目前，與成套訂單調(diào)度問(wèn)題相關(guān)的文獻(xiàn)很少，且現(xiàn)有的相關(guān)研究?jī)H圍繞單機(jī)或兩臺(tái)機(jī)器的流水車間環(huán)境進(jìn)行，鮮有對(duì)柔性作業(yè)車間環(huán)境下的成套訂單調(diào)度問(wèn)題的研究。與成套訂單調(diào)度問(wèn)題類似的問(wèn)題是最小化提前/拖期懲罰、最小化總拖期等，與成套訂單調(diào)度問(wèn)題的相同點(diǎn)是都需要設(shè)置工件的交貨時(shí)間。Pan 等[1]利用離散蜂群算法解決了批量流水車間的最小化提前拖期問(wèn)題；Zhang 等[2]提出了一種基于塊特性的鄰域結(jié)構(gòu)，融合模擬退火算法解決了最小化作業(yè)車間總拖期時(shí)間問(wèn)題；魯建廈等[3]提出了一種基于模擬退火的混合粒子群算法，解決了最小化作業(yè)車間下總加權(quán)拖期時(shí)間問(wèn)題。成套訂單調(diào)度問(wèn)題是存在工件交貨時(shí)間的前提下同時(shí)存在訂單工件的配套問(wèn)題，Zhou等[4]首先提出了成套訂單問(wèn)題并采用遺傳算法解決了單機(jī)環(huán)境下加權(quán)成套訂單的調(diào)度問(wèn)題；Yu 等[5]提出了采用隨機(jī)鍵編碼方式的螢火蟲算法用來(lái)解決單機(jī)環(huán)境下成套訂單的調(diào)度問(wèn)題；周水銀等[6]采用啟發(fā)式規(guī)則研究解決了兩臺(tái)機(jī)器構(gòu)成的流水車間環(huán)境下的成套訂單調(diào)度問(wèn)題；吳春輝等[7]提出了一種基于工件交貨時(shí)間瓶頸的啟發(fā)式規(guī)則，利用遺傳算法解決了單一工序并行機(jī)環(huán)境下的成套訂單調(diào)度問(wèn)題；傅青[8]以最大化成套訂單數(shù)和最小化總配送時(shí)間為多目標(biāo)，采用遺傳算法和啟發(fā)式算法相結(jié)合的方法求解該多目標(biāo)問(wèn)題。

蟻群算法具有相對(duì)較好的尋優(yōu)特性，廣泛應(yīng)用于組合優(yōu)化問(wèn)題中[9]。本文在最大最小螞蟻系統(tǒng)（Max-Min Ant System，MMAS）的基礎(chǔ)上，根據(jù)成套訂單問(wèn)題工件之間配套性的特點(diǎn)設(shè)計(jì)了新的鄰域結(jié)構(gòu)，提出了一種具有鄰域結(jié)構(gòu)的最大最小螞蟻系統(tǒng)（ MAX-MIN Ant System with a Neighbor Structure， MMAS-NS）。通過(guò)鄰域搜索反復(fù)迭代縮減瓶頸訂單和瓶頸工件的交貨時(shí)間瓶頸，達(dá)到消除訂單工件交貨時(shí)間瓶頸的效果，進(jìn)而使瓶頸工件按時(shí)完工，最終達(dá)到提高加權(quán)訂單成套率的目的。實(shí)驗(yàn)結(jié)果表明，MMAS-NS 算法能夠獲得加權(quán)訂單成套率較高的解，表現(xiàn)出比其他算法優(yōu)越的性能。

1 問(wèn)題模型和特點(diǎn)

1.1 問(wèn)題模型

針對(duì)柔性作業(yè)車間環(huán)境下的成套訂單調(diào)度問(wèn)題模型，有以下描述：n 個(gè)工件在m 臺(tái)機(jī)器上加工，這n 個(gè)工件分別屬于H 個(gè)訂單。

訂單層面看，每個(gè)訂單來(lái)自不客戶，對(duì)于訂單h，其權(quán)重為 wh，表示該訂單的重要性，它包含 nh個(gè)工件，可表示為。

（1）每臺(tái)機(jī)床每次只能加工一個(gè)工件；

（2）每個(gè)工序的加工過(guò)程不能中斷；

（3）工件之間具有相同的優(yōu)先級(jí)；

（4）不同工件的工序之間沒(méi)有前后約束；

（5）所有工件到達(dá)時(shí)間均為零。

柔性作業(yè)車間環(huán)境下成套訂單調(diào)度問(wèn)題的數(shù)學(xué)模型表示如下：

其中， xh是決策變量：

約束條件如下：

其中， ahijkpl和 xhijopqk是決策變量：

式 ( 1) 為問(wèn)題的目標(biāo)函數(shù)，即最大化加權(quán)成套訂單數(shù)，它與每個(gè)訂單的權(quán)值 wh和該訂單的成套系數(shù)xh有關(guān)；式 ( 2) 為加工工藝約束，即工件的某一工序只有在當(dāng)前機(jī)器上加工完成后，才能進(jìn)入下一臺(tái)機(jī)器加工該工件的下一道工序；式 ( 3) 為工序非堵塞約束（資源約束），當(dāng)前工序加工之前需要等待同機(jī)緊前工序加工完成才能開始加工，同機(jī)緊后工序需要在當(dāng)前工序加工完成后才能開始加工。

1.2 問(wèn)題特點(diǎn)

柔性作業(yè)車間的成套訂單調(diào)度問(wèn)題是以加權(quán)訂單成套率作為目標(biāo)函數(shù)，因此與其他目標(biāo)函數(shù)的調(diào)度問(wèn)題相比，具有以下特點(diǎn)：

（1）加權(quán)訂單成套率和工件交貨期有密切關(guān)系。當(dāng)交貨期比較寬松時(shí)，甚至每個(gè)工件都能按時(shí)完工，進(jìn)而每個(gè)訂單都滿足成套性要求，此時(shí)加權(quán)訂單成套率為1；而當(dāng)交貨期設(shè)置得比較緊張時(shí)，未成套訂單所包含的工件都具有較大的交貨時(shí)間瓶頸，而且很難將其交貨時(shí)間瓶頸削減至0。

（2）難跳出局部最優(yōu)狀態(tài)。搜索過(guò)程停滯時(shí)，搜索結(jié)果的進(jìn)一步改進(jìn)需要加權(quán)訂單成套率的進(jìn)一步提高，即需要未成套的訂單滿足成套要求，而未成套訂單可能包含多個(gè)工件，需要將每個(gè)工件的交貨時(shí)間瓶頸削減到0 才能滿足成套要求。與以makespan作為目標(biāo)函數(shù)的調(diào)度問(wèn)題相比，顯然成套訂單調(diào)度問(wèn)題的搜索過(guò)程更難跳出局部最優(yōu)的狀態(tài)。

2 MMAS-NS 算法

2.1 算法框架

與其他種類蟻群算法(AS、ACO)相比，MMAS具有相對(duì)更好的搜索效果，但它仍然存在和其他元啟發(fā)式算法相同的缺陷：雖然全局尋優(yōu)能力較強(qiáng)，但局部搜索能力弱，當(dāng)?shù)_(dá)到一定代數(shù)后，信息素集中在某條路徑，種群同化現(xiàn)象嚴(yán)重，容易陷入局部最優(yōu)。為了避免螞蟻種群的過(guò)早同化，彌補(bǔ)群智能算法局部搜索能力的不足，本文針對(duì)成套訂單調(diào)度問(wèn)題的特點(diǎn)提出了一種新的鄰域結(jié)構(gòu)，結(jié)合MMAS 得到帶有鄰域結(jié)構(gòu)的最大最小螞蟻系統(tǒng)(MMAS-NS)。MMAS-NS 的流程如圖1 所示。

圖 1 具有鄰域結(jié)構(gòu)的最大最小螞蟻系統(tǒng)流程圖Fig. 1 Flowchart of MMAS-NS

2.1.1 編碼 解的編碼方式采用擴(kuò)展的基于工序的編碼方式。解個(gè)體由兩部分組成：基于工序編碼的工序加工順序序列(OS)、基于機(jī)器編碼的工序加工機(jī)器序列(MS)。OS 段的數(shù)字代表工件，數(shù)字出現(xiàn)的次數(shù)代表該工件對(duì)應(yīng)的工序；MS 段依次代表工件工序的加工機(jī)器。一種FJSP 的編碼方式如圖2 所示。

圖 2 一種FJSP 的編碼方式Fig. 2 An encoding method of FJSP

2.1.2 終止準(zhǔn)則 算法在150 代內(nèi)振幅不超過(guò)5%時(shí)終止迭代過(guò)程。

2.2 鄰域結(jié)構(gòu)

2.2.1 鄰域搜索算法的思想和結(jié)構(gòu) 訂單未成套的原因在于訂單中存在工件完工時(shí)間超過(guò)規(guī)定交貨期，要想該訂單成套，需要削減和消除訂單中瓶頸工件的交貨時(shí)間瓶頸。對(duì)于訂單h 中的瓶頸工件i，其交貨時(shí)間瓶頸定義如下：當(dāng)時(shí)，工件完工時(shí)間晚于規(guī)定交貨時(shí)間，稱工件具有交貨時(shí)間瓶頸，該工件稱為瓶頸工件，包含瓶頸工件的訂單稱為瓶頸訂單。

文獻(xiàn)[10]針對(duì)作業(yè)車間下makespan 最小化問(wèn)題提出了有效鄰域結(jié)構(gòu)N5，利用關(guān)鍵塊首和塊尾工序交換縮短關(guān)鍵路徑的長(zhǎng)度；類似地，針對(duì)成套訂單問(wèn)題，重新選擇針對(duì)瓶頸工件的關(guān)鍵路徑，并利用類似N5 的工序交換操作可以縮短瓶頸工件的關(guān)鍵路徑長(zhǎng)度，當(dāng)瓶頸訂單內(nèi)所有瓶頸工件的交貨時(shí)間瓶頸削減到0 時(shí)，加權(quán)訂單成套率得到提高。

本文提出的新的鄰域結(jié)構(gòu)的主要思想：首先要選擇迭代最優(yōu)解Xiter-best或者全局最優(yōu)解Xglobal-best作為鄰域搜索的個(gè)體，然后選擇該個(gè)體中未成套訂單中權(quán)值較大的訂單，接著選擇該訂單中交貨時(shí)間瓶頸較大的瓶頸工件。由被選擇工件的尾工序開始，從后向前選擇一條關(guān)鍵路徑，參考N5 鄰域結(jié)構(gòu)進(jìn)行關(guān)鍵工序位置交換產(chǎn)生新的解，再根據(jù)訂單加權(quán)成套率對(duì)新產(chǎn)生的鄰域解進(jìn)行貪婪選擇，重復(fù)以上過(guò)程直到不能繼續(xù)對(duì)任何工件的交貨時(shí)間瓶頸進(jìn)行削減。

鄰域搜索算法結(jié)構(gòu)如圖3 所示。圖4 為鄰域搜索后的調(diào)度甘特圖。在8 工件5 訂單的情況下，假定綠色虛線是訂單5 中工件7 的交貨期，鄰域搜索前工件7 完工時(shí)間在交貨期之后，在進(jìn)行了工序O72向前插空在O83之前的操作后，工件7 的尾工序O73的完工時(shí)間減小到13，因此訂單5 成套，其他工件的完工時(shí)間不變，加權(quán)訂單成套率上升。

圖 3 鄰域搜索算法流程圖Fig. 3 Flowchart of neighborhood search algorithm

圖 4 鄰域搜索后調(diào)度甘特圖Fig. 4 Gantt chart of scheduling after neighborhood search

2.2.2 待搜索解、瓶頸訂單和瓶頸工件的選擇 待搜索解的選擇：在鄰域搜索過(guò)程中貪婪選擇訂單加權(quán)成套率高的解，當(dāng)兩個(gè)或多個(gè)解的訂單加權(quán)成套率相同時(shí)，選擇加權(quán)瓶頸小的訂單（因?yàn)樵摻鈾?quán)值較高的未成套訂單的交貨時(shí)間瓶頸相對(duì)較?。唵渭訖?quán)瓶頸表示如下：

瓶頸訂單(Choosed_order)的選擇：因?yàn)檫M(jìn)行鄰域搜索的解即為蟻群算法較優(yōu)的解，可優(yōu)化空間較小，所以直接選擇未成套訂單中權(quán)值最大的訂單。若兩個(gè)訂單權(quán)值相同，選擇訂單總交貨時(shí)間瓶頸較小的訂單。

瓶頸工件(Choosed_job)的選擇：選擇交貨時(shí)間瓶頸大的工件。工件交貨時(shí)間瓶頸越大越難以消除，若該工件瓶頸無(wú)法完全消除，可直接放棄對(duì)該訂單的優(yōu)化進(jìn)行下一個(gè)訂單的優(yōu)化。

2.2.3 鄰域解的生成 本文的鄰域結(jié)構(gòu)不改變工序的加工機(jī)器，只改變工序間的相對(duì)位置。

關(guān)鍵路徑的選?。菏紫冉⒖盏年P(guān)鍵路徑工序集Set_CriticalPath，將Choosed_job 的最后一道工序放入關(guān)鍵路徑。設(shè)關(guān)鍵工序集Set_CriticalPath 中首道工序?yàn)槿舸嬖谕瑱C(jī)緊前工序和同件緊前 工 序，則 分 別 為和。 若的結(jié)束時(shí)間與的開始時(shí)間相同，則選擇加入關(guān)鍵工序集Set_CriticalPath，否則選擇加入關(guān)鍵工序集Set_CriticalPath，直到的開始時(shí)間為0。如圖5 所示甘特圖中關(guān)鍵工序集為

可交換工序?qū)凸ば蚪粨Q：工序交換使用N5 鄰域結(jié)構(gòu)，N5 鄰域結(jié)構(gòu)被證明是一種速度較快、效果較好的鄰域結(jié)構(gòu)。同機(jī)相連的關(guān)鍵工序形成關(guān)鍵塊。對(duì)于首關(guān)鍵塊，只交換塊尾工序和塊尾的同機(jī)緊前工序；對(duì)于中間關(guān)鍵塊，可交換塊首工序和塊首的同機(jī)緊后工序，也可以交換塊尾工序和塊尾工序的同機(jī)緊前工序；對(duì)于尾關(guān)鍵塊，只交換塊首工序和塊首工序的同機(jī)緊后工序。需要注意的是，若相鄰工序?qū)儆谕粋€(gè)工件，則不能交換。

圖 5 關(guān)鍵路徑示意圖Fig. 5 Schematic diagram of critical path

鄰域解生成：對(duì)于任意被選擇的解個(gè)體，構(gòu)造其鄰域解時(shí)需要對(duì)關(guān)鍵路徑中的可交換工序?qū)Ψ謩e進(jìn)行工序位置交換，其他工序位置不變。由此所得到若干鄰域解的適應(yīng)度值需要重新計(jì)算。當(dāng)存在鄰域解的適應(yīng)度值大于當(dāng)前解時(shí)，則利用該鄰域解替換當(dāng)前解。

3 仿真實(shí)驗(yàn)及性能分析

成套訂單調(diào)度問(wèn)題優(yōu)化難度較大，因此本文的測(cè)試實(shí)例是在已有FJSP 實(shí)例基礎(chǔ)上加入工件的交貨時(shí)間、訂單的工件分布情況、訂單權(quán)值生成。其中工件交貨時(shí)間在一定范圍內(nèi)隨機(jī)生成，訂單數(shù)量、訂單情況（包含哪些工件）、訂單權(quán)值隨機(jī)生成。隨機(jī)生成規(guī)則：每個(gè)訂單包含的工件采用隨機(jī)插入方法生成；訂單數(shù)量、訂單權(quán)值由式（8）生成。

3.1 算法參數(shù)分析和整定

影響蟻群算法的參數(shù)主要有：螞蟻數(shù)量Npop、信息素殘留系數(shù)ρ、信息啟發(fā)式因子α、期望啟發(fā)式因子β 等。本文通過(guò)正交試驗(yàn)方式對(duì)算法主要參數(shù)進(jìn)行分析。正交試驗(yàn)使用的是20 工件5 機(jī)器11 訂單測(cè)試實(shí)例，工序時(shí)間表見(jiàn)文獻(xiàn)[11]。正交試驗(yàn)因素和水平設(shè)置如表1 所示。

根據(jù)正交表給出的每一組因素水平組合情況，進(jìn)行10 次試驗(yàn)取平均值并做方差分析。

圖6 示出了不同因素下目標(biāo)函數(shù)95%置信度LSD 區(qū)間均值。從圖6 可以看出，算法性能與Npop、ρ、α 相關(guān)，與β 無(wú)關(guān)。隨著Npop的擴(kuò)大，搜索次數(shù)增加，對(duì)解空間的搜索更加徹底，算法全局搜索能力增強(qiáng)，解的質(zhì)量將有所提高，但搜索周期會(huì)相應(yīng)變長(zhǎng)；隨著ρ 的增長(zhǎng)，信息素蒸發(fā)速度降低，算法可以持續(xù)進(jìn)行更大范圍的搜索，解的質(zhì)量將有所提高，但收斂速度將減慢；α 越低，搜索對(duì)信息素濃度的敏感性降低，當(dāng)各條路徑上信息素濃度差別較大時(shí)，較低的α 可以使信息素濃度不同帶來(lái)的影響減小，收斂速度減慢，搜索時(shí)間更長(zhǎng)，得到更好的解，反之若α 較大將會(huì)使這種濃度的差別指數(shù)級(jí)放大，加快收斂速度，往往會(huì)造成搜索收斂到局部最優(yōu)解；β 只在搜索開始階段信息素濃度信息匱乏時(shí)引導(dǎo)搜索進(jìn)行，隨著迭代的進(jìn)行，各路徑間信息素濃度τ 的差別逐漸增大，所以隨著搜索的進(jìn)行，β 的作用越來(lái)越小。本文算法參數(shù)設(shè)置如下：Npop=200，ρ=0.95，α=0.5。

表 1 正交設(shè)計(jì)因素和水平表Table 1 Factors and levels of orthogonal design

圖 6 不同因素下目標(biāo)函數(shù)95%置信度LSD 區(qū)間均值圖Fig. 6 Prediction interval graphs of objective function at different factors

3.2 鄰域結(jié)構(gòu)有效性分析

為了驗(yàn)證本文提出的鄰域搜索算法的有效性，對(duì)小、中、大3 種規(guī)模實(shí)例進(jìn)行仿真實(shí)驗(yàn)。選取未加入鄰域結(jié)構(gòu)的MMAS 作為對(duì)比算法，對(duì)每個(gè)實(shí)例分別利用MMAS-NS 和MMAS 進(jìn)行10 次仿真，MMAS算法參數(shù)設(shè)置和MMAS-NS 相同，記錄迭代過(guò)程平均值并作收斂曲線圖，通過(guò)對(duì)比兩種算法的收斂結(jié)果說(shuō)明MMAS-NS 算法的有效性。

3.2.1 小規(guī)模實(shí)例有效性分析 小規(guī)模實(shí)例包括文獻(xiàn)[12]中的改編測(cè)試實(shí)例1（8 工件8 機(jī)器6 訂單）和根據(jù)文獻(xiàn)[13]提出的Mk01 改編的實(shí)例2（10 工件6 機(jī)器8 訂單）。兩個(gè)實(shí)例的訂單數(shù)量、訂單所含工件、訂單權(quán)值均采用隨機(jī)方式生成。小規(guī)模實(shí)例的收斂曲線如圖7 所示。

由圖7 可知，小規(guī)模實(shí)例下MMAS-NS 和MMAS算法都能達(dá)到較好的尋優(yōu)效果。因?yàn)閷?shí)例規(guī)模較小，雖然MMAS 也可以達(dá)到和MMAS-NS 相近的尋優(yōu)效果，但MMAS-NS 每次搜索的結(jié)果更加穩(wěn)定。以實(shí)例1 為例，MMAS 在10 次優(yōu)化仿真中有4 次陷入了局部最優(yōu)解，而MMAS-NS 的搜索結(jié)果每次都能達(dá)到MMAS 搜索結(jié)果的最優(yōu)值，因此目標(biāo)函數(shù)的平均收斂曲線收斂到了更好的值。由于搜索初始階段信息素濃度信息缺乏，且沒(méi)有采用精英保留策略，采用最早完工準(zhǔn)則選擇機(jī)器的方式本身可以構(gòu)造較優(yōu)的初始解，因此收斂曲線初始階段可能出現(xiàn)下降情況。

3.2.2 中等規(guī)模和大規(guī)模實(shí)例有效性分析 中等規(guī)實(shí)例和大規(guī)模實(shí)例由文獻(xiàn)[14]提出的測(cè)試實(shí)例（實(shí)例3）和文獻(xiàn)[13]提出的Mk10（實(shí)例4）改編而成。收斂曲線如圖8 所示。

圖8 表明，在中等規(guī)模實(shí)例3 中，MMAS-NS 比MMAS 尋優(yōu)性能有很大提升，加權(quán)訂單成套率從0.60 提升到了0.78，并且在200 代以后尋優(yōu)速度有了明顯提升。與小規(guī)模實(shí)例不同，當(dāng)問(wèn)題規(guī)模提升后，沒(méi)有采用鄰域搜索的MMAS 的搜索能力有限，而鄰域搜索算法可以有效提升加權(quán)訂單成套率，尤其是只含有單一工件的訂單成套率。以兩種算法仿真結(jié)果中目標(biāo)函數(shù)值的眾數(shù)為例，10 次MMAS 仿真結(jié)果眾數(shù)為0.591 7，對(duì)應(yīng)滿足成套性的訂單為1、4、6、7、10；10 次MMAS-NS 仿真結(jié)果眾數(shù)為0.784 7，對(duì)應(yīng)滿足成套性的訂單為1、3、4、5、6、7、10，MMASNS 在MMAS 實(shí)現(xiàn)的成套訂單基礎(chǔ)上又實(shí)現(xiàn)了3、5 的成套，而3、5 都是單工件訂單。由于是針對(duì)訂單中的單一工件采用N5 鄰域結(jié)構(gòu)優(yōu)化（將該工件的尾工序作為關(guān)鍵路徑的尾工序），該工件的加工時(shí)間可以有效減小，因此該訂單將成套，加權(quán)訂單成套率提升。大規(guī)模測(cè)試實(shí)例的收斂曲線顯示，MMAS-NS 針對(duì)大規(guī)模算例也有比MMAS 更好的尋優(yōu)性能，分析過(guò)程和中等規(guī)模算例類似，不再贅述。

圖 7 兩個(gè)小規(guī)模測(cè)試實(shí)例下的算法收斂曲線圖Fig. 7 Algorithmic convergence curves for two small-scale test instances

圖 8 中等規(guī)模和大規(guī)模測(cè)試實(shí)例下的算法收斂曲線圖Fig. 8 Algorithmic convergence curves for medium and large scale test instances

3.3 算法性能比較

為了說(shuō)明加入鄰域搜索過(guò)程后MMAS-NS 算法性能的優(yōu)越性，本文針對(duì)不同規(guī)模下成套訂單調(diào)度問(wèn)題的測(cè)試實(shí)例進(jìn)行仿真驗(yàn)證。選擇最大最小螞蟻系統(tǒng)(Max-Min Ant System，MMAS)、帝國(guó)競(jìng)爭(zhēng)算法（Imperialist Competitive Algorithm，ICA）、帶鄰域結(jié)構(gòu)的帝國(guó)競(jìng)爭(zhēng)算法（Imperialist Competitive Algorithm with Neighborhood Structure，ICA-NS）作 為 對(duì) 比 算法。MMAS-NS 和ICA-NS 具有2.2 節(jié)所述鄰域結(jié)構(gòu)。MMAS-NS 和MMAS 的算法參數(shù)根據(jù)3.1 節(jié)分析結(jié)果進(jìn)行設(shè)置，ICA 和ICA-NS 算法參數(shù)設(shè)置參考文獻(xiàn)[15]進(jìn)行，ICA-NS 和ICA 的區(qū)別是在ICA 每完成一次迭代后對(duì)最強(qiáng)帝國(guó)代表的解個(gè)體進(jìn)行鄰域搜索。表2 中所有仿真實(shí)例均采用文獻(xiàn)[16]中的仿真實(shí)例對(duì)每一個(gè)測(cè)試實(shí)例進(jìn)行10 次仿真，并對(duì)仿真結(jié)果進(jìn)行分析，結(jié)果如表2 所示。表2 中n 為總工件數(shù)，m 為機(jī)器數(shù)，o 表示訂單數(shù)，Max 表示最大加權(quán)訂單成套率（Maximum Whole-Set Orders）、Min表示最小 加 權(quán) 訂 單 成 套 率（Minimum Whole-Set Orders）、Avg 表示平均加權(quán)訂單成套率（Average Whole-Set Orders）、Std 表示均方差（Standard Deviation）。

由表2 可知，當(dāng)實(shí)例規(guī)模較小時(shí)，4 種算法都能找到較好的解，而且加入鄰域搜索的MMAS-NS 和ICA-NS 多次仿真的均方差均為0，說(shuō)明在小規(guī)模測(cè)試實(shí)例下，加入了鄰域結(jié)構(gòu)的兩種算法每次都能找到最優(yōu)解。隨著測(cè)試實(shí)例規(guī)模的擴(kuò)大，不加入鄰域搜索的MMAS 和ICA 仿真結(jié)果均值(Avg)大致相同，與MMAS-NS 和ICA-NS 相比結(jié)果較差，說(shuō)明MMAS-NS 和ICA-NS 在中等規(guī)模和大規(guī)模實(shí)例下表現(xiàn)出更加良好的尋優(yōu)性能，進(jìn)而說(shuō)明了鄰域搜索結(jié)構(gòu)的有效性。在中等規(guī)模和大規(guī)模測(cè)試實(shí)例下，MMAS-NS 比ICA-NS 的均值更好，這是因?yàn)镸MASNS 的機(jī)制是在每次迭代后，針對(duì)迭代最優(yōu)解個(gè)體Xiter_best 進(jìn)行鄰域搜索，而在MMAS 的初始階段幾乎每次迭代的最優(yōu)解都是不相同的，因而在MMAS的基礎(chǔ)上加入鄰域搜索可以對(duì)解空間進(jìn)行更廣闊的搜索；ICA 算法具有收斂速度快的特點(diǎn)，而帝國(guó)和殖民地之間是進(jìn)行的有條件的更替，每次迭代最強(qiáng)帝國(guó)不一定改變，換句話說(shuō)，ICA 是自帶精英保留策略的搜索算法，最強(qiáng)帝國(guó)一直是全局最優(yōu)解（精英解），因而ICA-NS 對(duì)解空間的搜索不如MMAS-NS 充分，因此MMAS-NS 比ICA-NS 有更好的全局尋優(yōu)效果。

表 2 4 種算法在不同算例下的仿真結(jié)果對(duì)比Table 2 Comparison of simulation results of four algorithms under different instances

續(xù)表 2

為了更加清楚地表現(xiàn)MMAS-NS 和3 種算法的搜索過(guò)程，繪制4 種算法在中等規(guī)模實(shí)例的平均收斂曲線如圖9 所示?？梢钥闯黾尤肓肃徲蛩阉骱蟮膬煞N改進(jìn)算法相比原有的算法性能都得到了提升，而且MMAS-NS 可以達(dá)到最好的尋優(yōu)效果。ICA 和ICANS 收斂速度較快，但基于帝國(guó)競(jìng)爭(zhēng)算法改進(jìn)的ICANS 存在鄰域搜索不夠充分的缺點(diǎn)，不過(guò)性能比ICA仍然有一定的提升。

圖 9 測(cè)試實(shí)例Case3 的收斂曲線圖Fig. 9 Convergence curves of case3 problem

4 結(jié)束語(yǔ)

成套訂單調(diào)度問(wèn)題是一種在實(shí)際生產(chǎn)過(guò)程中廣泛存在并亟待解決的調(diào)度問(wèn)題，但由于該問(wèn)題的復(fù)雜性，目前的相關(guān)研究主要集中于單機(jī)環(huán)境且研究成果較少。本文提出了一種新的基于柔性作業(yè)車間環(huán)境下的加權(quán)成套訂單調(diào)度模型，分析了解決該問(wèn)題的難點(diǎn)，并針對(duì)問(wèn)題特點(diǎn)提出了一種新的鄰域結(jié)構(gòu)。針對(duì)瓶頸訂單內(nèi)包含的瓶頸工件，通過(guò)反復(fù)削減工件的交貨時(shí)間瓶頸，最終達(dá)到提高加權(quán)訂單成套率的目的。在不同規(guī)模實(shí)例下，通過(guò)MMAS-NS和MMAS 的仿真結(jié)果對(duì)比，驗(yàn)證了該鄰域結(jié)構(gòu)的有效性。為了進(jìn)一步表明算法的有效性，與帝國(guó)競(jìng)爭(zhēng)算法ICA 等其他元啟發(fā)式算法的仿真結(jié)果進(jìn)行了對(duì)比，說(shuō)明了MMAS-NS 在搜索性能方面的優(yōu)越性及其他算法存在的不足。以上結(jié)論僅限于柔性作業(yè)車間環(huán)境下的研究，實(shí)際生產(chǎn)中的模型將會(huì)更加復(fù)雜。另外解個(gè)體中工序加工機(jī)器分配使用的是工序最早完工準(zhǔn)則，如果考慮工序加工機(jī)器的安排，鄰域搜索該如何改進(jìn)，算法性能是否會(huì)有進(jìn)一步的提升，是下一步需要考慮的問(wèn)題。