基于改进GSO算法的柔性作业车间E/T调度问题
|
摘要
针对机器资源和加工路线可选择情况下的柔性车间调度,以最小最大完工时间和时间惩罚成本为目标建立柔性车间E/T调度模型.根据问题特点,提出一种改进的萤火虫算法(GSO),算法设计了一种具有贪婪思想的编码策略,一个萤火虫个体表示工序加工顺序和工序加工位置;采用自适应选择策略,使步长自适应,提高算法精度;引入POX交叉、邻域交换和反序排序方法提高算法局部和全局寻优能力,并利用贪婪思想,提高算法的收敛速度.通过经典算例和实例验证算法性能,实验结果表明改进的萤火虫算法求解柔性车间调度问题的有效性.
For flexible shop scheduling in the case of machine resources and processing route selectable,a flexible shop model is established with minimum and maximum completion time and time penalty costs as targets.According to the characteristics of the problem,an improved firefly algorithm is proposed.The algorithm designs a coding strategy with greedy ideas.A firefly individual represents the processing sequence and process processing position.It adopts an adaptive selection strategy to adapt the step length and improve the accuracy of the algorithm.The introduction of POX cross strategy to improve the algorithm's local and global optimization capabilities,and the use of greed to improve the convergence speed of the algorithm.The performance of the algorithm is verified by comparison with example simulations and algorithms.The experimental results show that the improved firefly algorithm is effective for solving the flexible shop scheduling problem.
For flexible shop scheduling in the case of machine resources and processing route selectable,a flexible shop model is established with minimum and maximum completion time and time penalty costs as targets.According to the characteristics of the problem,an improved firefly algorithm is proposed.The algorithm designs a coding strategy with greedy ideas.A firefly individual represents the processing sequence and process processing position.It adopts an adaptive selection strategy to adapt the step length and improve the accuracy of the algorithm.The introduction of POX cross strategy to improve the algorithm's local and global optimization capabilities,and the use of greed to improve the convergence speed of the algorithm.The performance of the algorithm is verified by comparison with example simulations and algorithms.The experimental results show that the improved firefly algorithm is effective for solving the flexible shop scheduling problem.
引文
1 Pinedo M. Scheduling:Theory, algorithms, and systems. IHE Transactions, 1996, 28(8):695-697.[doi:10.1080/15458830.1996.11770714]
2刘爱军,杨育,邢青松,等.多目标模糊柔性车间调度中的多种群遗传算法.计算机集成制造系统,2011, 17(9):1954-1961.
3蔡霞,李枚毅,王康,等.基于浮点型编码策略的差分多目标柔性车间调度优化.计算机应用研究,2013, 30(4):999-1003.[doi:10.3969/j.issn. 1001-3695.2013.04.010]
4侯晓莉,刘永,江来臻,等.多目标FJSP的一维编码粒子群优化求解方法.计算机工程与应用,2015, 51(13):47-51,71.[doi:10.3778/j.issn. 1002-8331.1408-0067]
5马立波,王艳.基于离散震荡粒子群算法的柔性作业车间调度优化方法.机械制造与自动化,2016, 45(2):231-235.[doi:10.3969/j.issn.1671-5276.2016.02.065]
6薛宏全,魏生民,张鹏,等.基于多种群蚁群算法的柔性作业车间调度研究.计算机工程与应用,2013, 49(24):243-248, 261.[doi:10.3778/j.issn.1002-8331.1306-0315]
7栾飞,王雯,傅卫平,等.基于PST层次结构的改进GA求解柔性车间调度问题.计算机集成制造系统,2014, 20(10):2494-2501.
8徐华,张庭.新型离散蝙蝠算法求解柔性流水车间调度问题.计算机工程与应用,2016, 52(2):262-265.[doi:10.3778/j.issn.1002-8331.1412-0353]
9傅卫平,刘冬梅,来春为,等.基于多色集合的改进遗传算法求解多品种柔性调度问题.计算机集成制造系统,2011,17(5):1004-1010.
10 Krishnanand KN, Ghose D. Detection of multiple source locations using a glowworm metaphor with applications to collective robotics. Proceedings of the IEEE Swarm Intelligence Symposium. Pasadena, CA, USA. 2005. 84-91.
11 Chiang TC, Lin HJ. A simple and effective evolutionary algorithm for multiobjective flexible job shop scheduling.International Journal of Production Economics, 2013, 141(1):87-98.[doi:10.1016/j.ijpe.2012.03.034]
12 Xia WJ, Wu ZM. An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problems.Computers&Industrial Engineering, 2005, 48(2):409-425.
13吴秀丽,张志强,杜彦华,等.改进细菌觅食算法求解柔性作业车间调度问题.计算机集成制造系统,2015, 21(5):1262-1270.
14马佳,石刚.基于改进人工免疫算法的柔性车间调度问题.计算机仿真,2014, 31(12):375-379.[doi:10.3969/j.issn.1006-9348.2014.12.083]
15田旻,刘人境.分层混合遗传算法求解柔性作业车间调度问题.工业工程与管理,2017, 22(5):32-39.
16 Xing LN, Chen YW, Wang P, et al. A knowledge-based ant colony optimization for flexible job shop scheduling problems. Applied Soft Computing, 2010,10(3):888-896.[doi:10.1016/j.asoc.2009.10.006]
2刘爱军,杨育,邢青松,等.多目标模糊柔性车间调度中的多种群遗传算法.计算机集成制造系统,2011, 17(9):1954-1961.
3蔡霞,李枚毅,王康,等.基于浮点型编码策略的差分多目标柔性车间调度优化.计算机应用研究,2013, 30(4):999-1003.[doi:10.3969/j.issn. 1001-3695.2013.04.010]
4侯晓莉,刘永,江来臻,等.多目标FJSP的一维编码粒子群优化求解方法.计算机工程与应用,2015, 51(13):47-51,71.[doi:10.3778/j.issn. 1002-8331.1408-0067]
5马立波,王艳.基于离散震荡粒子群算法的柔性作业车间调度优化方法.机械制造与自动化,2016, 45(2):231-235.[doi:10.3969/j.issn.1671-5276.2016.02.065]
6薛宏全,魏生民,张鹏,等.基于多种群蚁群算法的柔性作业车间调度研究.计算机工程与应用,2013, 49(24):243-248, 261.[doi:10.3778/j.issn.1002-8331.1306-0315]
7栾飞,王雯,傅卫平,等.基于PST层次结构的改进GA求解柔性车间调度问题.计算机集成制造系统,2014, 20(10):2494-2501.
8徐华,张庭.新型离散蝙蝠算法求解柔性流水车间调度问题.计算机工程与应用,2016, 52(2):262-265.[doi:10.3778/j.issn.1002-8331.1412-0353]
9傅卫平,刘冬梅,来春为,等.基于多色集合的改进遗传算法求解多品种柔性调度问题.计算机集成制造系统,2011,17(5):1004-1010.
10 Krishnanand KN, Ghose D. Detection of multiple source locations using a glowworm metaphor with applications to collective robotics. Proceedings of the IEEE Swarm Intelligence Symposium. Pasadena, CA, USA. 2005. 84-91.
11 Chiang TC, Lin HJ. A simple and effective evolutionary algorithm for multiobjective flexible job shop scheduling.International Journal of Production Economics, 2013, 141(1):87-98.[doi:10.1016/j.ijpe.2012.03.034]
12 Xia WJ, Wu ZM. An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problems.Computers&Industrial Engineering, 2005, 48(2):409-425.
13吴秀丽,张志强,杜彦华,等.改进细菌觅食算法求解柔性作业车间调度问题.计算机集成制造系统,2015, 21(5):1262-1270.
14马佳,石刚.基于改进人工免疫算法的柔性车间调度问题.计算机仿真,2014, 31(12):375-379.[doi:10.3969/j.issn.1006-9348.2014.12.083]
15田旻,刘人境.分层混合遗传算法求解柔性作业车间调度问题.工业工程与管理,2017, 22(5):32-39.
16 Xing LN, Chen YW, Wang P, et al. A knowledge-based ant colony optimization for flexible job shop scheduling problems. Applied Soft Computing, 2010,10(3):888-896.[doi:10.1016/j.asoc.2009.10.006]