求解擴展雙資源約束作業車間調度的分支種群遺傳算法

李兢堯, 黃媛, 王軍強, 郭陽明

?

求解擴展雙資源約束作業車間調度的分支種群遺傳算法

李兢堯1, 黃媛2, 王軍強3, 郭陽明4

摘要：根據擴展雙資源約束作業車間調度問題的特點,構造了一種混合遺傳算法進行求解:以分支種群為載體繼承遺傳進化經驗,利用精英進化算子、基于扇形分割的輪盤賭選擇算子及鄰域搜索等機制,進一步優化了算法性能。通過分析策略對比仿真、算法性能對比仿真等實驗,結果表明上述各種優化機制可行,且對于算法運算效率與尋優性能的優化效果均有良好表現。

關鍵詞：調度算法;擴展雙資源約束;作業車間調度;分支種群;精英進化;扇形分割;鄰域搜索

雙資源約束作業車間調度問題(dual resource constrained job shop scheduling problem,DRCJSP)是一類特殊的柔性作業車間調度問題,同時考慮了設備、工人兩類資源的能力約束。相對于經典FJSP問題,DRCJSP的調度靈活性及資源配置選擇更多,更接近實際生產調度環境,是迫切需要解決的NP-Hard問題。

Elmaraghy等[1]基于同時考慮雙資源任務分配的染色體表達形式,用遺傳算法(genetic algorithm,GA)求解DRCJSP與JSP,得到針對不同指標的最佳分派規則。周炳海等[2]將DRCJSP問題分解為雙資源的分配優化問題與作業序列優化問題2個子問題,然后分別采用基于分派規則與作業塊右移規則的GA算法求解上述2個子問題。陶澤等[3]基于帶有控制器的Petri網為動態DRCJSP建模,靈活使用GA算法、SA算法、再分配策略等應對各類動態事件。陳勇等[4]針對考慮不確定訂單的雙資源約束多裝配線,提出了一種基于差分進化算法和粒子群算法的混合優化算法,并驗證了其可行性和有效性。Araz等[5]基于人工神經網絡建立了DRCJSP實時調度模型,有效降低了計算復雜度,但其性能易受到初選分派規則集合和人工神經網絡模型準確性的影響。

縱觀現有研究,應用智能算法求解DRCJSP問題雖已獲得一定成果,但依然存在3點不足:①采用從單一種群出發,不斷逼近最優個體的進化模式,優化結果過分依賴初始群體質量;②進化算子僅針對工序信息,缺乏資源配置相關的進化操作;③現有的DRCJSP研究對零件批次、準備時間等影響實際生產調度的因素考慮較少。針對上述問題,作者前期已展開了一系列研究,先后提出了蟻群-退火混合算法[6]和繼承式遺傳算法[7]求解DRCJSP問題,但前者優化雙目標時效果不佳,后者有進一步優化Pareto解集分布均勻程度的空間。

本文針對EDRCJSP問題的多類約束及柔性工藝特點,在文獻[8]的算法基礎上,引入精英進化與鄰域局部搜索等機制進一步優化其全局搜索性能,并通過一系列仿真算例與實例驗證了各個優化機制的先進性和算法的有效性。

1問題描述

2BPGA算法研究

2.1算法設計

分支種群遺傳算法(branch population genetic algorithm,BPGA)將每個工序的多道工藝路線視作多條分支路徑。每次迭代前,根據路徑信息素及啟發式信息生成染色體分支種群,與當代染色體共同進化。一方面以分支種群為載體繼承之前各代種群的“生存經驗”,客觀反映工序調度次序及工藝選擇對于調度指標的影響,正確引導種群的進化及搜索方向;另一方面,通過引入外部染色體增強進化種群的多樣性,既可避免算法早熟,又拓展了算法的全局搜索能力。此外,BPGA算法通過以下3種機制,進一步優化算法性能:①精英進化策略,鼓勵較優個體間的交叉、變異,以較小運算量得到更優的進化結果;②基于扇形分割的選擇算子,在選擇存活種群的同時,兼顧種群均勻分布;③構建基于工序關鍵路徑的鄰域結構進行鄰域搜索,增強全局搜索能力。

