Research on Optimization Algorithm of Workshop Scheduling Based on Improved NSGA-II

doi:10.3778/j.issn.1002-8331.2006-0067

Abstract

Abstract:

Aiming at the problems of poor population diversity and convergence ability of the progeny of NSGA-II algorithm in dealing with shop floor scheduling optimization, an improved NSGA-II algorithm is proposed. The new algorithm mainly proposes the new improved adaptive crossover and mutation operators for the crossover. It compares the individual crowding degree with the population average crowding degree, and combines with the population iterative evolution process. The genetic probability is associated with the population individual and the population evolution iteration times. So it avoids blind guidance and improves the convergence speed of the population. The new algorithm proposes the new uniform evolution elite retention strategy. Through choosing the population individuals via the adaptive hierarchy, it solves the problem of the poor diversity of the population of the offspring. Finally, it regards “maximize the minimum delivery lead time” and “minimize the maximum ideal processing time deviation” as the objective function. In the light of the problem of shop floor scheduling, it uses the improved NSGA-II algorithm to carry out the simulation analysis of the actual project. And by comparing the results of the algorithm optimization before and after the improvement, the effectiveness of the algorithm is verified. Its value parameter applied to the actual production scheduling problem examination is also proved.

Key words: improved NSGA-II algorithm, adaptive crossover and mutation operator, uniform evolutionary elitist retention strategy, scheduling optimization

摘要：

针对NSGA-II算法在处理车间排产优化问题中出现的子代种群多样性差、收敛能力差等问题，提出了一种改进NSGA-II的车间排产优化算法。改进NSGA-II算法主要对传统NSGA-II算法的交叉和变异环节，提出新的改进自适应交叉和变异算子，通过对个体拥挤度与种群平均拥挤度进行对比，并结合种群迭代进化过程，将遗传概率与种群个体及种群进化迭代次数关联，避免盲目导向性，提高种群的收敛速度；提出新的均匀进化精英保留策略，通过自适应分层次选取种群个体，解决子代种群多样性差的问题。针对车间排产问题，选择“最大化最小交货提前期”和“最小化最大理想加工时间偏差”作为目标函数，运用改进NSGA-II算法进行实际工程的仿真分析，对比改进前后算法优化的结果，验证了算法的有效性，同时证明了其应用于实际生产排产调度问题的价值参考性。

关键词: 改进NSGA-II算法, 自适应交叉和变异算子, 均匀进化精英保留策略, 排产优化

ZHOU Yuanling, HU Xiaobing, JIANG Daiyu, LI Hang. Research on Optimization Algorithm of Workshop Scheduling Based on Improved NSGA-II[J]. Computer Engineering and Applications, 2021, 57(19): 274-281.

周原令，胡晓兵，江代渝，李航. 基于改进NSGA-II的车间排产优化算法研究[J]. 计算机工程与应用, 2021, 57(19): 274-281.

References

