Genetic Algorithm for Solving Multi-Objective Dynamic Flexible Job Shop Scheduling

doi:10.16182/j.issn1004731x.joss.201708003

Abstract

Abstract: To solve the scheduling problem of mold workshop in a toy factory with dynamic and flexible features, a mathematical model was established by introducing virtual operation and virtual working hours. Based on the strategies of periodic scheduling combined with dynamic event scheduling as well as the rolling window scheduling operation technology, dynamic scheduling was transformed into several continuous static scheduling windows, under which multi-objective genetic algorithm was used to solve the model. The priority of operation scheduling was given in different dynamic events. In addition, the encoding and anti-encoding of chromosome's operation sequence were made based on the proposed priority. Real running of mold workshop scheduling verifies the effectiveness of the proposed dynamic scheduling model, scheduling policy and the algorithm.

Key words: dynamic scheduling, virtual operation, virtual working hours, rolling window, genetic algorithm, priority

CLC Number:

TP183

Wang Chun, Zhang Ming, Ji Zhicheng, Wang Yan. Genetic Algorithm for Solving Multi-Objective Dynamic Flexible Job Shop Scheduling[J]. Journal of System Simulation, 2017, 29(8): 1647-1657.

References

[1] Chryssolouris G, Subramaniam V.Dynamic Scheduling of Manufacturing Job Shops Using Genetic Algorithms[J]. Journal of Intelligent Manufacturing (S0956-5515), 2001, 12(3): 281-293.
[2] Rangsaritratsamee R, Ferrell J R W G, Kurz M B. Dynamic Rescheduling that Simultaneously Considers Efficiency and Stability[J]. Computers & Industrial Engineering (S0360-8352), 2004, 46(1): 1-15.
[3] 潘全科, 朱剑英. 作业车间动态调度研究[J]. 南京航空天大学学报, 2005, 37(2): 262-268.
(Pan Q K, Zhu J Y.Rolling Time Horizon Job-Shop Scheduling Strategy in Dynamic Environment[J]. Journal of Nanjing University of Aeronautics & Astronautics, 2005, 37(2): 262-268.)
[4] Branke J, Mattfeld D.Anticipation and Flexibility in Dynamic Scheduling[J]. International Journal of Production Research (S0020-7543), 2005, 43(15): 3103-3129.
[5] 张超勇, 李新宇, 王晓娟, 等. 基于滚动窗口的多目标动态调度优化研究[J]. 中国机械工程, 2009, 20(18): 2190-2197.
(Zhang C Y, Li X Y, Wang X J, et al.Multi-objective Dynamic Scheduling Optimization Strategy Based on Rolling-horizon Procedure[J]. China Mechanical Engineering, 2009, 20(18): 2190-2197.)
[6] Adibi M, Zandieh M, Amiri M.Multi-Objective Scheduling of Dynamic Job Shop Using Variable Neighborhood Search[J]. Expert Systems with Applications (S0957-4174), 2010, 37(1): 282-287.
[7] 吴秀丽. 柔性作业车间动态调度问题研究[J]. 系统仿真学报, 2008, 20(14): 3828-3832.
(Wu X L.Research on Flexible Job Shop Dynamic Scheduling Problem[J]. Journal of System Simulation, 2008, 20(14): 3828-3832.)
[8] Fattahi P, Fallhi A.Dynamic Scheduling in Flexible Job Shop Systems by Considering Simultaneously Efficiency and Stability[J]. CIRP Journal of Manufacturing Science and Technology (S1755-5817), 2010, 2(2): 114-123.
[9] 刘爱军, 杨育, 刑青松, 等. 柔性作业车间多目标动态调度[J]. 计算机集成制造系统, 2011, 17(12): 2629-2637.
(Liu A J, Yang Y, Xing Q S, et al.Dynamic scheduling on multi-objective flexible job shop[J]. Computer Integrated Manufacturing Systems, 2011, 17(12): 2629-2637.)
[10] 潘颖, 孙伟, 马跃, 等. 基于多Agent的柔性作业车间调度研究[J]. 大连理工大学学报, 2011, 51(5): 667-674.
(Pan Y, Sun W, Ma Y, et al.Research on Multi-agent-based Flexible Job-shop Scheduling[J]. Journal of Dalian University of Technology, 2011, 51(5): 667-674.)
[11] Holloway C A, Nelson R T.Job Shop Scheduling with Due Dates and Variable Processing Times[J]. Management Science (S0025-1909), 1997, 20(9): 1264-1275.
[12] Guohui Zhang, Liang Gao, Yang Shi.An Effective Genetic Algorithm for the Flexible Job-Shop Scheduling Problem[J]. Expert Systems with Applications (S0957-4174), 2011, 38(4): 3563-3573.
[13] Gen M, Tsujimura Y, Kubota E.Solving Job-Shop Scheduling Problem by Genetic Algorithms[C]// Proceedings of the 1994 IEEE International Conference on Systems and Cybernetics, San Antonio, USA. USA: IEEE, 1994: 1577-1582.
[14] Yuan Y, Xu H.Multiobjective Flexible Job Shop Scheduling Using Memetic Algorithms[J]. IEEE Transactions on Automation Science and Engineering (S1545-5955), 2015, 12(1): 336-353.
[15] Gao J, Sun L Y, Gen M.A Hybrid Genetic and Variable Neighborhood Descent Algorithm for Flexible Job Shop Scheduling Problems[J]. Computer and Operations Research (S0305-0548), 2008, 35(9): 2892-2907.
[16] Lee K M, Yamakawa T.A Genetic Algorithm for General Machine Scheduling Problems[C]// Proceedings of 2nd International Conference on Knowledge-Based Intelligent Electronic Systems (KES-98), Adelaide, South Australia. USA: IEEE, 1998, 2: 60-66.
[17] 潘颖. 离散制造业MES系统建模与调度研究 [D]. 大连: 大连理工大学, 2012: 44. (Research on System Modeling and Scheduling of Manufacturing Execution System of Discrete Manufacturing Industry [D]. Dalian, China: Dalian University of Technology, 2012: 44.)
[18] Deb K, Pratap A, Agarwal S, et al.A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II[J]. IEEE Transactions on Evolutionary Computation (S1089-778X), 2002, 6(2): 182-197.