2.2算法關鍵技術

1) 分支種群

(1)

2) 精英進化

根據文獻[8]得到的結論：當至少一個調度指標優于種群均值的染色體經過交叉變異進化后，有較大幾率得到非劣解，并對種群質量有明顯優化。在此基礎上，BPGA算法提出鼓勵精英個體繁殖變異的精英進化算子：提取父輩種群中至少有一個調度指標超過種群目標均值的染色體，構成精英種群，僅對該種群與保存每次迭代非劣解的伴隨種群進行下列進化操作；其余染色體直接進入子輩種群接受選擇，以增強種群多樣性。

(1) 精英交叉

篩選精英種群、伴隨種群中雙目標均超過種群均值的個體共同組成King種群，每個King染色體與其他所有King染色體以及任意2個非King精英染色體基于POX交叉算子[10]進行交叉進化。

(2) 精英變異

BPGA算法建立包含設備交叉、工人交叉、資源組合變異等資源變異算子[11]與互反變異、插入變異等工序變異算子在內的復合變異策略庫。每個King染色體執行策略庫中所有變異策略以增加得到非劣解的可能性；剩余的非King精英個體分別選擇一種策略執行，避免算法早熟。

(3) 時間復雜度分析

對于每次迭代，假設進化種群、分支種群、非劣解集的數量分別為Nevo、Nant、Np。如采用全進化模式，其運算復雜度為：O(Nevo+2Nevo+4Nevo+8Nevo)=O(15Nevo)。根據Pareto支配關系定義，King種群規模約為0.25Nevo，非King精英種群規模約為0.5Nevo，則精英交叉進化的運算復雜度為O(Nant×0.5Nevo)+O(Nevo),精英變異過程中每個King染色體進行5種變異，運算復雜度為O(1.25Nevo)，非King精英個體僅執行一種變異，運算復雜度為O(0.5Nevo)。因此整個精英進化過程的運算復雜度為O(Nant×0.5Nevo+2.75Nevo),當Nant×0.5Nevo<12.25Nevo，即Nant<24.5時精英進化策略的運算復雜度小于全進化模式。

3) 基于扇形分割的輪盤賭選擇算子

每個解在目標空間中表現為一個點，它與原點的連線和坐標橫軸構成的夾角θ能夠體現解在解空間內的分布。BPGA算法確定非劣伴隨種群后，通過基于扇形分割的輪盤賭法，從存活種群中選擇優秀且分布均勻的解共同構成進化種群，具體步驟為：①首先找到Cp或Td最優的2個極值個體；②分別用線連接2個極值點與原點，形成一個扇形解區域；③將該扇形區域按角度N等分；④依角度順序從每個小扇形區域中選擇一個解進入進化種群Pevolution，如該區域有多個解，則根據解離原點的距離，按輪盤賭方法進行選擇，直至Pevolution規模達到N為止。

4) 鄰域結構搜索

解鄰域結構設計一直是鄰域搜索的關鍵問題與難點所在，關鍵路徑法是最常用的一種鄰域結構生成方式，其中關鍵工序與關鍵路徑的準確定位成為鄰域搜索在JSP調度中取得顯著優化效果的基礎。潘全科等[12]指出：全局最優解是所有鄰域結構的局部最優解，且一種鄰域結構的局部最優解往往會在另一種鄰域結構的局部最優解附近。Chu[13]提出交換關鍵工序塊上的相鄰工序不會影響調度方案的可行性。Nowicki[14]指出只有關鍵工序塊的前2個或后2個相鄰關鍵工序的交換能夠優化調度時間指標。

