Dynamic Job Shop scheduling based on hybrid differential evolution algorithm

• Article •

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

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

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

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

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

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

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

CLC Number:

TP182

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]. .

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

[1]	. Energy-saving job shop scheduling problem with multi-objective discrete grey wolf optimization algorithm [J]. , 2021, 27(8): 2295-2306.
[2]	. Lot-splitting and scheduling algorithm of multi-level assembly job shops [J]. , 2021, 27(8): 2307-2320.
[3]	. Time recursive modeling and cross entropy algorithm for flexible job shop scheduling problem [J]. , 2021, 27(6): 1703-1713.
[4]	. Green manufacturing-oriented multi-objective scheduling optimization for half built-up marine crank shaft component workshop [J]. , 2021, 27(6): 1714-1727.
[5]	. Multi-objective scheduling algorithm for one worker job shop considering learning effect [J]. , 2021, 27(5): 1361-1370.
[6]	. Dynamic scheduling for complex manufacturing system based on extreme learning machine [J]. , 2021, 27(4): 1081-1088.
[7]	. Modeling and optimization of two-sided disassembly line balance problem considering station constraint and energy consumption [J]. , 2021, 27(3): 701-715.
[8]	. Performance analysis of flexible assembly job shop scheduling under variable disturbance intensity [J]. , 2021, 27(3): 800-814.
[9]	. Dynamic scheduling of complex product discrete assembly workshop based on digital twin [J]. , 2021, 27(2): 557-568.
[10]	. Integrated optimization of cutting parameters and flexible job shop scheduling based on improved discrete gravity search algorithm [J]. , 2021, 27(12): 3519-3535.
[11]	. Improved Jaya algorithm and tabu search for flexile job shop scheduling problem [J]. , 2021, 27(11): 3172-3184.
[12]	. Flexible job shop scheduling with lot streaming based on improved migrating birds optimization algorithm [J]. , 2021, 27(11): 3185-3195.
[13]	. Job shop scheduling considering multiple AGVs with charging [J]. , 2021, 27(10): 2872-2879.
[14]	. Job shop scheduling with buffer constraint [J]. , 2021, 27(10): 2880-2888.
[15]	. Task planning of UAV stocktaking tray in complex industrial storage environment [J]. , 2021, 27(10): 2940-2949.