求解混合流水車間調度的多目標優化算法

謝 光，潘玉霞，李俊青

(1.三亞學院 信息與智能工程學院，海南 三亞 572000；2.聊城大學 計算機學院，山東 聊城 252059；3.東北大學 流程工業自動化國家重點實驗室，遼寧 沈陽 110819)

0 引 言

混合流水車間調度(hybrid flow shop，HFS)作為經典流水車間調度問題的擴展，屬于一類NP-難調度問題[1]。近年來，智能優化算法在求解HFS調度問題中得到了廣泛應用，其中包括蟻群優化方法[1]、分布估計算法(estimation of distribution algorithm，EDA)[2,3]、粒子群優化算法(particle swarm optimization，PSO)[4]、遷徙鳥群優化算法(migrating birds optimization，MBO)[5]、人工蜂群算法[6,7]、布谷鳥群搜索算法(cuckoo search algorithm，CSA)[8]、生物地理學優化算法[9]等。上述文獻中涉及的優化算法，有的全局搜索能力強但局部搜索能力弱，有的則反之。如何有效地平衡算法全局和局部搜索能力，亟待有效解決。算法混合可以有效提高算法性能，已成為相關研究熱點。通過混合不同優化算法，或者優化算法與局部搜索算法相結合，可以在一定程度提升單一優化算法的性能。通過算法混合求解多階段HFS問題的典型文獻包括：人工免疫和蟻群優化混合算法[10]、蟻群優化和遺傳混合算法[11]、迭代局部搜索和迭代貪心算法混合[12]、人工蜂群算法和禁忌算法混合[13]等。然而，綜合考慮HFS調度問題的多目標特點，采用群體智能優化算法，構建一種多目標算法框架，目前相關研究還很少，亟待開展深入研究。

多目標優化算法在工業生產實際中得到了廣泛應用和研究，目前主要有兩種典型的多目標優化算法，即基于Pareto占優[14]和基本分解策略[15]。多目標優化與演化算法的融合也成為研究熱點，如基于差分進化的多目標[16,17]、免疫多目標[18]、文化多目標[19]等算法。目前，在實際工業生產中，特別是鋼鐵生產調度過程中，處理多目標的技術以加權求和方法為主。上述方法一次運行只能得到一個解，且權重系數不好確定。僅有少量文獻針對HFS調度問題開展多目標優化算法研究。譬如，采用NSGA-II求解煉鋼生產HFS調度問題[20]，以及采用MOEA/D求解煉鋼連鑄集成計劃問題[21]等。文獻[22]針對近年來生產制造中的多目標優化算法進行分析。從文獻可見，目前尚缺乏針對HFS調度問題的多目標優化算法。

鑒于此，本文提出了一種改進的MOEA/D優化算法，用于求解多目標HFS調度問題，主要貢獻在于：①設計了兩種局部搜索策略，特別是基于關鍵路徑的強化局部搜索策略，可以有效提高算法求解性能；②設計了一種全局搜索交叉算子；③設計了一種種群更新策略，可以有效提高算法解的分布均勻性；④最小化3個目標，即最大完工時間目標，提前懲罰量和滯后懲罰量。

1 算法框架

1.1 編碼和解碼

HFS調度問題的定義和模型請參見文獻[12,13]。采用簡單工序排列編碼方式[5,6]，即按照工件編號進行排列的編碼方式。譬如，給定一個編碼{1,2,3,7,8,9,4,5,6}，其對應的含義為：在第一個加工階段，按照各工件在解中的位置次序先后調度，首先調度工件J1，之后J2，最后調度工件J6。進入下一個加工階段后，工件按照在上一個加工階段的完工時間從小到大進行排列，按照先來先服務的策略安排工件在下一個加工階段加工。

1.2 種群初始化

初始化策略采用隨機方法[13]，即隨機生成PS個互不相同的初始解。

1.3 局部搜索策略

1.3.1 變異算子

針對采用基于排列編碼的解，常采用的鄰域生成策略主要有交換鄰域、插入鄰域等[5,6]。不同的鄰域結構具備不同的挖掘和搜索能力，對于全局搜索和局部搜索的貢獻則不同。本文采用隨機選擇交換鄰域和插入鄰域的策略，即產生一個新解時，隨機選擇交換鄰域和插入鄰域的一種作為變異操作算子。