由現有的研究結果可以看出，緊前關鍵工序的確定是鄰域搜索的基礎。例如，對于EDRCJSP調度中的某道工序，假定其緊前工序共有4種可能，以圖1為例：①在同一臺設備上連續加工，工序“2-1-2”為“1-1-2”的緊前工序；②同一個工人連續加工，“3-1-3”為“1-1-3”的緊前工序；③同一批次的同一工件的2道緊鄰工序，如“4-1-2”與“4-1-1”；④同一個工人在數控機床為某個任務上料后立即轉移到其他設備上加工另一個任務，如“3-1-2”與“2-1-2”。

圖1　EDRCJSP調度方案示意圖

借鑒上述基于關鍵路徑的鄰域結構搜索思想，BPGA算法在每次遺傳進化后，均對每個非劣解所代表的調度方案從最后一道完成工序開始，按上述4個條件的優先順序，從后向前尋找關鍵工序，據此可最終得到關鍵路徑。可將其中由同一資源組合連續加工的多個關鍵工序稱為雙資源約束關鍵塊，并據此設計下列3種鄰域結構，共同構成鄰域種群Pneighbour，與其他染色體共同參與進化選擇。

1) 第1鄰域：將隨機關鍵工序的加工資源組合更換為效率最高或成本最低組合。

2) 第2鄰域：將關鍵塊的前兩道工序或最后兩道工序互換構成的所有鄰域。

3) 第3鄰域：如某個關鍵塊中存在不同批次的同工序任務非連續加工，則將較晚開工的任務提前，實現工序合批加工。

3仿真試驗及分析

3.1優化機制性能仿真分析

本文基于文獻[11]構造的EDRCJSP隨機算例，采用文獻[8]的評價指標，分別對分支種群等幾種優化機制引入前后的數據進行分析，驗證其優化效果。

1) 分支種群優化效果

圖2　分支種群對種群差異度的影響

圖3　有無分支種群的最終調度結果

2) 精英進化模式

圖4　不同進化模式的非劣解集I對比　圖5　不同進化模式的非劣解集Arange對比　圖6　不同進化模式的非劣解集SΔA對比

由圖6可見，精英進化算子偏重在優秀解空間的搜索， 指標相對穩定，全進化模式則隨著算法收斂有一個明顯的 下降過程。圖7所示為使用2種進化模式的BPGA算法分別運算同一算例所得結果，全進化模式通過更大規模的運算，算法全局搜索能力更強，非劣解集覆蓋范圍更大，但最終解集在中間與兩端區域分布較密集；精英進化模式的求解結果更趨近于Pareto前沿，雖然覆蓋范圍略小，但分布更為均勻。

圖7　不同模式的最終非劣解集對比

3) 基于扇形分割的輪盤賭選擇算子

圖8　不同選擇算子的I對比　　　圖9　不同選擇算子的Arange對比　　　圖10　不同選擇算子的SΔA對比

圖11　不同選擇算子的混合指標對比

3.2算法性能對比

本文采用文獻[8]中的DOIGAII算法和經典多目標進化算法NSGAII[16]作為對比算法，分別運算10組EDRCJSP隨機算例20次，并比較結果均值的4種非劣性能評價指標，如表1所示。

DOIGAII算法與BPGA算法的 明顯優于NSGAII算法，可見精英進化算子能顯著優化BPGA算法的局部搜索能力；而BPGA的 除了算例4和8均優于DOIGAII算法，鄰域搜索機制使搜索空間更加逼近Pareto前沿。NSGAII算法使用基于小生境技術的Pareto等級排序，側重于搜索雙目標極值區域，解覆蓋范圍最大；由于搜索非劣解鄰域，BPGA算法的解搜索范圍優于DOIGAII算法。但由于引入分支種群，種群多樣性得到優化，非劣解集的分布均勻性由于扇形分割選擇算子得到有效優化，因此DOIGAII算法與BPGA算法的解集分布更加均勻，且兩者不相伯仲。對絕大部分算例，DOIGAII算法與BPGA算法的混合指標均優于NSGAII算法；相比DOIGAII算法，BPGA算法的不僅更優秀而且更加穩定。綜上所述，雖然NSGAII算法搜索范圍較廣，但DOIGAII算法與BPGA算法的搜索范圍更加逼近Pareto前沿，且由于精英進化算子與鄰域搜索機制的引入，BPGA算法具有更為優秀的魯棒性與全局搜索性能。

