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.

Key words： 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