Performance guarantees for flowshop heuristics to minimize makespan

Averbakh, 1999, A simple heuristic for m-machine flow-shop and its applications in routing-scheduling problems, Operations Research, 47, 165, 10.1287/opre.47.1.165 Barany, 1981, A vector-sum theorem and its application to improving flow shop guarantees, Mathematics of Operations Research, 6, 445, 10.1287/moor.6.3.445 Campbell, 1970, A heuristic algorithm for the n job m machine sequencing problem, Management Science, 16, B630, 10.1287/mnsc.16.10.B630 Chen, 1996, A new heuristic for three-machine flow shop scheduling, Operations Research, 44, 891, 10.1287/opre.44.6.891 Coffman, 1985, On the expected relative performance of list scheduling, Operations Research, 33, 548, 10.1287/opre.33.3.548 Dannenbring, 1977, An evaluation of flow-shop sequencing heuristics, Management Science, 23, 1174, 10.1287/mnsc.23.11.1174 Dushin, 1980, Note on the algorithm for Johnson’s single route problem, Cybernetics, 16, 300, 10.1007/BF01069124 Framinan, 2004, A review and classification of heuristics for permutation flowshop scheduling with makespan objective, Journal of Operational Research Society, 55, 1243, 10.1057/palgrave.jors.2601784 Garey, 1976, The complexity of flowshop and jobshop scheduling, Mathematics of Operations Research, 1, 117, 10.1287/moor.1.2.117 Gonzalez, 1978, Flowshop and jobshop schedules: Complexity and approximation, Operations Research, 26, 36, 10.1287/opre.26.1.36 Gupta, J.N.D., 1971a. Flowshop scheduling via sorting analogy. UARI Report No. 109, University of Alabama in Huntsville, Huntsville, AL, USA. Gupta, 1971, A functional heuristic algorithm for the flow-shop scheduling problem, Operational Research Quarterly, 22, 39, 10.1057/jors.1971.18 Gupta, 1972, Heuristic algorithms for multistage flowshop scheduling problem, AIIE Transactions, 4, 11, 10.1080/05695557208974823 Gupta, J.N.D., 1974. Flowshop scheduling via sorting analogy: multi-sorting algorithms, ORSA/TIMS Joint Meeting, San Juan, Puerto Rico, 16–18 October 1974. Gupta, 1975, Optimal schedules for special structure flowshops, Naval Research Logistics Quarterly, 26, 255, 10.1002/nav.3800220205 Gupta, 1976, A heuristic algorithm for the flowshop scheduling problem, Revue Francaise d’Automatique, Informatique, Recherche Operationnelle, 10, 63, 10.1051/ro/197610V200631 Gupta, 1979, A review of flowshop scheduling research, 359 Gupta, J.N.D., Smutnicki, C., in preparation. Flowshop scheduling via sorting analogy: Selected worst-case analysis, Working Research Paper. Hall, 1998, Approximability of flow-shop scheduling, Mathematical Programming, 82, 175, 10.1007/BF01585870 Hundal, 1988, An extension of palmer’s heuristic for the flow-shop scheduling problem, International Journal of Production Research, 26, 1119, 10.1080/00207548808947922 Johnson, 1954, Optimal two- and three-stage production schedules with setup times included, Naval Research Logistics Quarterly, 1, 61, 10.1002/nav.3800010110 King, 1980, Heuristics for flow-shop scheduling, International Journal of Production Research, 18, 345, 10.1080/00207548008919673 Koulamas, 2000, Asymptotically optimal linear time algorithms for two-stage and three-stage flexible flow shops, Naval Research Logistics, 47, 259, 10.1002/(SICI)1520-6750(200004)47:3<259::AID-NAV5>3.0.CO;2-K Lai, 1996, A note on heuristics of flow-shop scheduling, Operations Research, 44, 648, 10.1287/opre.44.4.648 Lawler, 1993, Sequencing and scheduling: Algorithms and complexity, Vol. 4, 445, 10.1016/S0927-0507(05)80189-6 Lourenco, 1996, Sevast’yanov’s algorithm for the flow-shop scheduling problem, European Journal of Operational Research, 91, 176, 10.1016/0377-2217(94)00356-4 Nabeshima, 1963, On bounds of makespan and its application in M-machine scheduling problems, Journal of Operational Research Society of Japan, 9, 98 Nawaz, 1983, A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem, OMEGA, 11, 91, 10.1016/0305-0483(83)90088-9 Nowicki, 1999, Tabu search method in job scheduling problems, 1 Nowicki, 1989, Worst-case analysis of an approximation algorithm for flow-shop scheduling, Operations Research Letters, 8, 171, 10.1016/0167-6377(89)90045-X Nowicki, 1991, Worst-case analysis of Dannenbring’s algorithm for flow-shop scheduling, Operations Research Letters, 10, 473, 10.1016/0167-6377(91)90025-K Nowicki, 1993, New results in the worst-case analysis for flow-shop scheduling, Discrete Applied Mathematics, 46, 21, 10.1016/0166-218X(93)90156-I Nowicki, 1994, A note on worst-case analysis of approximation algorithms for a scheduling problem, European Journal of Operational Research, 74, 128, 10.1016/0377-2217(94)90210-0 Page, 1961, An approach to scheduling jobs on machines, Journal of the Royal Statistical Society, 23, 484 Palmer, 1965, Sequencing jobs through a multi-stage process in the minimum total time—a quick method of obtaining a near optimum, Operational Research Quarterly, 16, 101, 10.1057/jors.1965.8 Potts, 1991, Permutation vs. non-permutation flow-shop schedules, Operations Research Letters, 10, 281, 10.1016/0167-6377(91)90014-G Röck, 1983, Machine aggregation heuristics in shop scheduling, Methods of Operations Research, 45, 303 Sevast’janov, 1980, Approximation algorithms for Johnson’s and vector summation problems, Upravlyaemye Systemy, 20, 64 Sevast’janov, 1981, Some generalizations of the Johnson problem, Upravlyaemye Systemy, 21, 45 Sevast’janov, 1982, Algorithms with estimates for the Johnson and Akers-Friedman problems in the case of three machines, Upravlyaemye Systemy, 22, 51 Sevast’janov, 1994, On some geometric methods in scheduling theory: A survey, Discrete Applied Mathematics, 55, 59, 10.1016/0166-218X(94)90036-1 Sevast’janov, 1995, Vector summation in Banach space and polynomial algorithms for flow shops and open shops, Mathematics of Operations Research, 20, 90, 10.1287/moor.20.1.90 Sevast’janov, 1997, Nonstrict vector summation in the plane and its application to scheduling problems, 241 Shmoys, 1994, Improved approximation algorithms for shop scheduling problems, SIAM Journal on Computing, 23, 617, 10.1137/S009753979222676X Smutnicki, 1998, Some results of the worst-case analysis for flow shop scheduling, European Journal of Operational Research, 109, 66, 10.1016/S0377-2217(97)00139-2 Williamson, 1997, Short stop schedules, Operations Research, 45, 288, 10.1287/opre.45.2.288