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.

Keywords

scheduling / dynamic flowshops / flowtime / heuristic / mean flowtime

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

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

RIGHTS & PERMISSIONS

2014 Higher Education Press and Springer-Verlag Berlin Heidelberg