No-Wait Flowshop Scheduling Is as Hard as Asymmetric Traveling Salesman Problem

References

• Asadpour A, Goemans MX, Madry A, Oveis Gharan S, Saberi A (2010) An O(log n/log log n)-approximation algorithm for the asymmetric traveling salesman problem. SODA (SIAM, Philadelphia), 379–389.Google Scholar
• Bläser M (2008) A new approximation algorithm for the asymmetric TSP with triangle inequality. ACM Trans. Algorithms 4(4):Article No. 47.Crossref, Google Scholar
• Feige U, Singh M (2007) Improved approximation ratios for traveling salesperson tours and paths in directed graphs. Charikar M, Jansen K, Reingold O, Rolim JDP, eds. Approximation, Randomization, and Combinatorial Optimization, Lecture Notes Comput. Sci., Vol. 4627 (Springer, Berlin), 104–118.Crossref, Google Scholar
• Frieze AM, Galbiati G, Maffioli F (1982) On the worst-case performance of some algorithms for the asymmetric traveling salesman problem. Networks 12(1):23–39.Crossref, Google Scholar
• Gilmore PC, Gomory RE (1964) Sequencing a one state-variable machine: A solvable case of the traveling salesman problem. Oper. Res. 12(5):655–679.Link, Google Scholar
• Hall N, Sriskandarajah C (1996) A survey of machine scheduling problems with blocking and no-wait in process. Oper. Res. 44(3):510–525.Link, Google Scholar
• Kaplan H, Lewenstein M, Shafrir N, Sviridenko M (2005) Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs. J. ACM 52(4):602–626.Crossref, Google Scholar
• Karpinski M, Lampis M, Schmied R (2013) New inapproximability bounds for TSP. Cai L, Cheng S-W, Lam T-W, eds. Algorithms and Computation, Lecture Notes Comput. Sci., Vol. 8283 (Springer, Berlin), 568–578.Crossref, Google Scholar
• Lawler EL, Lenstra JK, Rinnooy Kan AHG, Shmoys DB (1993) Sequencing and scheduling: Algorithms and complexity. Graves SC, Rinnooy Kan AHG, Zipkin P, eds. Handbooks in Operations Research and Management Science, Volume 4: Logistics of Production and Inventory (North-Holland, Amsterdam), 445–522.Crossref, Google Scholar
• Papadimitriou CH, Kanellakis PC (1980) Flowshop scheduling with limited temporary storage. J. ACM 27(3):533–549.Crossref, Google Scholar
• Piehler J (1960) Ein Beitrag zum Reihenfolgeproblem. Unternehmensforschung 4(3):138–142.Google Scholar
• Röck H (1984) The three-machine no-wait flow shop is NP-complete. J. ACM 31(2):336–345.Crossref, Google Scholar
• Röck H, Schmidt G (1983) Machine aggregation heuristics in shop-scheduling. Math. Methods Oper. Res. 45:303–314.Google Scholar
• Spieksma FCR, Woeginger GJ (2005) The no-wait flow-shop paradox. Oper. Res. Lett. 33(6):603–608.Crossref, Google Scholar
• Sviridenko M (2003) Makespan minimization in no-wait flow shops: A polynomial time approximation scheme. SIAM J. Discrete Math. 16(2):313–322.Crossref, Google Scholar
• Williamson DP, Shmoys DB (2011) The Design of Approximation Algorithms (Cambridge University Press, New York).Crossref, Google Scholar
• Wismer DA (1972) Solution of the flow shop scheduling problem with no intermediate queues. Oper. Res. 20(3):689–697.Link, Google Scholar