《计算机应用研究》|Application Research of Computers

求解作业车间调度问题的改进混合灰狼优化算法

Solving Job-Shop scheduling problem using improved hybrid grey wolf optimizer

免费全文下载 (已被下载 次)  
获取PDF全文
作者 姚远远,叶春明
机构 上海理工大学 管理学院,上海 200093
统计 摘要被查看 次,已被下载
文章编号 1001-3695(2018)05-1310-05
DOI 10.3969/j.issn.1001-3695.2018.05.007
摘要 灰狼优化算法(GWO)是目前一种比较新颖的群智能优化算法,具有收敛速度快、寻优能力强等优点。将灰狼优化算法用于求解复杂的作业车间调度问题,与布谷鸟搜索算法进行比较研究,验证了标准GWO算法求解经典作业车间调度问题的可行性和有效性。在此基础上,针对复杂作业车间调度问题难以求解的特点,对标准GWO算法进行改进,通过进化种群动态、反向学习初始化种群以及最优个体变异三个方面的改进操作,测试结果表明,改进后的混合灰狼优化算法能够有效跳出局部最优值,找到更好的解,并且结果鲁棒性更强。
关键词 灰狼优化算法;作业车间调度;最小化最大完工时间;混合算法
基金项目 国家自然科学基金资助项目(71271138)
上海理工大学科技发展项目(16KJFZ028)
上海市高原学科项目“管理科学与工程”(GYXK1201)
本文URL http://www.arocmag.com/article/01-2018-05-007.html
英文标题 Solving Job-Shop scheduling problem using improved hybrid grey wolf optimizer
作者英文名 Yao Yuanyuan, Ye Chunming
机构英文名 BusinessSchool,UniversityofShanghaiforScience&Technology,Shanghai200093,China
英文摘要 Grey wolf optimizer(GWO) was currently one of the latest proposed swarm intelligence algorithms with the advantages of fast convergence rate and better optimization performance. Firstly this paper benchmarked the original GWO algorithm on 11 well-known Job-Shop scheduling test instances, and verified the results by a comparative study with cuckoo search (CS). The results show that the GWO algorithm is able to provide very competitive results compared to CS. In order to solve complex and large scale Job-Shop scheduling problems, it proposed an improved hybrid grey wolf optimizer (IGWO) by using evolutionary population dynamics (EPD) method, opposition-based learning strategy and mutation operator. Then it benchmarked the proposed IGWO algorithm on seven large scale test instances. It compared the results to the original GWO algorithm for verification. It demonstrates that the proposed algorithm is able to significantly improve the performance of the GWO algorithm for solving production scheduling problem in terms of exploration, local optima avoidance, exploitation and robustness.
英文关键词 grey wolf optimizer; Job-Shop scheduling; makespan minimization; hybrid algorithm
参考文献 查看稿件参考文献
  [1] 王永明, 尹红丽, 秦开大. 作业车间调度理论及其优化方法研究[M] . 北京:科学出版社, 2013:1-25.
[2] Mirjalili S, Mirjalili S M, Lewis A. Grey wolf optimizer[J] . Advances in Engineering Software, 2014, 69(3):46-61.
[3] Saremi S, Mirjalili S Z, Mirjalili S M. Evolutionary population dynamics and grey wolf optimizer[J] . Neural Computing and Applications, 2015, 26(5):1257-1263.
[4] Mirjalili S, Saremi S, Mirjalili S M, et al. Multi-objective grey wolf optimizer:a novel algorithm for multi-criterion optimization[J] . Expert Systems with Applications, 2016, 47(4):106-119. [5] Lu Chao, Xiao Shengqiang, Li Xinyu, et al. An effective multi-objective discrete grey wolf optimizer for a real-world scheduling problem in welding production[J] . Advances in Engineering Software, 2016, 99(9):161-176.
[6] Lu Chao, Gao Liang, Li Xinyu, et al. A hybrid multi-objective grey wolf optimizer for dynamic scheduling in a real-world welding industry[J] . Engineering Applications of Artificial Intelligence, 2017, 57(1):61-79.
[7] 吕新桥, 廖天龙. 基于灰狼优化算法的置换流水线车间调度[J] . 武汉理工大学学报, 2015, 37(5):111-116.
[8] 陈昌帅. 二进制灰狼优化算法的研究与分析[J] . 信息系统工程, 2016(7):136-138.
[9] 王凌. 智能优化算法及其应用[M] . 北京:清华大学出版社, 2001:10-16.
[10] 罗亚波. 作业系统调度优化理论与方法[M] . 武汉:华中科技大学出版社, 2011:1-10.
[11] Yang Xinshe. Nature-inspired metaheuristic algorithms[M] . 2nd ed. Frome:Luniver Press, 2010:16.
[12] Tizhoosh H R. Opposition-based learning:a new scheme for machine intelligence[C] //Proc of International Conference on Computational Intelligence for Modelling Control and Automation. [S. l. ] :IEEE Press, 2005:695-701.
[13] Wang Yong, Cai Zixing, Zhou Yuren, et al. Constrained optimization based on hybrid evolutionary algorithm and adaptive constraint-handling technique[J] . Structural and Multidisciplinary Optimization, 2009, 37(4):395-413.
[14] 陈乐, 龙文. 求解工程结构优化问题的改进布谷鸟搜索算法[J] . 计算机应用研究, 2014, 31(3):679-683.
[15] Yang Xinshe, Deb S. Cuckoo search via Lévy flights[C] //Proc of World Congress on Nature & Biologically Inspired Computing. New York:IEEE Publications, 2009:210-214.
[16] Yang Xinshe, Deb S. Engineering optimisation by cuckoo search[J] . International Journal of Mathematical Modelling and Numerical Optimisation, 2010, 1(4):330-343.
收稿日期 2017/1/5
修回日期 2017/2/26
页码 1310-1314
中图分类号 TP301.6
文献标志码 A