基于遗传算法的多目标动态柔性作业车间调度

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

中图分类号:

TP183

王春, 张明, 纪志成, 王艳. 基于遗传算法的多目标动态柔性作业车间调度[J]. 系统仿真学报, 2017, 29(8): 1647-1657.

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.

参考文献

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