1.3.2 基于關鍵路徑的強化局部搜索策略

基于文獻[26]給出的關鍵路徑規則，設計基于關鍵路徑的強化局部搜索策略，描述如下：

步驟1 針對當前解，劃分加工關鍵塊，即，每個關鍵塊中的工件處于關鍵路徑上。

步驟2 隨機選擇處于關鍵塊中的兩個工件編號，判斷是否符合縮減鄰域的條件之一，若符合，則按照縮減鄰域規則，執行插入操作；否則，結束本次局部搜索，保持當前解不變。

1.4 全局搜索策略

為保證交叉操作的學習性和多樣性，本算法給出了一種改進的交叉操作算子，具體描述如下：

步驟1 隨機選擇兩個父代個體p1和p2，并隨機選擇兩個位置r1和r2；

步驟2 填充兩個子代個體c1和c2，使得它們在位置[r1,r2]部分的元素分別取自于p2和p1的對應位置；

步驟3 填充子代個體c1剩余部分，填充規則為：依次遍歷父代個體p1的所有元素，若該元素尚未在子代個體c1中出現，則填充到第一個空白位置；子代個體c2剩余部分的填充規則與上述步驟相同。

交叉算子的示例如圖1所示。

圖1 交叉算子

1.5 多目標改進策略

1.5.1 權重向量生成策略

1.5.2 種群更新策略

當生成的子代個體加入下一代種群后，種群的大小會發生變化，為保持種群規模不變，需要淘汰劣解。淘汰解的策略在多目標優化算法中是一個研究熱點。基于PBI值的大小是一種比較經典的策略[23]。然而，上述策略并不能保證一定保留Pareto較優解。譬如，圖2給出了在給定的權重向量區域下，兩個候選解x4和x5所在的位置，圖中可見x4的PBI值大于x5的PBI值，因而，保留x5。然而，按照Pareto分層策略，x4相比x5具備更低的Pareto層，因而應保留Pareto較優解x4。基于上述分析，本文采用Pareto分層和PBI值比較相結合的策略，給出了一種新的種群更新策略，步驟如下：

步驟1 分別計算候選解的PBI值和Pareto層級；

步驟2 若兩個候選解處于相同Pareto層級，則保留PBI值較小者；若候選解處于不同Pareto層級，則選擇層級較小者。

圖2 權重向量區域

1.6 算法整體框架

基于上述策略，給出了本文所提出的改進的MOEA/D優化算法框架(I-MOEAD)，具體算法步驟如下：

步驟1 初始化參數、權重向量和初始種群；

步驟2 初始化Pareto外部解集PAS；

步驟3 判斷結束條件是否滿足，若是，則輸出PAS，算法結束；否則，執行步驟4～步驟6。

步驟4 局部搜索策略

(1)遍歷當前種群的所有解，執行1.3.1節給出的變異操作算子；

(2)遍歷PAS中的所有解，執行1.3.2節給出的強化局部搜索算子；

步驟5 全局搜索策略：循環如下步驟PS/2次：隨機選取兩個父代個體，執行1.4節給出的交叉算子；

步驟6 種群更新

(1)當前種群全部個體執行快速非支配排序過程，進行Pareto分層；

(2)計算所有個體的PBI值

(3)按照1.5.2節給出的種群更新策略進行候選解的選擇，生成下一代種群。同時更新PAS。

(4)跳轉到步驟2。

2 實驗分析

2.1 實驗參數設置

本文所給出的算法主要參數設置如下：權重向量步長σ=0.1，種群大小PS=66，算法終止條件為運行時間100 s。

算法采用VC++編程，在i7 3.4-GHz，16 GB內存PC上獨立運行30次，獲得的運行結果進行實驗分析。

2.2 實驗算例生成

某煉鋼廠設備配置和加工階段見表1：①兩臺連鑄機分別可加工兩個澆次，該生產期間內共加工4個澆次；②每個澆次分別連續加工5個爐次，該生產期間內共加工20個爐次；③爐次在每個加工階段其加工時間在[35,50]之間隨機選取。

表1 某煉鋼廠設備

基于上述實際生產數據，隨機生成20個算例驗證本文給出的多目標優化算法。

2.3 對比算法