表1　算法性能比較

4結論

本文旨在為EDRCJSP雙目標調度優化問題的特點，在遺傳算法基礎上，通過引入分支種群、精英進化算子、基于被支配域的非劣解集快速優選算子、基于扇形分割的輪盤賭選擇算子、鄰域搜索等性能優化機制，構造一種BPGA算法。通過各種仿真對比實驗，驗證了各種優化機制在算法運算效率、局部搜索能力、解分布均勻程度等方面均能得到有效優化，并通過算法性能對比試驗進一步驗證了用BPGA算法求解EDRCJSP問題的有效性與可行性。

參考文獻：

[1]Elmaraghy H, Patel V, Abdallah I B. Scheduling of Manufacturing Systems under Dual-Resource Constraints Using Genetic Algorithms[J]. Journal of Manufacturing Systems, 2000, 19(3): 186-201

[2]周炳海, 蔣舒宇, 何平, 等. 基于雙重資源的柔性生產系統調度算法[J]. 華南理工大學學報, 2008, 36(4): 45-49

Zhou Binghai, Jiang Shuyu, He Ping, et al. Scheduling Algorithm of Flexible Production System Based on Dual Resource[J]. Journal of South China University of Technology, 2008, 36(4): 45-49 (in Chinese)

[3]陶澤, 隋天中, 謝里陽,等. 基于Petri網和GASA的雙資源JSP動態優化調度[J]. 東北大學學報, 2007, 28(3): 405-409

Tao Ze, Sui Tianzhong, Xie Liyang, et al. Dynamic Scheduling Optimization of Dual-Resource Based on Petri Net and GASA[J]. Journal of Northeastern University, 2007, 28(3): 405-409 (in Chinese)

[4]陳勇, 吳云翔, 王亞良. 訂單不確定下雙資源約束多裝配線魯棒調度[J]. 中國機械工程, 2014, 25(12): 1567-1573

Chen Yong, Wu Yunxiang, Wang Yaliang. Multi-Assembly Line Robust Scheduling of Double Resource Constrains under Uncertain Orders[J]. China Mechanical Engineering, 2014, 25(12): 1567-1573 (in Chinese)

[5]Araza U, Salum L. A Multi-Criteria Adaptive Control Scheme Based on Neural Networks and Fuzzy Inference for DRC Manufacturing Systems[J]. International Journal of Production Research, 2010, 48(1): 251-270

[6]李兢堯，孫樹棟，黃媛，等. 雙資源約束作業車間調度算法研究[J]. 機械工程學報, 2010, 46(22): 175-181

Li Jingyao, Sun Shudong, Huang Yuan, et al. Algorithm for Dual Resource Constrained Job Shop Scheduling[J]. Journal of Mechanical Engineering, 2010, 46(22): 175-181 (in Chinese)

[7]李兢堯，孫樹棟，黃媛，等. 求解雙資源約束車間調度問題的繼承式雙目標遺傳算法[J]. 控制與決策, 2011, 26(12): 1761-1767

Li Jingyao, Sun Shudong, Huang Yuan, et al. Double Objective Inherited Genetic Algorithm for Dual Resource Constrained Job Shop[J]. Control and Decision, 2011, 26(12): 1761-1767 (in Chinese)

[8]李兢堯，孫樹棟，黃媛，等. 基于時窗的雙資源約束車間調度研究[J]. 機械工程學報, 2011, 46(22): 150-159

Li Jingyao, Sun Shudong, Huang Yuan, et al. Research on Dual Resource Constrained Job Shop Scheduling Based on Time Window[J]. Journal of Mechanical Engineering, 2011, 46(22): 150-159 (in Chinese)

[9]李兢堯，孫樹棟，黃媛，等. 基于自適應參數混合蟻群算法的雙資源約束作業車間調度[J]. 西北工業大學學報, 2011, 29(1): 54-61

