A polynomial time approximation scheme for the two-stage multiprocessor flow shop problem

R.E. Buten, V.Y. Shen, A scheduling model for computer systems with two classes of processors, Proc. 1973 Sagamore Computing Conf. on Parallel Processing, 1973, pp. 130–138. Chen, 1994, Scheduling multiprocessor flow shops, 1 Chen, 1995, Analysis of classes of heuristics for scheduling a two-stage flow shop with parallel machines at one stage, J. Oper. Res. Soc., 46, 234, 10.1057/jors.1995.28 Garey, 1979 Garey, 1976, The complexity of flow shop and job shop scheduling, Math. Oper. Res., 1, 117, 10.1287/moor.1.2.117 Graham, 1969, Bounds on multiprocessing timing anomalies, SIAM J. Appl. Math., 17, 416, 10.1137/0117039 Gupta, 1988, Two-stage, hybrid flow shop scheduling problem, J. Oper. Res. Soc., 39, 359, 10.1057/jors.1988.63 Gupta, 1991, Schedules for a two-stage hybrid flow shop with parallel machines at the second stage, Internat. J. Production Res., 29, 1489, 10.1080/00207549108948025 L.A. Hall, Approximability of flow shop scheduling, Proc. 36th IEEE Symp. on Foundations of Computer Science, 1995, pp. 82–91. Hochbaum, 1987, Using dual approximation algorithms for scheduling problems: theoretical and practical results, J. ACM, 34, 144, 10.1145/7531.7535 Hoogeveen, 1996, Preemptive scheduling in a two-stage multiprocessor flow shop is NP-hard, European J. Oper. Res., 89, 172, 10.1016/S0377-2217(96)90070-3 Johnson, 1954, Optimal two- and three-stage production schedules with setup times included, Naval Res. Logistics Quart., 1, 61, 10.1002/nav.3800010110 Langston, 1987, Interstage transportation planning in the deterministic flow-shop environment, Oper. Res., 35, 556, 10.1287/opre.35.4.556 Lee, 1994, Minimizing makespan in hybrid flow shops, Oper. Res. Lett., 16, 149, 10.1016/0167-6377(94)90026-4 Lenstra, 1983, Integer programming with a fixed number of variables, Math. Oper. Res., 8, 10.1287/moor.8.4.538 Sahni, 1976, Algorithms for scheduling independent tasks, J. ACM, 23, 116, 10.1145/321921.321934 Schmidt, 1995, Chernoff-Hoeffding bounds for applications with limited independence, SIAM J. Discrete Math., 8, 223, 10.1137/S089548019223872X Shmoys, 1994, Improved approximation algorithms for shop scheduling problems, SIAM J. Comput., 23, 617, 10.1137/S009753979222676X Sriskandarajah, 1989, Scheduling algorithms for flexible flow shops: worst and average case performance, European J. Oper. Res., 43, 143, 10.1016/0377-2217(89)90208-7 Williamson, 1997, Short shop schedules, Oper. Res., 45, 288, 10.1287/opre.45.2.288