改進遺傳算法求解織造車間并行批調度問題

杜利珍，葉 濤，宣自風，王宇豪

改進遺傳算法求解織造車間并行批調度問題

杜利珍，葉 濤，宣自風，王宇豪

（武漢紡織大學 機械工程與自動化學院，湖北 武漢 430200）

針對織造車間并行批處理調度問題，提出一種改進遺傳算法用于最大完工時間最小化求解。首先，采用實數編碼方式進行編碼操作；然后，引入模擬退火算法的Metropolis機制，從而增強遺傳算子在該調度問題的可行解集空間中尋優的能力；最后，通過隨機生成的150個仿真測試集對算法進行求解性能上的比較分析，并將測試結果與文獻中提到的BSNRPSO算法和另外一種差分進化算法進行比較分析。經過實驗證明，本文改進遺傳算法在求解性能上明顯優于對比算法。

遺傳算法；實數編碼；Metropolis機制；織造車間

批調度屬于車間調度問題的一個重要的分支，在制造業生產過程中也有廣泛應用，如半導體制造[1]、晶圓制造、紡織車間等。國內不少學者就該方向進行了不少研究，現階段針對該研究采用的方法大多是針對某算法的缺點，通過分析后將其他算法規則融入到該算法中進行對應問題的求解，從而有效的避免收斂過快等缺點。Jia等[2]針對具有任意容量的并行批處理機上的調度問題，以總加權交付時間最小化為目標，提出了改機蟻群算法(UACO)和粒子群算法(PSO)和一種元啟發式算法，解決需要考慮作業和批次之間關系情況下的排產調度問題，經過實驗證明，文中提出的此方法在求解性能上優于其他算法。Jia等[3]針對在模糊環境下不同容量下并行批處理機器的調度問題，以最大完工時間最小化為目標，提出了一種模糊的蟻群算法解決了具有不相同作業大小和模糊處理時間的調度優化問題，為提高解的質量，引入了FLO(Fuzzy Local Optimization)局部優化算法，通過模糊實驗和統計測試證明，該提出的算法在合理的時間內能找到更好的解。?？×值萚4]針對并行多機批調度問題展開研究，以最大完工時間最小化為目標，提出了一種基于批序列編碼的混合粒子群算法解決了該調度問題，在引入學習因子二階振蕩、隨機權重、最大速度線性遞減等方法后，有效避免了算法收斂速度慢及尋優能力差等問題。Zhou等[5]針對具有任意作業規模的均勻并行批處理機的調度問題，以最大限度的縮短完工時間為目的，提出了一種有效的基于差分進化算法(DE)來解決大規模問題，通過隨機生成的測試案例將其結果與商業解算器(MIP)、隨機密鑰遺傳算法(RKGA)和粒子群算法(PSO)進行比較，實驗結果證明了該算法在求解質量和魯棒性方面的優越性。