Li Jingyao, Sun Shudong, Huang Yuan, et al. Solving Dual Resource Constrained Job-Shop Scheduling Problem(DRCJSP) Based on Hybrid Ant Colony Algorithm with Self-Adaptive Parameters[J]. Journal of Northwestern Polytechnical University, 2011, 29(1): 54-61 (in Chinese)

[10] 張超勇, 饒運清, 李培根. 柔性作業車間調度問題的兩級遺傳算法[J]. 機械工程學報, 2007, 43(4): 119-124

Zhang Chaoyong, Rao Yunqing, Li Peigen. Bilevel Genetic Algorithm for the Flexible Job-Shop Scheduling Problem[J]. Chinese Journal of Mechanical Engineering, 2007, 43(4): 119-124 (in Chinese)

[11] Jingyao L, Shudong S, Yuan H. Dual Resource Constrained Job Shop Scheduling Based on Time Window[J]. Chinese Journal of Mechanical Engineering, 2011, 47(16): 150-159

[12] 潘全科, 王文宏, 朱劍英. 基于粒子群優化和變鄰域搜索的混合調度算法[J]. 計算機集成制造系統, 2007, 13(2): 323-329

Pan Quanke, Wang Wenhong, Zhu Jianying. Hybrid Heuristics Based on Particle Swarm Optimization and Variable Neighborhood Search for Job Shop Scheduling[J]. Computer Integrated Manufacturing Systems, 2007, 13(2): 323-329 (in Chinese)

[13] Chu C, Proth J M, Wang C. Improving Job Shop Schedules Through Critical Pairwise Exchanges[J]. International Journal of Production Research, 1998, 36(3): 683-694

[14] Nowicki E, Smutnicki C. A Fast Taboo Search Algorithm for the Job Shop Scheduling[J]. Management Science, 1996, 42(6): 797-813

[15] Doerner K, Gutjahr W, Hartl R, et al. Pareto Ant Colony Optimization: A Metaheuristic Approach to Multiobjective Portfolio Selection[J]. Annals of Operations Research, 2004, 131(1): 79-99

[16] 張勇德, 黃莎白. 多目標優化問題的蟻群算法研究[J]. 控制與決策, 2005, 20(2): 170-176

Zhang Yongde, Huang Shabai. On Ant Colony Algorithm for Solving Multiobjective Optimization Problems[J]. Control And Decision, 2005, 20(2): 170-176 (in Chinese)

Branch Population Genetic Algorithm for Extension Dual Resource Constrained Job Shop Scheduling Problem

Li Jingyao1, Huang Yuan2, Wang Junqiang3, Guo Yangming4

1.Research Institute of 365,Northwestern Polytechnical University, Xi′an 710065, China 2.School of Mechanical Engineering, Northwestern Polytechnical University, Xi′an 710072, China 3.Institute of System Integrated and Engineering Management, Northwestern Polytechnical University, Xi′an 710072, China 4.School of Computer, Northwestern Polytechnical University, Xi′an 710072, China

Abstract:In this paper, a hybrid genetic algorithm was proposed for solving extension dual resource constrained job shop scheduling problem. The algorithm was constructed based on inheriting evolution experience of parent population with the branch population. In addition, this algorithm used some optimization operators to optimize algorithm performance, such as the elite evolutionary operator, the roulette selection operator based on sector partition, the variable neighbourhood search operator, and so on. Finally, the optimization performances of above mechanisms were validated according to the statistical analysis on the simulation results of strategies comparison simulation and algorithm performance comparison simulation.

Keywords:scheduling algorithm; extension dual resource constrained; job shop scheduling; branch population; elite evolutionary; sector partition; neighborhood search

收稿日期：2015-10-12

基金項目：國家自然科學基金(51275421)和西北工業大學基礎研究基金(JC20120227)資助

作者簡介：李兢堯(1984—),西北工業大學講師,主要從事智能算法及調度優化研究。

中圖分類號：TP18

文獻標志碼：A

文章編號:1000-2758(2016)04-0635-07