Multi-objective Flexible Job Shop Dynamic Scheduling Strategy Aiming at Scheduling Stability and Robustness

Abstract

Abstract: A dynamic FJSP aiming at scheduling stability and robustness was studied. Firstly, an optimization mathematical model was proposed based on scheduling stability and robustness. Secondly, by analyzing characteristics of dynamic FJSP, a job arrival generator and a predictive maintenance generator of machine breakdown were presented. In each rescheduling points, periodic and event driven rescheduling strategies were employed, and a complete rescheduling strategy combined with right-shift rescheduling strategy was proposed. In order to preserve the good characteristics of paternal generations, an improved differential evolution algorithm was designed to solve the dynamic FJSP. The validity of the proposed strategies and algorithm was verified by instances.

Key words: flexible job-shop scheduling problem(FJSP), multi-objective, dynamic schedule, robustness, differential evolution algorithm

摘要： 研究了以调度稳定性和鲁棒性为优化目标的柔性作业车间动态调度问题。建立了多目标柔性作业车间动态调度问题模型；针对动态事件特点，采用工件到达发生器和机器故障预维护发生器模拟动态事件，提出了基于周期与事件驱动的混合重调度策略，该策略在每个重调度点对工件进行完全重调度或右移重调度；为克服传统差分算法早熟的缺点，设计了一种改进的多目标差分进化算法求解该调度问题；实例验证了提出策略和算法的有效性。

关键词: 柔性作业车间动态调度问题, 多目标, 动态调度, 稳健性, 差分进化

CLC Number:

TP18

ZHU Chuanjun, QIU Wen, ZHANG Chaoyong, JIN Liangliang. Multi-objective Flexible Job Shop Dynamic Scheduling Strategy Aiming at Scheduling Stability and Robustness[J]. China Mechanical Engineering.

朱传军, 邱文, 张超勇, 金亮亮. 多目标柔性作业车间稳健性动态调度研究[J]. 中国机械工程.

References

[1]潘全科，朱剑英. 作业车间动态调度研究[J]. 南京航空航天大学学报,2005，37(2):262-268.
PAN Quanke, ZHU Jianying. Rolling Time Horizon Job-Shop Scheduling Strategy in Dynamic Environment[J]. Journal of Nanjing University of Aeronautics & Astronautics, 2005, 37(2): 262-268.
[2]ADIBI M A, ZANDIEH M, AMIRI M. Multi-objective Scheduling of Dynamic Job Shop Using Variable Neighborhood Search[J]. Expert Systems with Applications, 2010, 37(1):282-287.
[3]HE W, SUN D H. Scheduling Flexible Job Shop Problem Subject to Machine Breakdown with Route Changing and Right-shift Strategies[J]. Int. J. Adv. Manuf. Technol., 2013, 66 (1):501-514.
[4]FANG J, XI Y. A Rolling Horizon Job Shop Rescheduling Strategy in the Dynamic Environment[J]. Int. J. Adv. Manuf. Technol., 1997, 13(3): 227-232.
[5]LI J Q, PAN Q K, FATIH TASGETIREN M. A Discrete Artificial Bee Colony Algorithm for Multi-objective Flexible Job Shop Scheduling Problems with Maintenance Activities[J]. Applied Mathematical Modelling, 2014, 38: 1111-1132.
[6]FATTAHI P, FALLAHI A. Dynamic Scheduling in Flexible Job Shop Systems by Considering Simultaneously Efficiency and Stability[J] .CIRP Journal of Manufacturing Science and Technology, 2010, 2(2): 114-123.
[7]XIONG J, XING L N, CHEN Y W. Robust Scheduling for Multi-objective Flexible Job-shop Problems with Random Machine Breakdowns[J]. Int. J. Production Economics, 2013, 141: 112-126.
[8]AL-HINAI N, ELMEKKAWY T Y. Robust and Stable Flexible Job Shop Scheduling with Random Machine Breakdowns Using a Hybrid Genetic Algorithm[J]. Int. J. Production Economics, 2011, 132: 279-291.
[9]ZHANG L P, GAO L, LI X Y. A Hybrid Genetic Algorithm and Tabu Search for a Multi-objective Dynamic Job Shop Scheduling Problem[J].International Journal of Production Research,2013,51(12): 3516-3531.
[10]CHURCH L K, UZSOY R. Analysis of Periodic and Event-driven Rescheduling Policies in Dynamic Shops[J]. International Journal of Computer Integrated Manufacturing, 1992, 5(3): 153-163.
[11]张超勇，李新宇，王晓娟，等.基于滚动窗口的多目标动态调度优化研究[J].中国机械工程，2009, 20(18): 2190-2197.
ZHANG Chaoyong, LI Xinyu, WANG Xiaojuan, et al. Multi-objective Dynamic Scheduling Optimization Strategy Based on Rolling-horizon Procedure[J]. China Mechanical Engineering, 2009, 20(18): 2190-2197.
[12]张利平. 作业车间预反应式动态调度理论与方法研究[D].武汉：华中科技大学，2013.
ZHANG Liping. Research on Theories and Methods for Dynamic Job Shop Scheduling Based on Predictive-reactive Scheduling[D].Wuhan：Huazhong University of Science and Technology，2013.
[13]LI J Q, PAN Q K,SUGANTHAN P N, et al. A Hybrid Tabu Search Algorithm with an Efficient Neighborhood Structure for the Flexible Job Shop Scheduling Problem[J]. Int. J. Adv. Manuf. Technol., 2011, 52: 683-697.
[14]KARSITI M N, CRUZ J B, MULLIGAN J H. Simulation Studies of Mutilevel Dynamic Job Shop Scheduling Using Heuristic Dispatching Rules[J]. Journal of Manufacturing Systems, 1992,11(5):346-358.
[15]XUE F, SANDERSON A C, GRAVES R J. Pareto-based Multi-objective Differential Evolution[C]//Proceedings of the Congress on Evolutionary Computation. Washington D C, 2003: 862-869.
[16]YUAN Y, XU H. Flexible Job Shop Scheduling Using Hybrid Differential Algorithms[J]. Journal of Intelligent Manufacturing, 2007, 18(3):331-342.
[17]LI J Q, PAN Q K, LIANG Y C. An Effective Hybrid Tabu Search Algorithm for Multi-objective Flexible Job Shop Scheduling Problems[J]. Comput. Int. Eng., 2010, 59: 647-662.
[18]刘炜琪, 刘琼，张超勇，等. 基于混合粒子群算法求解多目标混流装配线排序[J]. 计算机集成制造系统, 2011, 17(12): 2590-2598.
LIU Weiqi, LIU Qiong, ZHANG Chaoyong, et al.Hybrid Particle Swarm Optimization for Multy-objective Sequencing Problem in Mixed Model Assembly Lines[J]. Computer Intergraded Manufacturing Systems, 2011, 17(12): 2590-2598.
[19]ZHANG G H, SHAO X Y, LI P G, et al. An Effective Hybrid Particle Swarm Optimization Algorithm for Multi-objective Flexible Job-shop Scheduling Problem[J]. Computers & Industrial Engineering, 2009, 56: 1309-1318.
[20]张超勇，董星，王晓娟，等. 基于改进非支配遗传算法的多目标柔性作业车间调度[J]. 机械工程学报，2010, 46(11):156-164.
ZHANG Chaoyong, DONG Xing, WANG Xiaojuan, et al. Improved NSGA-II for the Multi-objective Flexible Job Shop Scheduling Problem[J]. Journal of Mechanical Engineering, 2010, 46(11): 156-164.