本文重點研究遺傳算法(Genetic Algorithm，GA)的優缺點，針對織造車間生產實際所存在的約束，建立混合整數線性規模型(MILP），將模擬退火算法(SA)的Metropolis準則引入到該算法中，以提高算子在可行解集空間中尋優的能力，最后通過隨機生成的150個測試案例進行該算法求解性能上的對比分析，經過實驗證明了此方法在求解能力上明顯優于其他對比算法。

1 織造車間并行批調度問題描述

本文以河南省杰瑞織造科技有限公司紡織服裝(毛衫)生產線作為研究對象，該服裝生產車間前道工序為：織片—套口—洗水—后整，洗水車間的工序為將“織片—套口”兩道工序處理后的毛衫制品按照不同類型進行分類，送洗水車間進行批次處理，該工序可以視作為一個并行批處理調度的問題。其生產過程實景圖如圖1所示。

圖1 生產實景

約束1為優化的目標函數；約束2為判斷批次中的工件是否在對應批處理機器上進行加工；約束3表示批次中工件的加工尺寸總和不能超過批處理機器的加工容量；約束4表示批次的加工時間為批中工件最大加工時間；約束5表示最大完成時間至少大于所有批次加工時間總和；約束6表示布爾變量的取值范圍。

2 算法設計

2.1 GA算法簡介

遺傳算法在車間調度領域已得到廣泛的使用。該算法自20世紀70年代由Holland提出，自此得到了廣泛的關注。遺傳算法已成功應用與解決各類復雜的組合優化問題，該算法是通過模仿自然界生物進化機制發展起來的隨機全局搜索和優化的方法，借鑒了達爾文的進化論及孟德爾的遺傳學說。遺傳算法的算子在其搜索過程中能夠做到自動獲取和積累搜索空間知識的特點，并自適應地控制其搜索過程以求得最佳解。

2.2 編解碼

所研究的調度問題屬于離散優化問題，遺傳算法屬于連續優化方法，通過實數編碼的方式將此問題轉化為連續型問題進行求解，其編碼原理通過隨機生成一組實數，將此數組與工件序列配對，通過基于該實數組的降序排列來規劃工件的加工次序，數組的長度表示工件的數目，具體如表1所示。

表1 實數編碼

如表1所示，通過第一行實數的排序間接的規定加工序列號，工件{1,2,3,4,5,6,7,8}經過編碼后的加工次序為I4、I6、I8、I7、I3、I2、I5、I8。

2.3 算法內操作

2.3.1 選擇操作

該遺傳算法的選擇操作采取“隨機聯賽選擇”機制，該機制主要通過從種群中隨機選擇幾個適應度最高的個體(編碼)，然后將其個體一個個的傳遞到子代種群中去，同時方便交叉、變異操作。

2.3.2 交叉操作

圖2 均勻交叉操作

2.3.3 變異操作

圖3 基本位變異

2.4 改進遺傳算法步驟及流程圖

改進遺傳算法的流程如圖4所示，步驟如下：

步驟1：初始化算法參數，主要包括：種群數量、交叉率、變異率、最大遺產代數。

步驟2：分別對算法的種群進行對應適應度值得求解。

步驟3：基于模擬退火算法的Metropolis機制，對原有的適應度值進行再次更新，其主要根據該機制在可行解集空間中尋得比當前解更優的解。

步驟4：基于“隨機聯賽選擇”機制，從種群中選取適應值最好幾個對應的個體，將其傳遞給子代。

步驟5：基于“均勻交叉”機制，對父代、母代個體進行概率交叉操作，增加種群的多樣性。

步驟6：基于“基本位變異”機制，對經過交叉后留下的子代(當前變異操作的新父代)進行概率性變異，增強種群的穩定性。

圖4 改進遺傳算法流程圖

步驟7：循環進行步驟2～步驟6，直到滿足終止條件(一般為最大迭代次數)，若滿足，則輸出最優個體及適應值，否則再次進入循環體，直到滿足終止條件。

2.5 運算復雜度

3 實驗仿真分析

為了測試改進遺傳算法在求解織造車間并行批調度問題上的性能，通過測試案例進行對應的仿真實驗，所有的算法代碼編寫均在Matlab R2016實現，操作系統為Window 7，處理器為Intel(R) Core(TM)i5-5200U CPU @ 2.20GHz。

表2 算例參數設置

表3 批調度測試結果

從表3中的數據可知，就算法的最優值、最差值、平均值進行比較，IGA算法在大多數情況下都比BSNPPSO的效果好，少數在工件數為50、150，加工時間在[1,20]情況下其求解效果較BSNRPSO差一點，相比于DE算法，其結果明顯優于DE算法求解的效果，為了更好的比較3種算法的性能優越性，采用相對改進率作為新的評價指標，改進遺傳算法(GA)相對于DE算法的改進率為：

根據公式（7），IGA算法相對于BSNRPSO算法和DE算法的平均值改進率結果見表4所示。并且根據表4的結果做出算法的平均值改進率圖，如圖5所示。

由圖4可知，IGA算法相對于DE在求解性能方面有一定的改進，但相對于BSNRPSO其改進不是很穩定，尤其表現在J2t1～J4t1這個區間，在區間J2t2～J4t2其改善相對穩定，這說明IGA在面對加工時間長、工件數多的情況下更能勝任，面對加工時間短、工件數多時存在一定誤差性。綜合以上數據，IGA在求解織造車間并行批調度問題上，比BSNRPSO和DE都能更好的找到最優解。

表4 算法平均值改進率

圖5 算法平均值改進率

4 結論

針對遺傳算法自身存在的優缺點提出一種改進算法，并將其運用到求解織造車間并行批調度問題上，經過仿真實驗驗證，這種改進的算法對求解該調度問題是有效的。并在改進遺傳算法中采用了實數編碼機制，結合模擬退火算法中的Metropolis進一步提高算子在可行解集空間中尋優的能力，使得改進遺傳算法相比于BSNRPSO和DE更加合適于解決此類調度問題，對實際的織造車間批調度具有一定的指導意義。

[1] Chandru V，Lee C Y，Uzsoy R．Minimizing total completion time on a batch processing machine with job families[J]. Operations Research Letters，1993，13：61-65.

[2] Jia Z H，Huo S Y，Li K，et al．Integrated scheduling on parallel batch processing machines with non-identical capacities[J]. Engineering Optimization，2019，52 (4)：715-730.

[3] Jia Z，Yan J，Leung J Y T，et al．Ant colony optimization algorithm for scheduling jobs with fuzzy processing time on parallel batch machines with different capacities[J]. Applied Soft Computing，2019，75：548-561.

[4] ?？×? 王慶, 孟彥軍, 等. 并行多機批調度的混合粒子群算法研究[J]. 化工自動化及儀表, 2014, 41(04): 397- 454.

[5] Zhou S，Liu M，Chen H，et al．An effective discrete differential evolution algorithm for scheduling uniform parallel batch processing machines with non-identical capacities and arbitrary job sizes [J]．International Journal of Production Economics，2016，179：1-11.

Improved Genetic Algorithm for Parallel Batch Scheduling in Weaving Workshop

DU Li-zhen, YE Tao, XUAN Zi-feng, WANG Yu-hao

(School of Mechanical Engineering and Automation, Wuhan Textile University，Wuhan Hubei 430200, China)

Aiming at the parallel batch scheduling problem in weaving workshop，an improved genetic algorithm is proposed to minimize the maximum completion time.Firstly，the real number coding method is used for coding operation；Then，the metropolis of simulated annealing algorithm is introduced to enhanced the optimization ability of genetic operator in the feasible solution set space of the scheduling problem；Finally，the performance of the algorithm is compared and analyzed through 150 randomly generated simulation test sets. Then, the test results are compared with the BSNRPSO algorithm mentioned in the literature and another differential evolution algorithm.Experiments show that the improved genetic algorithm is significantly better than its comparison algorithm in solving performance.

genetic algorithm; real coding; metropolis mechanism; weaving workshop

TP39

A

2095－414X(2022)04－0008－05

杜利珍（1975-），女，副教授，博士，研究方向：智能調度、系統建模仿真與優化.

國家重點研究計劃（2019YFB1706300）.