本文選取同樣基于MOEA/D的兩種算法進行對比分析，即DBEA[24]和EADD[25]。由于上述兩種算法是針對連續優化問題，因而本文對其進行重新編碼，選取文獻給出的參數，以求解多目標HFS調度問題。對比指標采用國際通用的超平面體積(Hypervolume，HV)和反轉世代距離(inverted generational distance，IGD)[23-25]。

2.4 實驗結果分析

針對隨機生成的20個算例，對比結果見表2，表3。由表2可見：①本文給出的I-MOEAD方法在所有的20個隨機算例中表現了良好性能，取得了較好解；②平均性能來看，I-MOEAD算法明顯優于其它兩個對比算法；③HV值的比較結果，驗證了本文所提出算法的有效性，也驗證了所得結果結合的收斂能力和解的多樣性。

由表3可見：①本文給出的I-MOEAD方法在所有的20個隨機算例中均取得了較優解；②平均性能來看，I-MOEAD算法明顯優于其它兩個對比算法；③IGD值的比較結果，進一步驗證了本文所提出算法的有效性。

I-MOEAD算法性能優于其它兩種比較算法的主要原因分析如下：①全局搜索策略提高了算法求解的多樣性和分散性；②兩種局部搜索策略，特別是基于關鍵路徑的強化局部搜索策略，進一步提高了算法性能；③種群更新策略，在保持解集質量的前提下，進一步提高了種群的多樣性。

3 結束語

為求解多目標HFS調度問題，本文給出了一種改進的MOEA/D優化算法，主要貢獻在于：①提出了兩種局部搜索策略，即基于交換、插入鄰域的局部搜索和基于關鍵路徑的強化局部搜索策略，提高了算法求解的性能。②設計了一種新的交叉算子，提高了算法全局搜索的能力。③設計了一種種群更新策略，進一步提高了算法解集的分布均勻性。

表2 HV值的比較結果

表3 IGD值的比較結果

[1]TIAN Yunna,LI Dongni,ZHENG Dan,et al.A time window-based approach for multi-stage hybrid flow shop[J].Chinese Journal of Mechanical Engineering,2016,52(16):185-196(in Chinese).[田云娜,李冬妮,鄭丹,等.一種基于時間窗的多階段混合流水車間調度方法[J].機械工程學報,2016,52(16):185-196.]

[2]WANG Shengyao,WANG Ling,XU Ye,et al.An estimation of distribution algorithm for solving hybrid flow-shop sche-duling problem[J].ACTA Automatica Sinica,2012,38(3):437-443(in Chinese).[王圣堯,王凌,許燁,等.求解混合流水車間調度問題的分布估計算法[J].自動化學報,2012,38(3):437-443.]

[3]LIU Chang,LI Dong,PENG Hui,et al.EDA algorithm with correlated variables for solving hybrid flow-shop scheduling problem[J].Computer Integrated Manufacturing Systems CIMS,2015,21(4):1032-1039(in Chinese).[劉昶,李冬,彭慧,等.求解混合流水車間調度問題的變量相關EDA算法[J].計算機集成制造系統,2015,21(4):1032-1039.]

[4]Chou F D.Particle swarm optimization with cocktail decoding method for hybrid flow shop scheduling problems with multi-processor tasks[J].International Journal of Production Economics,2013,141(1):137-145.

[5]Pan Q K,Dong Y.An improved migrating birds optimisation for a hybrid flowshop scheduling with total flowtime minimisation[J].Information Sciences,2014,277(2):643-655.

[6]Pan Q K,Wang L,Li J Q,et al.A novel discrete artificial bee colony algorithm for the hybrid flowshop scheduling problem with makespan minimisation[J].Omega,2014,45(2):42-56.

[7]LI Junqing,PAN Quanke,WANG Fatao.Solving hybrid flow-shop scheduling problems by a hybrid discrete artificial bee colony algorithm[J].Operations Research & Management Science,2015,24(1):157-163(in Chinese).[李俊青,潘全科,王法濤.求解混合流水線調度問題的離散人工蜂群算法[J].運籌與管理,2015,24(1):157-163.]

[8]Marichelvam M K,Prabaharan T,Yang X S.Improved cuckoo search algorithm for hybrid flow shop scheduling problems to minimize makespan[J].Applied Soft Computing,2014,19(1):93-101.

