Hans Röck
- 1 ARORA, R.K., AND RANA, S.P.Scheduling in a semvordered flow-shop without intermediate queues. AIIE Trans 12 (1980), 263-272.Google Scholar
- 2 GAREV, M.R., ANt> JOHNSON, D.S.Computers and Intractabdtty W.H. Freeman, San Francisco, 1979.Google Scholar
- 3 GAREY, M.R., JOHNSON, D.S., AND TARJAN, R.E.The planar Hamfltonian circmt problem is NP- complete. SIAM J Comput 5 (1976), 704--714.Google Scholar
- 4 GILMORE, P.C., AND GOMORY, R.E.Sequencing a one-state variable machine: A solvable case of the traveling salesman problem. Oper. Res 12 (1964), 655-679.Google Scholar
- 5 GONZALEZ, T.unit execution time shop problems. Math Oper. Res 7 (1982), 57-66.Google Scholar
- 6 KANELLAKIS, P.C, AND PAPADIMITRIOU, C.H.Local search for the asymmetric travehng salesman problem. Oper Res 28 (1980), 1086-1099.Google Scholar
- 7 KARP, R.M.Reducibility among combinatorial problems. In Complextty of Computer Computtons, R.E. Miller and J.W. Thatcher, Eds., Plenum, New York, 1972, pp. 85-104.Google Scholar
- 8 LENSTRA, J.K., RINNOOY K_AN, A.H.G,, AND BRUCKER, P.Complexity of machine scheduling problems. Ann Disc. Math. 1 (I977), 343-362.Google Scholar
- 9 PANWALKAR, S.S., AND WOOLLAM, C.R.Ordered flow shop problems with no in-process waiting: Further results. J Oper. Res Soc. 31 (1980), 1039-1043.Google Scholar
- 10 PAPADIMITRIOU, C.H., AND KANELLAKIS, P.C.Flowshop scheduling with limited temporary storage. J A'CM 27, 3 (July 1980), 533-549. Google Scholar
- 11 PIEHLER, J. Ein Beitrag zum Reihenfolgeproblem. Unternehmensforschung 4 (1960), 138-142.Google Scholar
- 12 REDDI, S.S., AND RAMAMOORTHY, C.V.On the flow-shop sequencing problem with no wait in process. J. Oper Res. Soc 23 (1972), 323-331.Google Scholar
- 13 ROCK, H. Three machine no-wa3t flowshop---Complexity and approximation. Rep. 82-07, Fachbereich Informatik, Technical Univ. of Berhn, Berlin, West Germany, 1982.Google Scholar
- 14 ROCK, H.Approx~mative methods for some weighted tour problems. Rep. 82-13, Fachbereieh Informatik, Technical Univ. of Berlin, Berlin, West Germany, 1982.Google Scholar
- 15 ROCK, H.Some new results in no-wait flow shop scheduling. Rep. 83-09, Fachbereieh lnformatik, Technical Umv. of Berlin, Berlin, West Germany, 1983.Google Scholar
- 16 ROCK, H., AND SCHMIDT, G.Machine aggregation heuristics in shop scheduling. Meth. Oper. Res. 45 (1983), 303-314.Google Scholar
- 17 SAHNI, S., AND CHO, Y.Complexity of scheduling shops with no wait in process. Math. Oper. ges 4 (1979), 448-457.Google Scholar
- 18 WISMER, D.A.Solutmn of the flowshop-scheduling problem w~th no intermediate queues. Oper. Res 20 (1972), 689-697.Google Scholar
Index Terms
- The Three-Machine No-Wait Flow Shop is NP-Complete
Recommendations
Two-Machine No-Wait Flow Shop Scheduling with Missing Operation
This paper considers the no-wait scheduling of n jobs in a two-machine flow shop, where some jobs require processing on the first machine only. The objective is to minimize the maximum completion time, or makespan. In view of its NP-hardness, we propose ...
Two-Machine No-Wait Flow Shop Scheduling with Missing Operations
This paper considers the no-wait scheduling of n jobs in a two-machine flow shop, where some jobs require processing on the first machine only. The objective is to minimize the maximum completion time, or makespan. In view of its NP-hardness, we propose ...
A New Heuristic for Three-Machine Flow Shop Scheduling
This paper considers the problem of sequencing n jobs in a three-machine flow shop with the objective of minimizing the makespan, which is the completion time of the last job. An On log n time heuristic that is based on Johnson's algorithm is presented. ...
Comments