A review and classification of heuristics for permutation flow-shop scheduling with makespan objective

Graham RL, Lawler EL, Lenstra JK and Rinnooy Kan AHG (1979). Optimisation and approximation in deterministic sequencing and scheduling: a survey. Ann Discrete Math 5: 287–326. Dudek RA and Teuton OF (1964). Development of m stage decision rule for scheduling n jobs through m machines. Opns Res 12: 471–497. Szwarc W (1971). Elimination methods in the m × n sequencing problem. Naval Res Logist 18: 295–305. Lageweg BJ, Lenstra JK and Rinnooy Kan AHG (1978). A general bounding scheme for the permutation flowshop problem. Opns Res 26: 53–67. Potts CN (1980). An adaptive branching rule for the permutation flowshop problem. Eur J Opl Res 5: 19–25. Carlier J and Rebaï I (1996). Two branch and bound algorithms for the permutation flowshop problem. Eur J Opl Res 90: 238–251. Garey MR, Johnson DS and Sethi R (1976). The complexity of flowshop and jobshop scheduling. Math Opns Res 1: 117–129. Rinnooy Kan AHG (1976). Machine Scheduling Problems. Martinus Nijhoff: The Hague. Gupta JND (1971). Flowshop scheduling via sorting analogy. UARI Research Report No. 109, University of Alabama in Huntsville, USA. Pinedo M (1995). Scheduling: Theory, Algorithms and Systems. Prentice-Hall: Englewood Cliffs, NJ. Lourenço HR (1996). Sevast'yanov's algorithm for the flow-shop scheduling problem. Eur J Opl Res 91: 176–189. Gupta JND (1979). A review of flowshop scheduling research. In: Ritzman LP, Krajewski LJ, Berry WL, Goodman SM, Hardy ST, Vitt LD (eds). Disaggregation Problems in Manufacturing and Service Operations. Martin Nijhoff Publishers, The Hague, Netherlands, pp 363–388. King JR and Spachis AS (1980). Heuristics for flow-shop scheduling. Int J Prod Res 18: 345–357. Park YB, Pegden CD and Enscore EE (1984). A survey and evaluation of static flowshop scheduling heuristic. Int J Prod Res 22: 127–141. Widmer M and Hertz A (1991). A new heuristic method for the flow-shop sequencing problem. Eur J Opl Res 41: 186–193. Moccellin JV (1995). A new heuristic method for the permutation flow-shop scheduling problem. J Opl Res Soc 46: 883–886. Nawaz M, Enscore EE and Ham I (1983). A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. Omega-Int J Mngt Sci 11: 91–95. Palmer DS (1965). Sequencing jobs through a multistage process in the minimum total time: a quick method of obtaining a near-optimum. Opns Res Quart 16: 101–107. Campbell HG, Dudek RA and Smith ML (1970). A heuristic algorithm for the n-job, m-machine sequencing problem. Mngt Sci 16: B630–B637. Gupta JND (1971). A functional heuristic for the flow-shop scheduling problem. Opns Res Quart 22: 39–47. Gupta JND (1968). Heuristic rules for n × m flowshop scheduling problem. Opsearch (India) 5: 165–170. Gupta JND (1972). Heuristic algorithms for multistage flowshop scheduling problem. AIIE Trans 4: 11–18. Röck H and Schmidt G (1983). Machine aggregation heuristics in shop-scheduling. Methods Opl Res 45: 303–314. Page ES (1961). An approach to the scheduling of jobs on machines. J R Stat Soc 24: 484–492. Morton TE and Pentico DW (1993). Heuristic Scheduling Systems. Wiley: New York. Ashour S (1967). A decomposition approach for the machine scheduling problem. Int J Prod Res 6: 109–122. Ashour S (1970). A modified decomposition algorithm for scheduling problems. Int J Prod Res 8: 281–284. Gupta JND and Maykut AR (1973). Flow-shop scheduling by heuristic decomposition. Int J Prod Res 11: 105–111. Averbakh I and Berman O (1999). A simple heuristic for m-machine flow-shop and its applications in routing-scheduling problems. Opns Res 47: 165–170. Azim MA, Moras RG and Smith ML (1989). Antithetic sequences in flow shop scheduling. Comput Indust Eng 17: 353–358. Hundal TS and Rajgopal J (1988). An extension of Palmer heuristic for the flow shop scheduling problem. Int J Prod Res 26: 1119–1124. Gupta JND (1976). A heuristic algorithm for the flowshop scheduling problem. RAIRO Rech Opér 10: 63–73. Bonney MC and Gundry SW (1976). Solutions to the constrained flowshop sequencing problem. Opns Res Quart 27: 869–883. Koulamas C (1998). A new constructive heuristic for the flowshop scheduling problem. Eur J Opl Res 105: 66–71. Burns F and Rooker J (1976). Johnson's three machine flow-shop conjecture. Opns Res 24: 578–580. Johnson SM (1954). Optimal two- and three-stage production schedule with setup times included. Naval Res Logist 1: 61–68. Dannenbring DG (1977). An evaluation of flow-shop sequence heuristics. Mngt Sci 23: 1174–1182. Selim SZ and Al-Turki UM (1987). A new heuristic algorithm for the flowshop problem. In: Kusiak A (ed). Modern Production Management Systems. Elsevier Science, Amsterdam, pp 91–96. Lai T (1996). A note on heuristics of flow-shop scheduling. Opns Res 44: 648–652. Gupta JND (1968). Travelling salesman problem—a survey of theoretical developments and applications. Opsearch (India) 5: 181–192. Stinson JP and Smith W (1982). A heuristic programming procedure for sequencing the static flowshop. Int J Prod Res 20: 753–764. Stinson JP (1977). A heuristic algorithm for obtaining an initial solution for the travelling salesman problem. Working Paper 77-12, School of Management, Syracuse University. Sevast'janov S (1995). Vector summation in Banach space and polynomial algorithms for flow shops and open shops. Math Opns Res 20: 90–103. Lawler EL, Lenstra JK, Rinnooy Kan AHG and Shmoys DB (1993). Sequencing and scheduling: algorithms and complexity. In: Graves SC, Rinnooy Kan AHG and Zipkin PH (eds). Logistics of Production and Inventor. North-Holland, Amsterdam, pp 445–522. Sarin S and Lefoka M (1993). Scheduling heuristic for the n-job m-machine flow shop. Omega-Int J Mngt Sci 21: 229–234. Aggarwal SC and Stafford E (1975). A heuristic algorithm for the flowshop problem with a common sequence on all machines. Dec Sci 6: 237–251. Woo DS and Yim HS (1998). A heuristic algorithm for mean flowtime objective in flowshop scheduling. Comput Opns Res 25: 175–182. McCormick ST, Pinedo ML, Shenker S and Wolf B (1989). Sequencing in an assembly line with blocking to minimize cycle time. Opns Res 37: 925–936. Sridhar J and Rajendran C (1996). Scheduling in flowshop an cellular manufacturing systems with multiple objectives—a genetic algorithmic approach. Prod Plan Control 7: 374–382. Rajendran C (1993). Heuristic algorithm for scheduling in a flowshop to minimise total flowtime. Int J Prod Econ 29: 65–73. Taillard E (1990). Some efficient heuristic methods for the flow-shop sequencing problem. Eur J Opl Res 47: 65–74. Gupta JND and Maykut AR (1973). Heuristic algorithms for scheduling n jobs in a flowshop. J Opl Res Soc Japan 16: 131–150. Nowicki E and Smutnicki C (1996). A fast tabu search algorithm for the permutation flow-shop problem. Eur J Opl Res 91: 160–175. Stützle T (1998). An ant approach for the flow shop problem. ELITE Foundation (ed). Proceedings of EUFIT'98 Aachen, Germany. Verlag Mainz, Aachen, Germany, pp. 1560–1564. Ho JC and Chang YL (1991). A new heuristic for the n-job, m-machine flow-shop problem. Eur J Opl Res 52: 194–202. Osman IH and Potts CN (1989). Simulated annealing permutation flow-shop scheduling. Omega-Int J Mngt Sci 17: 551–557. Ogbu FA and Smith DK (1990). The application of the simulated annealing algorithm to the solution of the n/m/Cmax flowshop problem. Comput Opns Res 17: 243–253. Ogbu FA and Smith DK (1991). Simulated annealing algorithm for the permutation flowshop problem. Omega-Int J Mngt Sci 19: 64–67. Zegordi SH, Itoh K and Enkawa T (1995). Minimizing makespan for flow-shop scheduling by combining simulated annealing with sequencing knowledge. Eur J Opl Res 85: 515–531. Grabowski J and Pempera J (2001). New block properties for the permutation flow shop problem with application in TS. J Opl Res Soc 52: 210–220. Reeves CR (1995). A genetic algorithm for flowshop sequencing. Comput Opns Res 22: 5–13. Murata T, Ishibuchi H and Tanaka H (1996). Genetic algorithms for flowshop scheduling problems. Comput Indust Eng 30: 1061–1071. Reeves CR and Yamada T (1998). Genetic algorithms, path relinking and the flowshop sequencing problem. Evol Comput 6: 230–234. Chen CL, Vempati VS and Aljaber N (1995). An application of genetic algorithms for flow shop problem. Eur J Opl Res 80: 389–396. Werner F (1993). On the heuristic solution of the permutation flow shop problem by path algorithms. Comput Opns Res 20: 707–722. Turner S and Booth D (1987). Comparison of heuristics for flowshop sequencing. Omega-Int J Mngt Sci 15: 75–85. Smith AW and Stafford EF (1980). A comparison of multiple criteria solutions of large-scale flow-shop scheduling problems. American Institute of Decision Science (ed). AIDS 1980 Proceedings, Vol. 2. American Institute of Decision Science, Las Vegas, NV, pp. 35–37. Framinan JM, Leisten R and Rajendran C (2003). Different initial sequences for the heuristic of Nawaz, Enscore and Ham to minimize makespan, idletime or flowtime in the static permutation flowshop sequencing problem. Int J Prod Res 41: 121–148. Amar AD and Gupta JND (1986). Simulated versus real life data in testing the efficiency of scheduling algorithms. IIE Trans 18: 16–25. Conway RW, Maxwell WL and Miller LW (1967). Theory of Scheduling. Addison-Wesley: Reading, MA. Watson JP, Barbulescu L, Whitley LD and Howe AE (2002). Contrasting structured and random permutation flow-shop scheduling problems: search space topology and algorithm performance. INFORMS J Comput 14: 98–123. Taillard E (1993). Benchmark for basic scheduling problems. Eur J Opl Res 64: 278–285. Bestwick P and Hastings N (1976). A new bound for machine scheduling. Opns Res Quart 27: 479–487. Lahiri S, Rajendran C and Narendran TT (1993). Evaluation of heuristics for scheduling in a flowshop: a case study. Prod Plan Control 4: 153–158. Reeves CR (1993). Improving the efficiency of tabu search for machine sequencing problem. J Opl Res Soc 44: 375–382. Reeves CR (1999). Landscapes, operators and heuristic search. Ann Opns Res 86: 473–490.