柔性作業車間的成套訂單調度問題

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

（華東理工大學化工過程先進控制和優化技術教育部重點實驗室，上海 200237）

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

蟻群算法具有相對較好的尋優特性，廣泛應用于組合優化問題中[9]。本文在最大最小螞蟻系統（Max-Min Ant System，MMAS）的基礎上，根據成套訂單問題工件之間配套性的特點設計了新的鄰域結構，提出了一種具有鄰域結構的最大最小螞蟻系統（ MAX-MIN Ant System with a Neighbor Structure， MMAS-NS）。通過鄰域搜索反復迭代縮減瓶頸訂單和瓶頸工件的交貨時間瓶頸，達到消除訂單工件交貨時間瓶頸的效果，進而使瓶頸工件按時完工，最終達到提高加權訂單成套率的目的。實驗結果表明，MMAS-NS 算法能夠獲得加權訂單成套率較高的解，表現出比其他算法優越的性能。

1 問題模型和特點

1.1 問題模型

針對柔性作業車間環境下的成套訂單調度問題模型，有以下描述：n 個工件在m 臺機器上加工，這n 個工件分別屬于H 個訂單。

訂單層面看，每個訂單來自不客戶，對于訂單h，其權重為 wh，表示該訂單的重要性，它包含 nh個工件，可表示為。

（1）每臺機床每次只能加工一個工件；

（2）每個工序的加工過程不能中斷；

（3）工件之間具有相同的優先級；

（4）不同工件的工序之間沒有前后約束；

（5）所有工件到達時間均為零。

柔性作業車間環境下成套訂單調度問題的數學模型表示如下：

其中， xh是決策變量：

約束條件如下：

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

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

1.2 問題特點

柔性作業車間的成套訂單調度問題是以加權訂單成套率作為目標函數，因此與其他目標函數的調度問題相比，具有以下特點：

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

（2）難跳出局部最優狀態。搜索過程停滯時，搜索結果的進一步改進需要加權訂單成套率的進一步提高，即需要未成套的訂單滿足成套要求，而未成套訂單可能包含多個工件，需要將每個工件的交貨時間瓶頸削減到0 才能滿足成套要求。與以makespan作為目標函數的調度問題相比，顯然成套訂單調度問題的搜索過程更難跳出局部最優的狀態。

2 MMAS-NS 算法

2.1 算法框架

與其他種類蟻群算法(AS、ACO)相比，MMAS具有相對更好的搜索效果，但它仍然存在和其他元啟發式算法相同的缺陷：雖然全局尋優能力較強，但局部搜索能力弱，當迭代達到一定代數后，信息素集中在某條路徑，種群同化現象嚴重，容易陷入局部最優。為了避免螞蟻種群的過早同化，彌補群智能算法局部搜索能力的不足，本文針對成套訂單調度問題的特點提出了一種新的鄰域結構，結合MMAS 得到帶有鄰域結構的最大最小螞蟻系統(MMAS-NS)。MMAS-NS 的流程如圖1 所示。

圖 1 具有鄰域結構的最大最小螞蟻系統流程圖Fig. 1 Flowchart of MMAS-NS

2.1.1 編碼 解的編碼方式采用擴展的基于工序的編碼方式。解個體由兩部分組成：基于工序編碼的工序加工順序序列(OS)、基于機器編碼的工序加工機器序列(MS)。OS 段的數字代表工件，數字出現的次數代表該工件對應的工序；MS 段依次代表工件工序的加工機器。一種FJSP 的編碼方式如圖2 所示。

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

2.1.2 終止準則 算法在150 代內振幅不超過5%時終止迭代過程。

2.2 鄰域結構

2.2.1 鄰域搜索算法的思想和結構 訂單未成套的原因在于訂單中存在工件完工時間超過規定交貨期，要想該訂單成套，需要削減和消除訂單中瓶頸工件的交貨時間瓶頸。對于訂單h 中的瓶頸工件i，其交貨時間瓶頸定義如下：當時，工件完工時間晚于規定交貨時間，稱工件具有交貨時間瓶頸，該工件稱為瓶頸工件，包含瓶頸工件的訂單稱為瓶頸訂單。

文獻[10]針對作業車間下makespan 最小化問題提出了有效鄰域結構N5，利用關鍵塊首和塊尾工序交換縮短關鍵路徑的長度；類似地，針對成套訂單問題，重新選擇針對瓶頸工件的關鍵路徑，并利用類似N5 的工序交換操作可以縮短瓶頸工件的關鍵路徑長度，當瓶頸訂單內所有瓶頸工件的交貨時間瓶頸削減到0 時，加權訂單成套率得到提高。

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

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

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

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

2.2.2 待搜索解、瓶頸訂單和瓶頸工件的選擇 待搜索解的選擇：在鄰域搜索過程中貪婪選擇訂單加權成套率高的解，當兩個或多個解的訂單加權成套率相同時，選擇加權瓶頸小的訂單（因為該解權值較高的未成套訂單的交貨時間瓶頸相對較小），訂單加權瓶頸表示如下：

