求解柔性作业车间调度问题的多策略融合Pareto人工蜂群算法
|
摘要
为克服单一算法在求解多目标柔性作业车间调度问题时最优性和多样性方面的缺陷,提出了一种多策略融合的Pareto人工蜂群算法(multi-strategy integration Pareto artificial bee colony algorithm, MSIPABC).算法在初始化阶段采用混合启发式策略产生质量较高的初始化种群;雇佣蜂采用多种探索操作实现蜂群自主邻域搜索;观察蜂选择较优食物源执行交叉操作,实现蜂群协作搜索,扩大搜索范围,并执行柔性作业车间关键路径相关局部搜索操作,进一步加强蜂群寻优能力;最后侦查蜂对种群重复解进行多样性重构.多种搜索策略的融合使算法不仅实现了人工蜂群的自主与协同搜索,而且达到了全局探索与局部寻优的平衡.通过验证,所提算法在求解质量和获取基准算例Pareto最优解数目方面具有优势.
To remedy the deficiency of the single algorithm in optimality and diversity when solving the multi-objective flexible job shop scheduling problem, we proposed a multi-strategy integration Pareto artificial bee colony algorithm(MSIPABC). First, this algorithm employs the hybrid heuristic strategy to initialize the food source colony to obtain the initiation colony with higher quality. Then the employed foragers use multiple local search operations to explore new food sources around the current food source.The onlookers use the tournament rules to select the superior food sources and perform crossover operation and the critical-path-based neighborhood search to further enhance the optimization search of the algorithm. At last, the scouters reconstruct the repetitive solutions, ensuring the diversity of the food source colony. The algorithm adapts multiple search strategies, realizes the autonomous and cooperative search of artificial swarm and hits a balance between global search and local search. The proposed algorithm is proved to be superior both in solution quality and diversity.
To remedy the deficiency of the single algorithm in optimality and diversity when solving the multi-objective flexible job shop scheduling problem, we proposed a multi-strategy integration Pareto artificial bee colony algorithm(MSIPABC). First, this algorithm employs the hybrid heuristic strategy to initialize the food source colony to obtain the initiation colony with higher quality. Then the employed foragers use multiple local search operations to explore new food sources around the current food source.The onlookers use the tournament rules to select the superior food sources and perform crossover operation and the critical-path-based neighborhood search to further enhance the optimization search of the algorithm. At last, the scouters reconstruct the repetitive solutions, ensuring the diversity of the food source colony. The algorithm adapts multiple search strategies, realizes the autonomous and cooperative search of artificial swarm and hits a balance between global search and local search. The proposed algorithm is proved to be superior both in solution quality and diversity.
引文
[1] Li J Q, Pan Q K, Liang Y C. An effective hybrid tabu search algorithm for multi-objective flexible job-shop scheduling problems[J]. Computers&Industrial Engineering, 2010, 59(4):647-662.
[2] Wang X, Gao L, Zhang C, et al. A multi-objective genetic algorithm based on immune and entropy principle for flexible job-shop scheduling problem[J]. International Journal of Advanced Manufacturing Technology, 2010,51(5-8):757-767.
[3] Chiang T C, Lin H J. A simple and effective evolutionary algorithm for multi-objective flexible job shop scheduling[J]. International Journal of Production Economics, 2013, 141(1):87-98.
[4]李俊青,潘全科,王玉亭.多目标柔性车间调度的Pareto混合禁忌搜索算法[J].计算机集成制造系统,2010, 16(7):1419-1426.Li J Q, Pan Q K, Wang Y T. Hybrid Pareto-based tabu search algorithm for solving the multi-objective flexible job shop scheduling problem[J]. Computer Integrated Manufacturing Systems, 2010, 16(7):1419-1426.
[5]张铁男,韩兵,于渤.生产能力约束条件下的柔性作业车间调度优化[J].系统工程理论与实践,2011,31(3):505-511.Zhang T N, Han B, Yu B. Flexible job shop scheduling optimization based on improved genetic algorithm[J].Systems Engineering—Theory&Practice, 2011, 31(3):505-511.
[6] Moslehi G, Mahnam M. A Pareto approach to multi-objective flexible job-shop scheduling problem using particle swarm optimization and local search[J]. International Journal of Production Economics, 2011, 129(1):14-22.
[7] Shao X Y, Liu W Q, Liu Q, et al. Hybrid discrete particle swarm optimization for multi-objective flexible job-shop scheduling problem[J]. International Journal of Advanced Manufacturing Technology, 2013, 67(9):2885-2901.
[8]赵博选,高建民,陈琨.求解多目标柔性作业车间调度问题的两阶段混合Pareto蚁群算法[J].西安交通大学学报,2016,50(7):145-151.Zhao B X, Gao J M, Chen K. Two-stage hybrid Pareto ant colony algorithm for multi-objective flexible job shop scheduling problem[J]. Journal of Xi'an Jiaotong University, 2016, 50(7):145-151.
[9]朱伟.基于规则导向的柔性作业车间多目标动态调度算法[J].系统工程理论与实践,2017, 37(10):2690-2699.Zhu W. Multi-objective dynamic scheduling algorithm for flexible job shop problem based on rule orientation[J].Systems Engineering—Theory&Practice, 2017, 37(10):2690-2699.
[10]彭建刚,刘明周,张玺,等.基于Pareto优化的离散自由搜索算法求解多目标柔性作业车间调度问题[J].中国机械工程,2015, 26(5):620-626.Peng J G, Liu M Z, Zhang X, et al. Discrete free search based on Pareto-optimality for multi-objective job shop scheduling problem[J]. China Mechanical Engineering, 2015, 26(5):620-626.
[11]徐华,张庭.混合离散蝙蝠算法求解多目标柔性作业车间调度[J].机械工程学报,2016, 52(18):201-212.Xu H, Zhang T. Hybrid discrete bat algorithm for solving the multi-objective flexible job shop scheduling problem[J]. Chinese Journal of Mechanical Engineering, 2016, 52(18):201-212.
[12] Pan Q K, Fatih Tasgetiren M, Suganthan P N, et al. A discrete artificial bee colony algorithm for the lot-streaming flow shop scheduling problem[J]. Information Sciences, 2011, 181(12):2455-2468.
[13] Wang L, Zhou G, Xu Y, et al. An effective artificial bee colony algorithm for the flexible job-shop scheduling problem[J]. International Journal of Production Research, 2013, 51(1-4):303-315.
[14] Zhang R, Song S, Wu C. A hybrid artificial bee colony algorithm for the job shop scheduling problem[J]. International Journal of Production Economics, 2013, 141(1):167-178.
[15] Thammano A, Phuang A. A hybrid artificial bee colony algorithm with local search for flexible job-shop scheduling problem[J]. Procedia Computer Science, 2013, 20:96-101.
[16] Li J Q, Pan Q K, Gao K Z. Pareto-based discrete artificial bee colony algorithm for multi-objective flexible job shop scheduling problems[J]. International Journal of Advanced Manufacturing Technology, 2011, 55(9-12):1159-1169.
[17] Wang L, Zhou G, Xu Y, et al. An enhanced Pareto-based artificial bee colony algorithm for the multi-objective flexible job-shop scheduling[J]. International Journal of Advanced Manufacturing Technology, 2012, 60(9-12):1111-1123.
[18] Li J Q, Pan Q K, Tasgetiren M F. A discrete artificial bee colony algorithm for the multi-objective flexible job-shop scheduling problem with maintenance activities[J]. Applied Mathematical Modelling, 2014, 38(3):1111-1132.
[19]孟冠军,杨大春,陶细佩.基于混合人工蜂群算法的多目标柔性作业车间调度问题研究[J].计算机应用研究,2019, 36(4).http://www.arocmag.com/article/02-2019-04-029.html.Meng G J, Yang D C, Tao X P. Study on multi-objective flexible job-shop scheduling problem based on hybrid artificial bee colony algorithm[J]. Application Research of Computers, 2019, 36(4). http://www.arocmag.com/article/02-2019-04-029.html.
[20] Zhang G, Gao L, Shi Y. An effective genetic algorithm for the flexible job-shop scheduling problem[J]. Expert Systems with Applications, 2011, 38(4):3563-3573.
[2] Wang X, Gao L, Zhang C, et al. A multi-objective genetic algorithm based on immune and entropy principle for flexible job-shop scheduling problem[J]. International Journal of Advanced Manufacturing Technology, 2010,51(5-8):757-767.
[3] Chiang T C, Lin H J. A simple and effective evolutionary algorithm for multi-objective flexible job shop scheduling[J]. International Journal of Production Economics, 2013, 141(1):87-98.
[4]李俊青,潘全科,王玉亭.多目标柔性车间调度的Pareto混合禁忌搜索算法[J].计算机集成制造系统,2010, 16(7):1419-1426.Li J Q, Pan Q K, Wang Y T. Hybrid Pareto-based tabu search algorithm for solving the multi-objective flexible job shop scheduling problem[J]. Computer Integrated Manufacturing Systems, 2010, 16(7):1419-1426.
[5]张铁男,韩兵,于渤.生产能力约束条件下的柔性作业车间调度优化[J].系统工程理论与实践,2011,31(3):505-511.Zhang T N, Han B, Yu B. Flexible job shop scheduling optimization based on improved genetic algorithm[J].Systems Engineering—Theory&Practice, 2011, 31(3):505-511.
[6] Moslehi G, Mahnam M. A Pareto approach to multi-objective flexible job-shop scheduling problem using particle swarm optimization and local search[J]. International Journal of Production Economics, 2011, 129(1):14-22.
[7] Shao X Y, Liu W Q, Liu Q, et al. Hybrid discrete particle swarm optimization for multi-objective flexible job-shop scheduling problem[J]. International Journal of Advanced Manufacturing Technology, 2013, 67(9):2885-2901.
[8]赵博选,高建民,陈琨.求解多目标柔性作业车间调度问题的两阶段混合Pareto蚁群算法[J].西安交通大学学报,2016,50(7):145-151.Zhao B X, Gao J M, Chen K. Two-stage hybrid Pareto ant colony algorithm for multi-objective flexible job shop scheduling problem[J]. Journal of Xi'an Jiaotong University, 2016, 50(7):145-151.
[9]朱伟.基于规则导向的柔性作业车间多目标动态调度算法[J].系统工程理论与实践,2017, 37(10):2690-2699.Zhu W. Multi-objective dynamic scheduling algorithm for flexible job shop problem based on rule orientation[J].Systems Engineering—Theory&Practice, 2017, 37(10):2690-2699.
[10]彭建刚,刘明周,张玺,等.基于Pareto优化的离散自由搜索算法求解多目标柔性作业车间调度问题[J].中国机械工程,2015, 26(5):620-626.Peng J G, Liu M Z, Zhang X, et al. Discrete free search based on Pareto-optimality for multi-objective job shop scheduling problem[J]. China Mechanical Engineering, 2015, 26(5):620-626.
[11]徐华,张庭.混合离散蝙蝠算法求解多目标柔性作业车间调度[J].机械工程学报,2016, 52(18):201-212.Xu H, Zhang T. Hybrid discrete bat algorithm for solving the multi-objective flexible job shop scheduling problem[J]. Chinese Journal of Mechanical Engineering, 2016, 52(18):201-212.
[12] Pan Q K, Fatih Tasgetiren M, Suganthan P N, et al. A discrete artificial bee colony algorithm for the lot-streaming flow shop scheduling problem[J]. Information Sciences, 2011, 181(12):2455-2468.
[13] Wang L, Zhou G, Xu Y, et al. An effective artificial bee colony algorithm for the flexible job-shop scheduling problem[J]. International Journal of Production Research, 2013, 51(1-4):303-315.
[14] Zhang R, Song S, Wu C. A hybrid artificial bee colony algorithm for the job shop scheduling problem[J]. International Journal of Production Economics, 2013, 141(1):167-178.
[15] Thammano A, Phuang A. A hybrid artificial bee colony algorithm with local search for flexible job-shop scheduling problem[J]. Procedia Computer Science, 2013, 20:96-101.
[16] Li J Q, Pan Q K, Gao K Z. Pareto-based discrete artificial bee colony algorithm for multi-objective flexible job shop scheduling problems[J]. International Journal of Advanced Manufacturing Technology, 2011, 55(9-12):1159-1169.
[17] Wang L, Zhou G, Xu Y, et al. An enhanced Pareto-based artificial bee colony algorithm for the multi-objective flexible job-shop scheduling[J]. International Journal of Advanced Manufacturing Technology, 2012, 60(9-12):1111-1123.
[18] Li J Q, Pan Q K, Tasgetiren M F. A discrete artificial bee colony algorithm for the multi-objective flexible job-shop scheduling problem with maintenance activities[J]. Applied Mathematical Modelling, 2014, 38(3):1111-1132.
[19]孟冠军,杨大春,陶细佩.基于混合人工蜂群算法的多目标柔性作业车间调度问题研究[J].计算机应用研究,2019, 36(4).http://www.arocmag.com/article/02-2019-04-029.html.Meng G J, Yang D C, Tao X P. Study on multi-objective flexible job-shop scheduling problem based on hybrid artificial bee colony algorithm[J]. Application Research of Computers, 2019, 36(4). http://www.arocmag.com/article/02-2019-04-029.html.
[20] Zhang G, Gao L, Shi Y. An effective genetic algorithm for the flexible job-shop scheduling problem[J]. Expert Systems with Applications, 2011, 38(4):3563-3573.