Teofilo Gonzalez
Sartaj Sahni
Abstract
A linear time algorithm to obtain a minimum finish time schedule for the two-processor open shop together with a polynomial time algorithm to obtain a minimum finish time preemptive schedule for open shops with more than two processors are obtained. It is also shown that the problem of obtaining minimum finish time nonpreemptive schedules when the open shop has more than two processors is NP-complete.
- 1 BERGE, C Graphs and Hypergraphs American Elsevzer, New York, 1973, p 134 Google Scholar
- 2 COFFMAN, E G JR Computer and Job Shop Scheduhng Theory Wdey, New York, 1976.Google Scholar
- 3 CONWAY, R W , MAXWELL, W L , AND MILLER, L W Theory of Scheduhng Addison-Wesley, Readlng, Mass, 1968Google Scholar
- 4 GAREY, M R, JOHNSON, D , AND SETHI, R Complexity of flow shop and job shop scheduhng. Tech Rep 168, Pennsylvama State U , Umvers~ty Park, Pa, June 1975Google Scholar
- 5 GONZALEZ, T, AND SAHr~I, S Flow shop and jop shop schedules Tech Rep. TR 75-14, U of Minnesota, Mmneapohs, Mmn , July 1975Google Scholar
- 6 HOPCROFT, J.E, AND KARP, R.M. A n5f2 algorithm for maximum matchmgs m bipartite graphs. SICOMP 2 (1973), 225-231Google Scholar
- 7 HOROWITZ, E., AND SAHNI, S Fundamentals of Data Structures Computer Science Press, Los Angeles, Cahf, 1976Google Scholar
- 8 KARP, R.M. Reduclbthty among combmatortal problems. In Complextty of Computer Computattons, R E Mdler and J W Thatcher, Eds , Plenum Press, New York, 1972, pp 85-104Google Scholar
- 9 LIu, C.L. lntroductton to Combinatorial Mathematics. McGraw-Hall, New York, 1968.Google Scholar
Index Terms
- Open Shop Scheduling to Minimize Finish Time
Recommendations
A cyclical search for the two machine flow shop and open shop to minimise finishing time
This paper considers scheduling problems on two machines to minimise the makespan. It shows that a simple cyclical search can find a flow shop schedule with one job omitted with makespan less than or equal to the maximum of the total processing time of ...
Concurrent open shop scheduling to minimize the weighted number of tardy jobs
We consider a relaxed version of the open shop scheduling problem--the "concurrent open shop" scheduling problem, in which any two operations of the same job on distinct machines are allowed to be processed concurrently. The completion time of a job is ...
Scheduling the Open Shop to Minimize Mean Flow Time
It is shown that the problem of scheduling a two-processor n-job open shop nonpreemptively in order to minimize mean flow time is NP-complete even if input length is measured by the sum of the task lengths. The proof is similar in approach to that used by ...
Comments