基于混合差分进化算法的作业车间动态调度

• 论文 •

基于混合差分进化算法的作业车间动态调度

王万良，王磊，王海燕，徐新黎，赵燕伟

1.浙江工业大学计算机科学与技术学院，浙江杭州310023；2.浙江工业大学信息工程学院，浙江杭州310023；3.浙江工业大学机械工程学院，浙江杭州310014

出版日期:2012-03-15 发布日期:2012-03-25

Dynamic Job Shop scheduling based on hybrid differential evolution algorithm

WANG Wan-liang, WANG Lei, WANG Hai-yan, XU Xin-li, ZHAO Yan-wei

1.College of Computer Science and Technology, Zhejiang University of Technology, Hangzhou 310023, China; 2.College of Information Engineering, Zhejiang University of Technology, Hangzhou 310023, China; 3.College of Mechanical Engineering, Zhejiang University of Technology, Hangzhou 310014, China

Online:2012-03-15 Published:2012-03-25

摘要/Abstract

摘要： 针对动态多变环境下的作业车间调度问题，在基于周期和事件驱动的滚动窗口再调度策略基础上，采用冻结时段思想，同时又允许再调度在冻结时段内的资源上的闲置时段安排任务，并由此建立了机器存在不可用时段约束的动态调度模型。借鉴量子进化算法中量子旋转门更新量子位的方法，设计了三段式交叉操作，并在算法框架中嵌入了局部搜索操作，提出了混合差分进化算法作为再调度的优化方法。通过算法性能与作业车间动态调度实验，验证了所提动态调度方法的有效性。

关键词: 作业车间, 动态调度, 差分进化算法, 滚动窗口, 冻结时段

Abstract: Aiming at Job Shop scheduling problem under dynamic environment, by using frozen interval thought, a dynamic scheduling model with forbidden interval on machines was established based on rolling window rescheduling policy of periodic and event-driven, which allowed rescheduling to arrange task in leisure time of frozen interval. Use for reference on quantum gate updating operator in Quantum Evolutionary Algorithm(QEA), three-step crossover operation was designed. By embedding local search operation into algorithm framework, a new hybrid Differential Evolution(DE)algorithm was proposed as optimization method of rescheduling. Through test of algorithm performance and dynamic Job Shop scheduling, the proposed approach was verified.

Key words: Job Shop, dynamic scheduling, differential evolution algorithm

中图分类号:

TP182

王万良，王磊，王海燕，徐新黎，赵燕伟. 基于混合差分进化算法的作业车间动态调度[J]. .

WANG Wan-liang, WANG Lei, WANG Hai-yan, XU Xin-li, ZHAO Yan-wei. Dynamic Job Shop scheduling based on hybrid differential evolution algorithm[J]. .

[1]	顾九春,姜天华,朱惠琦. 多目标离散灰狼优化算法求解作业车间节能调度问题[J]. 计算机集成制造系统, 2021, 27(8): 2295-2306.
[2]	黎英杰,刘建军,陈庆新,毛宁. 多层级装配作业车间等量分批策略与调度算法[J]. 计算机集成制造系统, 2021, 27(8): 2307-2320.
[3]	杨艳华,姚立纲. 基于时间递推建模及交叉熵算法求解柔性作业车间调度问题[J]. 计算机集成制造系统, 2021, 27(6): 1703-1713.
[4]	段建国,李豪晨,张青雷. 面向绿色制造的半组合式船用曲轴结构件生产车间多目标调度优化[J]. 计算机集成制造系统, 2021, 27(6): 1714-1727.
[5]	马玉敏,陆晓玉,乔非,沈一路. 基于极限学习机的复杂制造系统动态调度[J]. 计算机集成制造系统, 2021, 27(4): 1081-1088.
[6]	谢梦柯,张则强,蒋晋. 考虑工位约束及能耗的双边拆卸线平衡问题建模与优化[J]. 计算机集成制造系统, 2021, 27(3): 701-715.
[7]	杨小佳,刘建军,陈庆新,毛宁. 变扰动强度下柔性装配作业车间调度性能分析[J]. 计算机集成制造系统, 2021, 27(3): 800-814.
[8]	曹远冲,熊辉,庄存波,刘检华,宁伟航. 基于数字孪生的复杂产品离散装配车间动态调度[J]. 计算机集成制造系统, 2021, 27(2): 557-568.
[9]	詹欣隆,张超勇,孟磊磊,连裕翔,薛燕社. 面向高效低碳的切削参数与柔性作业车间调度集成建模与优化[J]. 计算机集成制造系统, 2021, 27(12): 3519-3535.
[10]	葛艳,王爱民,叶介然. 基于遗传退火算法的质检扰动应对方法[J]. 计算机集成制造系统, 2021, 27(11): 3159-3171.
[11]	连裕翔,张超勇,孟磊磊,薛燕社,詹欣隆,吕畅. 基于改进Jaya算法的柔性作业车间调度问题[J]. 计算机集成制造系统, 2021, 27(11): 3172-3184.
[12]	刘雪红,段程,王磊. 基于改进候鸟算法的柔性作业车间分批调度问题[J]. 计算机集成制造系统, 2021, 27(11): 3185-3195.
[13]	薛玲玲. 作业车间调度的块结构邻域搜索遗传算法[J]. 计算机集成制造系统, 2021, 27(10): 2848-2857.
[14]	李峥峰,刘阳阳. 考虑充电的多AGV的作业车间调度问题[J]. 计算机集成制造系统, 2021, 27(10): 2872-2879.
[15]	罗焕,陈浩杰,宋小欣,张剑. 带有缓存约束的作业车间调度求解方法[J]. 计算机集成制造系统, 2021, 27(10): 2880-2888.