瓶頸訂單(Choosed_order)的選擇：因為進行鄰域搜索的解即為蟻群算法較優的解，可優化空間較小，所以直接選擇未成套訂單中權值最大的訂單。若兩個訂單權值相同，選擇訂單總交貨時間瓶頸較小的訂單。

瓶頸工件(Choosed_job)的選擇：選擇交貨時間瓶頸大的工件。工件交貨時間瓶頸越大越難以消除，若該工件瓶頸無法完全消除，可直接放棄對該訂單的優化進行下一個訂單的優化。

2.2.3 鄰域解的生成 本文的鄰域結構不改變工序的加工機器，只改變工序間的相對位置。

關鍵路徑的選取：首先建立空的關鍵路徑工序集Set_CriticalPath，將Choosed_job 的最后一道工序放入關鍵路徑。設關鍵工序集Set_CriticalPath 中首道工序為若存在同機緊前工序和同件緊前 工 序，則 分 別 為和。 若的結束時間與的開始時間相同，則選擇加入關鍵工序集Set_CriticalPath，否則選擇加入關鍵工序集Set_CriticalPath，直到的開始時間為0。如圖5 所示甘特圖中關鍵工序集為

可交換工序對和工序交換：工序交換使用N5 鄰域結構，N5 鄰域結構被證明是一種速度較快、效果較好的鄰域結構。同機相連的關鍵工序形成關鍵塊。對于首關鍵塊，只交換塊尾工序和塊尾的同機緊前工序；對于中間關鍵塊，可交換塊首工序和塊首的同機緊后工序，也可以交換塊尾工序和塊尾工序的同機緊前工序；對于尾關鍵塊，只交換塊首工序和塊首工序的同機緊后工序。需要注意的是，若相鄰工序屬于同一個工件，則不能交換。

圖 5 關鍵路徑示意圖Fig. 5 Schematic diagram of critical path

鄰域解生成：對于任意被選擇的解個體，構造其鄰域解時需要對關鍵路徑中的可交換工序對分別進行工序位置交換，其他工序位置不變。由此所得到若干鄰域解的適應度值需要重新計算。當存在鄰域解的適應度值大于當前解時，則利用該鄰域解替換當前解。

3 仿真實驗及性能分析

成套訂單調度問題優化難度較大，因此本文的測試實例是在已有FJSP 實例基礎上加入工件的交貨時間、訂單的工件分布情況、訂單權值生成。其中工件交貨時間在一定范圍內隨機生成，訂單數量、訂單情況（包含哪些工件）、訂單權值隨機生成。隨機生成規則：每個訂單包含的工件采用隨機插入方法生成；訂單數量、訂單權值由式（8）生成。

3.1 算法參數分析和整定

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

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

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

表 1 正交設計因素和水平表Table 1 Factors and levels of orthogonal design

圖 6 不同因素下目標函數95%置信度LSD 區間均值圖Fig. 6 Prediction interval graphs of objective function at different factors

3.2 鄰域結構有效性分析

為了驗證本文提出的鄰域搜索算法的有效性，對小、中、大3 種規模實例進行仿真實驗。選取未加入鄰域結構的MMAS 作為對比算法，對每個實例分別利用MMAS-NS 和MMAS 進行10 次仿真，MMAS算法參數設置和MMAS-NS 相同，記錄迭代過程平均值并作收斂曲線圖，通過對比兩種算法的收斂結果說明MMAS-NS 算法的有效性。

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

由圖7 可知，小規模實例下MMAS-NS 和MMAS算法都能達到較好的尋優效果。因為實例規模較小，雖然MMAS 也可以達到和MMAS-NS 相近的尋優效果，但MMAS-NS 每次搜索的結果更加穩定。以實例1 為例，MMAS 在10 次優化仿真中有4 次陷入了局部最優解，而MMAS-NS 的搜索結果每次都能達到MMAS 搜索結果的最優值，因此目標函數的平均收斂曲線收斂到了更好的值。由于搜索初始階段信息素濃度信息缺乏，且沒有采用精英保留策略，采用最早完工準則選擇機器的方式本身可以構造較優的初始解，因此收斂曲線初始階段可能出現下降情況。

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

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

圖 7 兩個小規模測試實例下的算法收斂曲線圖Fig. 7 Algorithmic convergence curves for two small-scale test instances

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

3.3 算法性能比較

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

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

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

續表 2

為了更加清楚地表現MMAS-NS 和3 種算法的搜索過程，繪制4 種算法在中等規模實例的平均收斂曲線如圖9 所示。可以看出加入了鄰域搜索后的兩種改進算法相比原有的算法性能都得到了提升，而且MMAS-NS 可以達到最好的尋優效果。ICA 和ICANS 收斂速度較快，但基于帝國競爭算法改進的ICANS 存在鄰域搜索不夠充分的缺點，不過性能比ICA仍然有一定的提升。

圖 9 測試實例Case3 的收斂曲線圖Fig. 9 Convergence curves of case3 problem

4 結束語

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