A job-insertion heuristic for minimizing the mean flowtime in dynamic flowshops

Abstract

A new adaptive job-insertion based heuristic is presented to minimize the mean flowtime in a dynamic flowshop consisting of m machines. Job orders arrive to the system randomly, and the job arrival or release dates are not known in advance. The heuristic is derived by inserting new jobs into the scheduled sequence as needed when the machine becomes free. Computation results indicate that the proposed heuristic performs 2.7%–10.8% better than the SPT dispatching rule, which is currently one of the most effective methods for minimizing the mean flowtime in dynamic flowshops.

Key words： scheduling; dynamic flowshops; flowtime; heuristic; mean flowtime

Acknowledgments

This work was supported by the National Key Basic Research Foundation of China (No. 2005CB724100) and the National Natural Science Foundation of China (Grant No. 50335020).

References

1 Stoop P P M, Wiers V C S. The complexity of scheduling in practice. International Journal of Operations & Production Management, 1996, 16(10): 37–53

2 MacCarthy B L, Liu J. Addressing the gap in scheduling research: A review of optimization and heuristic methods in production scheduling. International Journal of Production Research, 1993, 31(1): 59–79

3 Dudek R A, Panwalkar S S, Smith M L. The lessons of flowshop scheduling research. Operations Research, 1992, 40(1): 7–13

4 Rajendran C, Ziegler H. An efficient heuristic for scheduling in a flowshop to minimize total weighted flowtime of jobs. European Journal of Operational Research, 1997, 103(1): 129–138

5 Palmer D S. Sequencing jobs through a multistage process in the minimum total time: A quick method of obtaining a near-optimum. Operational Research Quarterly, 1965, 16(1): 101–107

6 Campbell H G, Dudek R A, Smith M L. A heuristic algorithm for the n-job, m-machine sequencing problem. Management Science, 1970, 16(10): B630–B637

7 Dannenbring D G. An evaluation of flowshop sequence heuristics. Management Science, 1977, 23(11): 1174–1182

8 Nawaz M, Enscore E E Jr, Ham I. A heuristic algorithm for the m-machine, n-job flowshop sequencing problem. Omega, 1983, 11(1): 91–95

9 Gupta J N D. Heuristic algorithms for multistage flowshop scheduling problem. AIIE Transactions, 1972, 4(1): 11–18

10 Rajendran C. Heuristic algorithm for scheduling in a flowshop to minimize total flowtime. International Journal of Production Economics, 1993, 29(1): 65–73

11 Ho J C. Flowshop sequencing with mean flowtime objective. European Journal of Operational Research, 1995, 81(3): 571–578

12 Woo D S, Yim H S. A heuristic algorithm for mean flowtime objective in flowshop scheduling. Computers & Operations Research, 1998, 25(3): 175–182

13 Framinan J M, Leisten R, Ruiz-Usano R. Efficient heuristics for flowshop sequencing with the objectives of makespan and flowtime minimisation. European Journal of Operational Research, 2002, 141(3): 559–569

14 Framinan J M, Gupta J N D, Leisten R. A review and classification of heuristics for permutation flow-shop scheduling with makespan objective. Journal of the Operational Research Society, 2004, 55(12): 1243–1255

15 Ruiz R, Maroto C. A comprehensive review and evaluation of permutation flowshop heuristics. European Journal of Operational Research, 2005, 165(2): 479–494

16 Holthaus O, Rajendran C. Efficient dispatching rules for scheduling in a job shop. International Journal of Production Economics, 1997, 48(1): 87–105

17 Thiagarajan S, Rajendran C. Scheduling in dynamic assembly job-shops to minimize the sum of weighted earliness, weighted tardiness and weighted flowtime of jobs. Computers & Industrial Engineering, 2005, 49(4): 463–503

18 Sabuncuoglu I. A study of scheduling rules of flexible manufacturing systems: a simulation approach. International Journal of Production Research, 1998, 36(2): 527–546

19 Rajendran C, Holthaus O. A comparative study of dispatching rules in dynamic flowshops and jobshops. European Journal of Operational Research, 1999, 116(1): 156–170

20 Rajendran C, Ziegler H. A performance analysis of dispatching rules and a heuristic in static flowshops with missing operations of jobs. European Journal of Operational Research, 2001, 131(3): 622–634

21 Lodree E Jr, Jang W, Klein C M. A new rule for minimizing the number of tardy jobs in dynamic flow shops. European Journal of Operational Research, 2004, 159(1): 258–263

22 Branke J, Mattfeld D C. Anticipation and flexibility in dynamic scheduling. International Journal of Production Research, 2005, 43(15): 3103–3129

23 Elbouri A, Balakrishnan S, Popplewell N. Cooperative dispatching for minimizing mean flowtime in a dynamic flowshop. International Journal of Production Economics, 2008, 113(2): 819–833

24 Rajendran C, Alicke K. Dispatching in owshops with bottleneck machines. Computers & Industrial Engineering, 2007, 52(1): 89–106

25 Framinan J M, Leisten R, Rajendran C. Different initial sequences for the heuristic of Nawaz, Enscore and Ham to minimize makespan, idletime or flowtime in the static permutation flowshop sequencing problem. International Journal of Production Research, 2003, 41(1): 121–148

26 Karsiti M N, Cruz J B, Mulligan J H. Simulation studies of multilevel dynamic job shop scheduling using heuristic dispatching rules. Journal of Manufacturing Systems, 1992, 11(5): 346–358

27 Pegden C D, Shannon R E, Sadowski R P. Introduction to Simulation Using SIMAN. New York: McGraw-Hill, 1995

28 Blachstone J H, Phillips D T, Hogg G L. Astate-of-the-art survey of dispatching rules for manufacturing job shop operations. International Journal of Production Research, 1982, 20(1): 27–45