改進(jìn)遺傳算法求解織造車間并行批調(diào)度問題

杜利珍，葉 濤，宣自風(fēng)，王宇豪

改進(jìn)遺傳算法求解織造車間并行批調(diào)度問題

杜利珍，葉 濤，宣自風(fēng)，王宇豪

（武漢紡織大學(xué) 機(jī)械工程與自動(dòng)化學(xué)院，湖北 武漢 430200）

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

遺傳算法；實(shí)數(shù)編碼；Metropolis機(jī)制；織造車間

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

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

1 織造車間并行批調(diào)度問題描述

本文以河南省杰瑞織造科技有限公司紡織服裝(毛衫)生產(chǎn)線作為研究對(duì)象，該服裝生產(chǎn)車間前道工序?yàn)椋嚎椘卓凇此笳?，洗水車間的工序?yàn)閷ⅰ翱椘卓凇眱傻拦ば蛱幚砗蟮拿乐破钒凑詹煌愋瓦M(jìn)行分類，送洗水車間進(jìn)行批次處理，該工序可以視作為一個(gè)并行批處理調(diào)度的問題。其生產(chǎn)過程實(shí)景圖如圖1所示。

圖1 生產(chǎn)實(shí)景

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

2 算法設(shè)計(jì)

2.1 GA算法簡介

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

2.2 編解碼

所研究的調(diào)度問題屬于離散優(yōu)化問題，遺傳算法屬于連續(xù)優(yōu)化方法，通過實(shí)數(shù)編碼的方式將此問題轉(zhuǎn)化為連續(xù)型問題進(jìn)行求解，其編碼原理通過隨機(jī)生成一組實(shí)數(shù)，將此數(shù)組與工件序列配對(duì)，通過基于該實(shí)數(shù)組的降序排列來規(guī)劃工件的加工次序，數(shù)組的長度表示工件的數(shù)目，具體如表1所示。

表1 實(shí)數(shù)編碼

如表1所示，通過第一行實(shí)數(shù)的排序間接的規(guī)定加工序列號(hào)，工件{1,2,3,4,5,6,7,8}經(jīng)過編碼后的加工次序?yàn)镮4、I6、I8、I7、I3、I2、I5、I8。

2.3 算法內(nèi)操作

2.3.1 選擇操作

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

2.3.2 交叉操作

圖2 均勻交叉操作

2.3.3 變異操作

圖3 基本位變異

2.4 改進(jìn)遺傳算法步驟及流程圖

改進(jìn)遺傳算法的流程如圖4所示，步驟如下：

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

步驟2：分別對(duì)算法的種群進(jìn)行對(duì)應(yīng)適應(yīng)度值得求解。

步驟3：基于模擬退火算法的Metropolis機(jī)制，對(duì)原有的適應(yīng)度值進(jìn)行再次更新，其主要根據(jù)該機(jī)制在可行解集空間中尋得比當(dāng)前解更優(yōu)的解。

步驟4：基于“隨機(jī)聯(lián)賽選擇”機(jī)制，從種群中選取適應(yīng)值最好幾個(gè)對(duì)應(yīng)的個(gè)體，將其傳遞給子代。

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

步驟6：基于“基本位變異”機(jī)制，對(duì)經(jīng)過交叉后留下的子代(當(dāng)前變異操作的新父代)進(jìn)行概率性變異，增強(qiáng)種群的穩(wěn)定性。

圖4 改進(jìn)遺傳算法流程圖

步驟7：循環(huán)進(jìn)行步驟2～步驟6，直到滿足終止條件(一般為最大迭代次數(shù))，若滿足，則輸出最優(yōu)個(gè)體及適應(yīng)值，否則再次進(jìn)入循環(huán)體，直到滿足終止條件。

2.5 運(yùn)算復(fù)雜度

3 實(shí)驗(yàn)仿真分析

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

表2 算例參數(shù)設(shè)置

表3 批調(diào)度測試結(jié)果

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

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

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

表4 算法平均值改進(jìn)率

圖5 算法平均值改進(jìn)率

4 結(jié)論

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

[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ī)批調(diào)度的混合粒子群算法研究[J]. 化工自動(dòng)化及儀表, 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-），女，副教授，博士，研究方向：智能調(diào)度、系統(tǒng)建模仿真與優(yōu)化.

國家重點(diǎn)研究計(jì)劃（2019YFB1706300）.