Abstract
Flowshop scheduling problems have received considerable research attention over the last five decades. This study proposes an iterated greedy heuristic for non-permutation flowshop scheduling problems. To validate and verify the proposed heuristic, computational experiments have been conducted on a well-known benchmark problem set, and the results are compared with 20 simple constructive heuristics and a state-of-the-art meta-heuristic performed on the same benchmark instances. In terms of both solution quality and computational expense, this study successfully develops an efficient and effective approach for non-permutation flowshop scheduling problems.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Johnson SM (1954) Optimal two- and three-stage production schedules with setup times included. Nav Res Logist 1:61–68
Garey MR, Johnson DS, Sethi R (1976) The complexity of flowshop and jobshop scheduling. Math Oper Res 1:117–129
Palmer DS (1965) Sequencing jobs through a multi-stage process in the minimum total time-a quick method of obtaining a near optimum. Oper Res Q 16:101–107
Campbell HG, Dudek RA, Smith ML (1970) A heuristic algorithm for the n-job, m-machine sequencing problem. Manage Sci 16/B:630–637
Nawaz M, Enscore JEE, Ham I (1983) A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. Manage Sci 11:91–95
Koulamas C (1998) A new constructive heuristic for the flowshop scheduling problem. Eur J Oper Res 105:66–71
Ling W, Liang Z (2006) Determining optimal combination of genetic operators for flow shop scheduling. Int J Adv Manuf Technol 30:302–308
Low C, Yeh JY, Huang KI (2004) A robust simulated annealing heuristic for flow shop scheduling problems. Int J Adv Manuf Technol 23:762–767
Solimanpur M, Vrat P, Shankar R (2004) A neuro-tabu search heuristic for the flow shop scheduling problem. Computers and Operations Research 31:2151–2164
Ying KC, Liao CJ (2004) An ant colony system for permutation flow-shop sequencing. Computers and Operations Research 31:791–801
Noorul Haq A, Ravindran D, Aruna V, Nithiya S (2004) A hybridisation of metaheuristics for flow shop scheduling. Int J Adv Manuf Technol 24:376–380
Reisman A, Kumar A, Motwani J (1997) Flowshop scheduling/sequencing research: a statistical review of the literature, 1952–1994. IEEE Trans Eng Manage 44:316–329
King JR, Spachis AS (1980) Heuristics for flow-shop scheduling. Int J Prod Res 18:345–357
Park YB, Pegden CD, Enscore EE (1984) A survey and evaluation of static flowshop scheduling heuristics. Int J Prod Res 22:127–141
Turner S, Booth D (1987) Comparison of heuristics for flow shop sequencing. Omega: Int J Manag Sci 15:75–85
Hejazi SR, Saghafian S (2005) Flowshop-scheduling problems with makespan criterion: a review. Int J Prod Res 43:2895–2929
Gupta JND, Stafford EF Jr (2006) Flowshop scheduling research after five decades. Eur J Oper Res 169:699–711
Tandon M, Cummings PT, Levan MD (1991) Flowshop sequencing with non-permutation schedules. Comput Chem Eng 15:601–607
Ying KC, Lin SW (2007) Multi-heuristic desirability ant colony system heuristic for non-permutation flowshop scheduling problems. Int J Adv Manuf Technol 33:793–802
Marchiori E, Steenbeek A (2000) An evolutionary algorithm for large set covering problems with applications to airline crew scheduling. Lect Notes Comput Sci 1803:367–381
Ruiz R, Stützle T (2007) A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem. Eur J Oper Res 177:2033–2049
Graham RL, Lawler EL, Lenstra JK, Rinnooy Kan AHG (1979) Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann Discrete Math 5:287–362
Conway RL, Maxwell WL, Miller LW (1967) Theory of scheduling. Addison Wesley, Reading, MA
Hundal TS, Rajgopal J (1988) An extension of Palmer’s heuristic for the flow shop scheduling problem. Int J Prod Res 26:1119–1124
Kalczynski PJ, Kamburowski J (2007) On the NEH heuristic for minimizing the makespan in permutation flow shops. Omega: Int J Manag Sci 35:53–60
Demirkol E, Mehta S, Uzsoy R (1998) Benchmarks for shop scheduling problems. Eur J Oper Res 109:137–141
Pinedo M (1995) Scheduling: theory, algorithms and system. Prentice-Hall, New Jersey
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Ying, KC. Solving non-permutation flowshop scheduling problems by an effective iterated greedy heuristic. Int J Adv Manuf Technol 38, 348–354 (2008). https://doi.org/10.1007/s00170-007-1104-y
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00170-007-1104-y