Open Shop Scheduling to Minimize Finish Time

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.

REFERENCES

• 1: C. Berge, Graphs and Hypergraphs, Elsevier Science Ltd, 1985
• 2: COFFMAN, E G JR Computer and Job Shop Scheduhng Theory Wdey, New York, 1976.
• 3: CONWAY, R W , MAXWELL, W L , AND MILLER, L W Theory of Scheduhng Addison-Wesley, Readlng, Mass, 1968
• 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 1975
• 5: GONZALEZ, T, AND SAHr~I, S Flow shop and jop shop schedules Tech Rep. TR 75-14, U of Minnesota, Mmneapohs, Mmn , July 1975
• 6: HOPCROFT, J.E, AND KARP, R.M. A n5f2 algorithm for maximum matchmgs m bipartite graphs. SICOMP 2 (1973), 225-231
• 7: HOROWITZ, E., AND SAHNI, S Fundamentals of Data Structures Computer Science Press, Los Angeles, Cahf, 1976
• 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-104
• 9: LIu, C.L. lntroductton to Combinatorial Mathematics. McGraw-Hall, New York, 1968.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Scheduling

General Terms:
Algorithms, Measurement, Performance, Theory, Verification