基于自适应变级遗传杂草算法的FJSP研究
|
摘要
针对以最小化最大完工时间为目标的柔性作业车间调度问题,建立其数学模型并提出一种自适应变级遗传杂草算法求解之。改进基本入侵杂草优化算法以适应柔性作业车间调度问题的组合优化特点,提出基于总个体数的评价指标,用其分析入侵杂草优化算法在解决柔性作业车间调度问题时的性能及参数对算法的影响,得出入侵杂草优化算法的种群数和个体产生种子数对算法性能的影响关系。分析入侵杂草优化算法和遗传算法在求解柔性作业车间调度问题时各自的优缺点。结合这两种算法,引入汉明距离来测度种群多样性并用该测度值作为变级控制的依据,提出一种根据多样性测度值的动态变化而自适应地在遗传算法和入侵杂草优化算法间串行变级的遗传杂草算法。通过实例对比入侵杂草优化算法、遗传算法和自适应变级遗传杂草算法,证明了自适应变级遗传杂草算法的有效性和优越性。将自适应变级遗传杂草算法用于标准测试实例与多种算法比较,证明了该算法能够有效求解柔性作业车间调度问题。
For flexible job shop scheduling problem with minimizing makespan, a mathematical model and a self-adaptive multistage genetic algorithm/invasive weed optimization algorithm are proposed. For the characteristics of flexible job shop scheduling problem,invasive weed optimization is improved. Using some new evaluating indicators based on total number of individuals to evaluate the performance of improved invasive weed optimization, how the population size and weed size affect invasive weed optimization is addressed. Using the new evaluating indicators to evaluate improved invasive weed optimization and genetic algorithm, some differences between them are illustrated. Using hamming distance to measure the population diversity, the value of population diversity is used to control the self-adaptive multistage between invasive weed optimization and genetic algorithm, obtaining a self-adaptive multistage genetic algorithm/invasive weed optimization algorithm. Using some instances to test genetic algorithm,invasive weed optimization, and self-adaptive multistage genetic algorithm/invasive weed optimization, the advantages of self-adaptive multistage genetic algorithm/invasive weed optimization are shown. Using some standard instances to compare a self-adaptive multistage genetic algorithm/invasive weed optimization with other algorithms, the simulation results show that the proposed algorithm can solve flexible job shop scheduling problem effectively.
For flexible job shop scheduling problem with minimizing makespan, a mathematical model and a self-adaptive multistage genetic algorithm/invasive weed optimization algorithm are proposed. For the characteristics of flexible job shop scheduling problem,invasive weed optimization is improved. Using some new evaluating indicators based on total number of individuals to evaluate the performance of improved invasive weed optimization, how the population size and weed size affect invasive weed optimization is addressed. Using the new evaluating indicators to evaluate improved invasive weed optimization and genetic algorithm, some differences between them are illustrated. Using hamming distance to measure the population diversity, the value of population diversity is used to control the self-adaptive multistage between invasive weed optimization and genetic algorithm, obtaining a self-adaptive multistage genetic algorithm/invasive weed optimization algorithm. Using some instances to test genetic algorithm,invasive weed optimization, and self-adaptive multistage genetic algorithm/invasive weed optimization, the advantages of self-adaptive multistage genetic algorithm/invasive weed optimization are shown. Using some standard instances to compare a self-adaptive multistage genetic algorithm/invasive weed optimization with other algorithms, the simulation results show that the proposed algorithm can solve flexible job shop scheduling problem effectively.
引文
[1]JOHNSON S.Optimal two-and-three stage production schedules with setup times included[J].Naval Research Logistics Quarterly,1954,1:61-68.
[2]GAREY M R,JOHNSON D S,SETHI R.The complexity of flow hop and job shop scheduling[J].Mathematics of Operations Research,1976,1(2):117-129.
[3]BRUCKER P,SCHLIE R.Job-shop scheduling with multi-purpose machines[J].Computing,1990,45(4):369-375.
[4]AZZOUZ A,ENNIGROU M,BEN S,et al.A hybrid algorithm for flexible job-shop scheduling problem with setup times[J].International Journal of Production Management and Engineering,2017,5(1):23-30.
[5]CHIANG T,LIN H.A simple and effective evolutionary algorithm for multi-objective flexible job shop scheduling[J].International Journal of Production Economics,2013,141:87-98.
[6]吴秀丽,张志强,杜彦华,等.改进细菌觅食算法求解柔性作业车间调度问题[J].计算机集成制造系统,2015,21(5):1262-1270.WU Xiuli,ZHANG Zhiqiang,DU Yanhua,et al.Improved bacteria foraging optimization algorithm for flexible job shop scheduling problem[J].Computer Integrated Manufacturing systems,2015,21(5):1262-1270.
[7]徐华,张庭.混合离散蝙蝠算法求解多目标柔性作业车间调度[J].机械工程学报,2016,52(18):201-212.XU Hua,ZHANG Ting.Hybrid discrete bat algorithm for solving the multi-objective flexible job shop scheduling problem[J].Journal of Mechanical Engineering,2016,52(18):201-212.
[8]LU C,LI X,GAO L,et al.An effective multi-objective discrete virus optimization algorithm for flexible job-shop scheduling problem with controllable processing times[J].Computers and Industrial Engineering,2017,104:156-174.
[9]刘洲洲,李彬.基于动态多子族群自适应群居蜘蛛优化算法[J].四川大学学报,2017,54(4):721-727.LIU Zhouzhou,LI Bin.An adaptation social spider optimization algorithm based on dynamic multi-swarm strategy[J].Journal of Sichuan University,2017,54(4):721-727.
[10]ZHANG W,WEN J B,ZHU Y C,et al.Multi-objective scheduling simulation of flexible job-shop based on multi-population genetic algorithm[J].International Journal of Simulation Modeling,2017,16(2):313-321.
[11]CHANG H C,LIU T K.Optimization of distributed manufacturing flexible job shop scheduling by using hybrid genetic algorithms[J].Journal of Intelligent Manufacturing,2017,28(8):1973-1986.
[12]TANG Qiuhua,LI Zixiang,ZHANG Liping,et al.Effective hybrid teaching-learning-based optimization algorithm for balancing two-sided sssembly lines with multiple constraints[J].Chinese Journal of Mechanical Engineering,2015,28(5):1067-1079.
[13]牟健慧.基于混合遗传算法的车间逆调度方法研究[D].武汉:华中科技大学,2015.MU Jianhui.Research on inverse scheduling methods based on hybrid genetic algorithm[D].Wuhan:Huazhong University of Science and Technology,2015.
[14]ATABAKI M S,MOHAMMADI M,NADERI B.Hybrid genetic algorithm and invasive weed optimization via priority based encoding for location-allocation decisions in a three-stage supply chain[J].Asla-pacific Journal of Operational Research,2017,32(2):1750008.
[15]MISHRA S K,BOSE P S C,RAO C S P.An invasive weed optimization approach for job shop scheduling problems[J].International Journal of Advanced Manufacturing Technology.2017,91(9-12):4233-4241.
[16]MEHRABIAN A R,LUCAS C.A novel numerical optimization algorithm inspired from weed colonization[J].Ecological Informatics,2006,1(4):355-366.
[17]张超勇,饶运清,李培根,等.柔性作业车间调度问题的两级遗传算法[J].机械工程学报,2007,43(4):119-124.ZHANG Chaoyong,RAO Yunqing,LI Peigen,et al.Bilevel genetic algorithm for the flexible job-shop scheduling problem[J].Chinese Journal of Mechanical Engineering,2007,43(4):119-124.
[18]石小秋,石宇强,袁雪娇.离散多种群入侵杂草优化算法求解柔性作业车间调度问题[J].信息与控制,2015,44(2):238-243.SHI Xiaoqiu,SHI Yuqiang,YUAN Xuejiao.Invasive weed optimization algorithm with discrete multi-population for the flexible job-shop scheduling problem[J].Information and control,2015,44(2):238-243.
[19]张超勇,饶运清,刘向车,等.基于POX交叉的遗传算法求解Job-Shop调度问题[J].中国机械工程,2004,15(23):2149-2153.ZHANG Chaoyong,RAO Yunqing,LIU Xiangjun,et al.An improved genetic algorithm for the job shop scheduling problem[J].China Mechanical Engineering,2004,15(23):2149-2153.
[20]KACEM I,HAMMADI S,BORNE P.Approach by localization and multiobjective evolutionary optimization for flexible job-shop scheduling problems[J].IEEETransactions on Systems,Man,and Cybernetics Part C:Applications and Reviews,2002,31(1):1-13.
[21]WANG Ling,WANG Shengyao,XU Ye,et al.Abi-population based estimation of distribution algorithm for the flexible job-shop scheduling problem[J].Computers and Industrial Engineering,2012,62(4):917-926.
[22]CHIANG T C,LIN H J.A simple and effective evolutionary algorithm for multiobjective flexible job shop scheduling[J].International Journal of Production Economics,2013,141(1):87-98.
[23]FATTAHI P,MEHRABAD M S,JOLAI F.Mathematical modeling and heuristic approaches to flexible job shop scheduling problems[J].Journal of Intelligent Manufacturing,2007,18(3):331342.
[24]YUAN Yuan,XU Hua,YANG Jiadong.A hybrid harmony search algorithm for the flexible job shop scheduling problem[J].Applied Soft Computing,2013,13(7):3259-3272.
[25]DEMIR Y,ISLEYEN S K.Evaluation of mathematical models for flexible job shop scheduling problems[J].Applied Mathematical Modelling,2013,37:977-988.
[26]BIRGIN E G,FEOFILOFF P,FERNANDES C G,et al.A MILP model for an extended version of the flexible job shop problem[J].Optimization Letters,2014,8:1417-1437.
[27]LI Xinyu,GAO Liang.An effective hybrid genetic algorithm and tabu search for flexible job shop scheduling problem[J].International Journal of Production Economics,2016,174:93-110.
[2]GAREY M R,JOHNSON D S,SETHI R.The complexity of flow hop and job shop scheduling[J].Mathematics of Operations Research,1976,1(2):117-129.
[3]BRUCKER P,SCHLIE R.Job-shop scheduling with multi-purpose machines[J].Computing,1990,45(4):369-375.
[4]AZZOUZ A,ENNIGROU M,BEN S,et al.A hybrid algorithm for flexible job-shop scheduling problem with setup times[J].International Journal of Production Management and Engineering,2017,5(1):23-30.
[5]CHIANG T,LIN H.A simple and effective evolutionary algorithm for multi-objective flexible job shop scheduling[J].International Journal of Production Economics,2013,141:87-98.
[6]吴秀丽,张志强,杜彦华,等.改进细菌觅食算法求解柔性作业车间调度问题[J].计算机集成制造系统,2015,21(5):1262-1270.WU Xiuli,ZHANG Zhiqiang,DU Yanhua,et al.Improved bacteria foraging optimization algorithm for flexible job shop scheduling problem[J].Computer Integrated Manufacturing systems,2015,21(5):1262-1270.
[7]徐华,张庭.混合离散蝙蝠算法求解多目标柔性作业车间调度[J].机械工程学报,2016,52(18):201-212.XU Hua,ZHANG Ting.Hybrid discrete bat algorithm for solving the multi-objective flexible job shop scheduling problem[J].Journal of Mechanical Engineering,2016,52(18):201-212.
[8]LU C,LI X,GAO L,et al.An effective multi-objective discrete virus optimization algorithm for flexible job-shop scheduling problem with controllable processing times[J].Computers and Industrial Engineering,2017,104:156-174.
[9]刘洲洲,李彬.基于动态多子族群自适应群居蜘蛛优化算法[J].四川大学学报,2017,54(4):721-727.LIU Zhouzhou,LI Bin.An adaptation social spider optimization algorithm based on dynamic multi-swarm strategy[J].Journal of Sichuan University,2017,54(4):721-727.
[10]ZHANG W,WEN J B,ZHU Y C,et al.Multi-objective scheduling simulation of flexible job-shop based on multi-population genetic algorithm[J].International Journal of Simulation Modeling,2017,16(2):313-321.
[11]CHANG H C,LIU T K.Optimization of distributed manufacturing flexible job shop scheduling by using hybrid genetic algorithms[J].Journal of Intelligent Manufacturing,2017,28(8):1973-1986.
[12]TANG Qiuhua,LI Zixiang,ZHANG Liping,et al.Effective hybrid teaching-learning-based optimization algorithm for balancing two-sided sssembly lines with multiple constraints[J].Chinese Journal of Mechanical Engineering,2015,28(5):1067-1079.
[13]牟健慧.基于混合遗传算法的车间逆调度方法研究[D].武汉:华中科技大学,2015.MU Jianhui.Research on inverse scheduling methods based on hybrid genetic algorithm[D].Wuhan:Huazhong University of Science and Technology,2015.
[14]ATABAKI M S,MOHAMMADI M,NADERI B.Hybrid genetic algorithm and invasive weed optimization via priority based encoding for location-allocation decisions in a three-stage supply chain[J].Asla-pacific Journal of Operational Research,2017,32(2):1750008.
[15]MISHRA S K,BOSE P S C,RAO C S P.An invasive weed optimization approach for job shop scheduling problems[J].International Journal of Advanced Manufacturing Technology.2017,91(9-12):4233-4241.
[16]MEHRABIAN A R,LUCAS C.A novel numerical optimization algorithm inspired from weed colonization[J].Ecological Informatics,2006,1(4):355-366.
[17]张超勇,饶运清,李培根,等.柔性作业车间调度问题的两级遗传算法[J].机械工程学报,2007,43(4):119-124.ZHANG Chaoyong,RAO Yunqing,LI Peigen,et al.Bilevel genetic algorithm for the flexible job-shop scheduling problem[J].Chinese Journal of Mechanical Engineering,2007,43(4):119-124.
[18]石小秋,石宇强,袁雪娇.离散多种群入侵杂草优化算法求解柔性作业车间调度问题[J].信息与控制,2015,44(2):238-243.SHI Xiaoqiu,SHI Yuqiang,YUAN Xuejiao.Invasive weed optimization algorithm with discrete multi-population for the flexible job-shop scheduling problem[J].Information and control,2015,44(2):238-243.
[19]张超勇,饶运清,刘向车,等.基于POX交叉的遗传算法求解Job-Shop调度问题[J].中国机械工程,2004,15(23):2149-2153.ZHANG Chaoyong,RAO Yunqing,LIU Xiangjun,et al.An improved genetic algorithm for the job shop scheduling problem[J].China Mechanical Engineering,2004,15(23):2149-2153.
[20]KACEM I,HAMMADI S,BORNE P.Approach by localization and multiobjective evolutionary optimization for flexible job-shop scheduling problems[J].IEEETransactions on Systems,Man,and Cybernetics Part C:Applications and Reviews,2002,31(1):1-13.
[21]WANG Ling,WANG Shengyao,XU Ye,et al.Abi-population based estimation of distribution algorithm for the flexible job-shop scheduling problem[J].Computers and Industrial Engineering,2012,62(4):917-926.
[22]CHIANG T C,LIN H J.A simple and effective evolutionary algorithm for multiobjective flexible job shop scheduling[J].International Journal of Production Economics,2013,141(1):87-98.
[23]FATTAHI P,MEHRABAD M S,JOLAI F.Mathematical modeling and heuristic approaches to flexible job shop scheduling problems[J].Journal of Intelligent Manufacturing,2007,18(3):331342.
[24]YUAN Yuan,XU Hua,YANG Jiadong.A hybrid harmony search algorithm for the flexible job shop scheduling problem[J].Applied Soft Computing,2013,13(7):3259-3272.
[25]DEMIR Y,ISLEYEN S K.Evaluation of mathematical models for flexible job shop scheduling problems[J].Applied Mathematical Modelling,2013,37:977-988.
[26]BIRGIN E G,FEOFILOFF P,FERNANDES C G,et al.A MILP model for an extended version of the flexible job shop problem[J].Optimization Letters,2014,8:1417-1437.
[27]LI Xinyu,GAO Liang.An effective hybrid genetic algorithm and tabu search for flexible job shop scheduling problem[J].International Journal of Production Economics,2016,174:93-110.