Analysis of dispatching rules in a stochastic dynamic job shop manufacturing system with sequence-dependent setup times

Abstract

Stochastic dynamic job shop scheduling problem with consideration of sequence-dependent setup times are among the most difficult classes of scheduling problems. This paper assesses the performance of nine dispatching rules in such shop from makespan, mean flow time, maximum flow time, mean tardiness, maximum tardiness, number of tardy jobs, total setups and mean setup time performance measures viewpoint. A discrete event simulation model of a stochastic dynamic job shop manufacturing system is developed for investigation purpose. Nine dispatching rules identified from literature are incorporated in the simulation model. The simulation experiments are conducted under due date tightness factor of 3, shop utilization percentage of 90 % and setup times less than processing times. Results indicate that shortest setup time (SIMSET) rule provides the best performance for mean flow time and number of tardy jobs measures. The job with similar setup and modified earliest due date (JMEDD) rule provides the best performance for makespan, maximum flow time, mean tardiness, maximum tardiness, total setups and mean setup time measures.

Keywords

scheduling / stochastic dynamic job shop / sequence-dependent setup times / dispatching rule / simulation

References

[1] Garey M R, Johnson D S, Sethi R. The complexity of flow shop and job shop scheduling. Mathematics of Operations Research, 1976, 1(2): 117-129

[2] Xiong J, Xing L N, Chen Y W. Robust scheduling for multi-objective flexible job-shop problems with random machine breakdowns. International Journal of Production Economics, 2013, 141(1): 112-126

[3] Allahverdi A, Soroush H M. The significance of reducing setup time/setup costs. European Journal of Operational Research, 2008, 187(3): 978-984

[4] Pinedo M. Scheduling: Theory, Algorithms and Systems. Englewood cliffs: Prentice-Hall, 1995

[5] Manikas A, Chang Y L. Multi-criteria sequence-dependent job shop scheduling using genetic algorithms. Computers & Industrial Engineering, 2009, 56(1): 179-185

[6] Defersha F M, Chen M Y. Jobshop lot streaming with routing flexibility, sequence-dependent setups, machine release dates and lag time. International Journal of Production Research, 2012, 50(8): 2331-2352

[7] Haupt R. A survey of priority rule-based scheduling. Operations-Research-Spektrum, 1989, 11(1): 3-16

[8] Ramasesh R. Dynamic job shop scheduling: A survey of simulation research. Omega, 1990, 18(1): 43-57

[9] Allahverdi A, Gupta J N D, Aldowaisan T. A review of scheduling research involving setup considerations. Omega, 1999, 27(2): 219-239

[10] Panwalkar S S, Iskander W. A survey of scheduling rules. Operations Research, 1977, 25(1): 45-61

[11] Blackstone J H, Philips D T, Hogg G L. A state-of-the-art survey of dispatching rules for manufacturing job shop operations. International Journal of Production Research, 1982, 20(1): 27-45

[12] Holthaus O, Rajendran C. New dispatching rules for scheduling in a job shop: An experimental study. International Journal of Advanced Manufacturing Technology, 1997, 13(2): 148-153

[13] Jayamohan M S, Rajendran C. New dispatching rules for shop scheduling: A step forward. International Journal of Production Research, 2000, 38(3): 563-586

[14] Jain A, Jain P K, Singh I P. An investigation on the performance of dispatching rules in FMS scheduling. International Journal of Simulation Modeling, 2004, 3(2-3): 49-60

[15] Dominic P D D, Kaliyamoorthy S, Saravana Kumar M. Efficient dispatching rules for dynamic job shop scheduling. International Journal of Advanced Manufacturing Technology, 2004, 24(1-2): 70-75

[16] Wilbrecht J K, Prescott W B. The influence of setup time on job shop performance. Management Science, 1969, 16(4): 274-280

[17] Kim S C, Bobrowski P M. Impact of sequence dependent setup time on job shop scheduling performance. International Journal of Production Research, 1994, 32(7): 1503-1520

[18] Kim S C, Bobrowski P M. Scheduling jobs with uncertain setup times and sequence dependency. Omega, 1997, 25(4): 437-447

[19] Vinod V, Sridharan R. Dynamic job shop scheduling with sequence-dependent setup times: Simulation modelling and analysis. International Journal of Advanced Manufacturing Technology, 2008, 36(3-4): 355-372

[20] Baker C T, Dzielinski B P. Simulation of a simplified job shop. Management Science, 1960, 6(3): 311-323

[21] Yu X, Ram B. Bio-inspired Scheduling for dynamic job shops with flexible routing and sequence dependent setups. International Journal of Production Research, 2006, 44(22): 4793-4813

[22] Rossi A, Dini G. Flexible job shop scheduling with routing flexibility and separable setup times using ant colony optimisation method. Robotics and Computer-integrated Manufacturing, 2007, 23(5): 503-516

[23] Baykasoğlu A, Göçken M, Unutmaz Z D. New approaches to due date assignment in job shops. European Journal of Operational Research, 2008, 187(1): 31-45

[24] Rangsaritratsamee R, Ferrell W G Jr, Kurz M B. Dynamic rescheduling that simultaneously considers efficiency and stability. Computers & Industrial Engineering, 2004, 46(1): 1-15

[25] Van Parunak H. Characterizing the manufacturing scheduling problem. Journal of Manufacturing Systems, 1991, 10(3): 241-259

[26] Baker K R. Sequencing rules and due-date assignments in a job shop. Management Science, 1984, 30(9): 1093-1104

[27] Law A M, Kelton W D. Simulation Modeling and Analysis. New York: McGraw-Hill, 1991

RIGHTS & PERMISSIONS

2014 Higher Education Press and Springer-Verlag Berlin Heidelberg