求解擴展雙資源約束作業(yè)車間調(diào)度的分支種群遺傳算法

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

?

求解擴展雙資源約束作業(yè)車間調(diào)度的分支種群遺傳算法

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

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

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

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

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

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

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

1問題描述

2BPGA算法研究

2.1算法設計

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

2.2算法關鍵技術

1) 分支種群

(1)

2) 精英進化

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

(1) 精英交叉

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

(2) 精英變異

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

(3) 時間復雜度分析

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

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

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

4) 鄰域結(jié)構(gòu)搜索

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

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

圖1　EDRCJSP調(diào)度方案示意圖

借鑒上述基于關鍵路徑的鄰域結(jié)構(gòu)搜索思想，BPGA算法在每次遺傳進化后，均對每個非劣解所代表的調(diào)度方案從最后一道完成工序開始，按上述4個條件的優(yōu)先順序，從后向前尋找關鍵工序，據(jù)此可最終得到關鍵路徑?？蓪⑵渲杏赏毁Y源組合連續(xù)加工的多個關鍵工序稱為雙資源約束關鍵塊，并據(jù)此設計下列3種鄰域結(jié)構(gòu)，共同構(gòu)成鄰域種群Pneighbour，與其他染色體共同參與進化選擇。

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

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

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

3仿真試驗及分析

3.1優(yōu)化機制性能仿真分析

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

1) 分支種群優(yōu)化效果

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

圖3　有無分支種群的最終調(diào)度結(jié)果

2) 精英進化模式

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

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

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

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

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

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

3.2算法性能對比

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

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

表1　算法性能比較

4結(jié)論

本文旨在為EDRCJSP雙目標調(diào)度優(yōu)化問題的特點，在遺傳算法基礎上，通過引入分支種群、精英進化算子、基于被支配域的非劣解集快速優(yōu)選算子、基于扇形分割的輪盤賭選擇算子、鄰域搜索等性能優(yōu)化機制，構(gòu)造一種BPGA算法。通過各種仿真對比實驗，驗證了各種優(yōu)化機制在算法運算效率、局部搜索能力、解分布均勻程度等方面均能得到有效優(yōu)化，并通過算法性能對比試驗進一步驗證了用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]周炳海, 蔣舒宇, 何平, 等. 基于雙重資源的柔性生產(chǎn)系統(tǒng)調(diào)度算法[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網(wǎng)和GASA的雙資源JSP動態(tài)優(yōu)化調(diào)度[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]陳勇, 吳云翔, 王亞良. 訂單不確定下雙資源約束多裝配線魯棒調(diào)度[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]李兢堯，孫樹棟，黃媛，等. 雙資源約束作業(yè)車間調(diào)度算法研究[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]李兢堯，孫樹棟，黃媛，等. 求解雙資源約束車間調(diào)度問題的繼承式雙目標遺傳算法[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]李兢堯，孫樹棟，黃媛，等. 基于時窗的雙資源約束車間調(diào)度研究[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]李兢堯，孫樹棟，黃媛，等. 基于自適應參數(shù)混合蟻群算法的雙資源約束作業(yè)車間調(diào)度[J]. 西北工業(yè)大學學報, 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] 張超勇, 饒運清, 李培根. 柔性作業(yè)車間調(diào)度問題的兩級遺傳算法[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] 潘全科, 王文宏, 朱劍英. 基于粒子群優(yōu)化和變鄰域搜索的混合調(diào)度算法[J]. 計算機集成制造系統(tǒng), 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] 張勇德, 黃莎白. 多目標優(yōu)化問題的蟻群算法研究[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)和西北工業(yè)大學基礎研究基金(JC20120227)資助

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

中圖分類號：TP18

文獻標志碼：A

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