[9]LI Zhicong,GU Xingsheng.Improved biogeography-based optimization algorithm used in solving hybrid flow shop scheduling problem[J].CIESC Journal,2016,67(3):751-757(in Chinese).[李知聰,顧幸生.改進的生物地理學優化算法在混合流水車間調度中的應用[J].化工學報,2016,67(3):751-757.

[10]Savsani P,Jhala R L,Savsani V.Effect of hybridizing bio-geography-based optimization (BBO) technique with artificial immune algorithm (AIA) and ant colony optimization (ACO)[J].Applied Soft Computing,2014,21(5):542-553.

[11]Chamnanlor C,Sethanan K,Gen M,et al.Embedding ant system in genetic algorithm for re-entrant hybrid flow shop scheduling problems with time window constraints[J/OL].[2015-04-24].https://link.springer.com/article/10.1007%2Fs10845-015-1078-9.

[12]Pan Q K,Gao L,Li X Y,et al.Effective metaheuristics for scheduling a hybrid flowshop with sequence-dependent setup times[J].Applied Mathematics & Computation,2017,303(6):89-112.

[13]Li J Q,Pan Q K.Solving the large-scale hybrid flow shop scheduling problem with limited buffers by a hybrid artificial bee colony algorithm[J].Information Sciences,2015,316(C):487-502.

[14]Hou Y,Wu N Q,Zhou M C,et al.Pareto-optimization for scheduling of crude oil operations in refinery via genetic algorithm[J].IEEE Transactions on Systems Man & Cyberne-tics Systems,2017,47(3):517-530.

[15]Zhou A,Zhang Q.Are all the subproblems equally important?Resource allocation in decomposition-based multiobjective evolutionary algorithms[J].IEEE Transactions on Evolutionary Computation,2016,20(1):52-64.

[16]Wang J,Zhang W,Zhang J.Cooperative differential evolution with multiple populations for multiobjective optimization[J].IEEE Transactions on Cybernetics,2016,46(12):2848-2861.

[17]Chen Y,Mahalec V,Chen Y,et al.Reconfiguration of satellite orbit for cooperative observation using variable-size multi-objective differential evolution[J].European Journal of Ope-rational Research,2015,242(1):10-20.

[18]ZUO Xingquan,WANG Chunlu,ZHAO Xinchao.Combining multi-objective immune algorithm and linear programming for double row layout problem[J].ACTA Automatica Sinica,2015,41(3):528-540(in Chinese).[左興權,王春露,趙新超.一種結合多目標免疫算法和線性規劃的雙行設備布局方法[J].自動化學報,2015,41(3):528-540.]

[19]Wang X,Tang L.A machine-learning based memetic algorithm for the multi-objective permutation flowshop scheduling problem[J].Computers & Operations Research,2017,79(3):60-77.

[20]Long J,Zheng Z,Gao X,et al.A hybrid multi-objective evo-lutionary algorithm based on NSGA-II for practical scheduling with release times in steel plants[J].Journal of the Operational Research Society,2016,67(9):1184-1199.

[21]Lin J,Liu M,Hao J,et al.A multi-objective optimization approach for integrated production planning under interval uncertainties in the steel industry[J].Computers & Operations Research,2016,72(C):189-203.

[22]Gen M,Zhang W,Lin L,et al.Recent advance in hybrid evolutionary algorithms for multiobjective manufacturing scheduling[J/OL].[2017-01-17].http://www.sciencedi-rect.com/science/article/pii/S036083521630523X.

[23]Li K,Deb K,Zhang Q,et al.Efficient nondomination level update method for steady-state evolutionary multiobjective optimization[J/OL].[2016-11-08].http://ieeexplore.ieee.org/document/7738460/.

[24]Asafuddoula M,Ray T,Sarker R.A decomposition-based evolutionary algorithm for many objective optimization[J].IEEE Transactions on Evolutionary Computation,2015,19(3):445-460.

[25]LiK,Deb K,Zhang Q,et al.An evolutionary many-objective optimization algorithm based on dominance and decomposition[J].IEEE Transactions on Evolutionary Computation,2015,19(5):694-716.

[26]Yazdani M,Gohari S,Naderi B.Multi-factory parallel machine problems:Improved mathematical models and artificial bee colony algorithm[J].Computers & Industrial Enginee-ring,2015,81:36-45.