[1] KHAMSEH A，JOLAI F，BABAEI M.Integrating sequence-dependent group scheduling problem and preventive maintenance in flexible flow shops[J].International Journal of Advanced Manufacturing Technology，2015，77（1/4）：173-185.
[2] ZUO Y H，ZHANG K R.Research on key techniques of intelligent optimization of batch production job shop scheduling[J].Advanced Materials Research，2013，753/755：1903-1909.
[3] DAO-FEI Z，ZHONG Z，XIAO-QIANG G.Intelligent optimization-based production planning and simulation analysis for steelmaking and continuous casting process[J].Journal of Iron and Steel Research（International），2010，17（9）：19-24.
[4] 罗函明，罗天洪，吴晓东，等.求解混合流水车间调度问题的离散布谷鸟算法[J].计算机工程与应用，2020，56（22）：264-271.
LUO H M，LUO T H，WU X D，et al.Discrete cuckoo search algorithm for solving hybrid flow-shop scheduling problem[J].Computer Engineering and Applications，2020，56（22）：264-271.
[5] GARCIA M E，VALERO S，ARGENTE E，et al.A FAST method to achieve flexible production programming systems[J].IEEE Transactions on Systems，Man and Cybernetics.Part C，Applications and Reviews，2008，38（2）：242-252.
[6] ROCK H.The three-machine no-wait flow-shop problem is NP-conmlete[J].Association for Computing Machinery，1984，31（2）：336-345.
[7] 崔维伟，陆志强，潘尔顺.基于多目标优化的生产调度与设备维护集成研究[J].计算机集成制造系统，2014，20（6）：1398-1404.
CUI W W，LU Z Q，PAN E S.Production scheduling and preventive maintenance integration based on multi-objective optimization[J].Computer Integrated Manufacturing Systems，2014，20（6）：1398-1404.
[8] YUE L，GUAN Z L，ZHANG L，et al.Multi objective lotsizing and scheduling with material constraints in flexible parallel lines using a Pareto based guided artificial bee colony algorithm[J].Computers & Industrial Engineering，2019，128：659-680.
[9] JOHNSON S M.Optimal two-and three-stage production schedules with setup times included[J].Naval Research Logistics Quarterly，1954（1）：61-68.
[10] GUNDOGAR E，YILMAZ A，ERKAYMAN B.A solution approach to a synchronisation problem in a JIT production system[J].Production Planning & Control，2014，25（12）.
[11] KUBIAK W，STEINER G，YEOMANS J S.Optimal level schedules for mixed-model multi-level just-in-time assembly systems[J].Annals of Operations Research，1997，69：241-259.
[12] BENKALAI I，REBAINE D，GAGNE C，et al.Improving the migrating birds optimization metaheuristic for the permutation flow shop with sequence-dependent set-up times[J].International Journal of Production Research，2017，55（20）：6145-6157.
[13] MANUPATI V K，RAJYALAKSHMI G，CHAN F T S，et al.A hybrid multi-objective evolutionary algorithm approach for handling sequence-and machine-dependent set-up times in unrelated parallel machine scheduling problem[J].Sādhanā，2017，42（3）：391-403.
[14] XIA W J，WU Z M.An effective hybrid optimization approach for muti-objective flexible job-shop scheduling problem[J].Computers & Industrial Engineering，2005，48（2）：409-425.
[15] 钱忱，闻立杰.流程模型约束下的排产问题求解算法[J].计算机集成制造系统，2018，24（7）：1598-1607.
QIAN C，WEN L J.Solving algorithm for scheduling problem with control-flow constraints[J].Computer Integrated Manufacturing Systems，2018，24（7）：1598-1607.
[16] 冯翔，杨红雨.进港飞机调度多目标优化问题的改进NSGA-II算法[J].电子科技大学学报，2014，43（1）：66-70.
FENG X，YANG H Y.Improved NSGA-II algorithm for multi-objective optimization of scheduling arrival aircrafts[J].Journal of University of Electronic Science and Technology of China，2014，43（1）：66-70.
[17] 林进，吕靖，王瑞.基于改进NSGA-II算法的班轮船期恢复双目标优化[J].大连海事大学学报，2020，46（2）：59-69.
LIN J，LV J，WANG R.A bi-objective optimization for liner schedule recovery based on improved NSGA-[Ⅱ][J].Journal of Dalian Maritime University，2020，46（2）：59-69.
[18] 刘东，黄强，杨元园，等.基于改进NSGA-II算法的水库双目标优化调度[J].西安理工大学学报，2020，36（2）：176-181.
LIU D，HUANG Q，YANG Y Y，et al.Reservoir bi-objective operation optimization based on improved NSGA-[Ⅱ][J].Journal of Xi’an University of Technology，2020，36（2）：176-181.
[19] 乐雄平.基于5M1E分析法提升物流企业服务质量对策的研究[J].铁道运输与经济，2016，38（8）：66-70.
LE X P.Study on countermeasures of improving service quality of logistics enterprises based on 5M1E analysis[J].Railway Transportation and Economy，2016，38（8）：66-70.
[20] SRINIVAS N，DEB K.Multi objective optimization using nondominated sorting in genetic algorithms[J].Evolutionary Computation，1995，2：221-248.
[21] DEB K，PRATAP A，AGARWAL S，et al.A fast and elitist multiobjective genetic algorithm：NSGA?II[J].IEEE Transactions on Evolutionary Computation，2002，6（2）：182-197.
[22] 肖刚，解建仓，罗军刚.基于改进NSGAII的水库多目标防洪调度算法研究[J].水力发电学报，2012，31（5）：77-83.
XIAO G，XIE J C，LUO J G.Improved NSGAH algorithm for flood dispatching of multi-objectives reservoir[J].Journal of Hydroelectric Engineering，2012，31（5）：77-83.
[23] CHEN C L，VEMPATI V S，ALJABER N.An application of genetic algorithms for flow shop problems[J].European Journal of Operational Research，1995，80（2）：389-396.
[24] 霍云亮，胡晓兵，杨雄，等.基于模糊综合评价方法的实例检索策略研究[J].四川大学学报（自然科学版），2018，55（6）：1197-1203.
HUO Y L，HU X B，YANG X，et al.Case retrieval strategy based on fuzzy comprehensive evaluation method[J].Journal of Sichuan University（Natural Science Edition），2018，55（6）：1197-1203.
[25] 王胜兵，张鹏飞.一种利用精英保留改进的量子遗传算法[J].海军工程大学学报，2010，22（1）：5-7.
WANG S B，ZHANG P F.An improved quantum genetic algorithm using elite retention[J].Journal of Naval University of engineering，2010，22（1）：5-7.
[26] 周原令，胡晓兵，霍云亮，等.双基球扁发射药生产线的改进遗传排产算法研究[J].四川大学学报（自然科学版），2019，56（4）：627-632.
ZHOU Y L，HU X B，HUO Y L，et al.Study on Improved Genetic Algorithm for production line of double base spherical flat propellant[J].Journal of Sichuan University（Natural Science Edition），2019，56（4）：627-632.
[27] VANDERHASSELT R F，SPRENGER M，DUCHATEAU L，et al.Automated assessment of footpad dermatitis in broiler chickens at the slaughter-line：Evaluation and correspondence with human expert scores[J].Poultry Science，2013，92（1）：12-18.