×
Rayward-Smith, V. J.; Rebaine, D.

Open shop scheduling with delays. (English) Zbl 0766.90043

RAIRO, Inform. Théor. Appl. 26, No. 5, 439-448 (1992).
Summary: The concept of interprocessor delay is introduced on the open shop model. Delays are uniform if they are always the same for any job and between any pair of machines. Scheduling an open shop with uniform delays is shown to be NP-complete even for two machines. However, if all tasks are unit execution time and the delays are uniform then a polynomial algorithm to solve the decision problem is exhibited. If the delays are nonuniform, the problem remains NP-complete.

Cited in 9 Documents

MSC:

90B35 Deterministic scheduling theory in operations research
68Q25 Analysis of algorithms and problem complexity
90C60 Abstract computational complexity for mathematical programming problems

Keywords:

interprocessor delay; open shop; NP-complete; polynomial algorithm
PDF BibTeX XML Cite
\textit{V. J. Rayward-Smith} and \textit{D. Rebaine}, RAIRO, Inform. Théor. Appl. 26, No. 5, 439--448 (1992; Zbl 0766.90043)
Full Text: DOI EuDML
  • logo of hbz
  • logo of WorldCat

References:

[1] T. GONZALEZ and S. SAHNI, Open Shop Scheduling to Minimize Finish Time, J. A.C.M., 1976, 23, pp. 665-679. Zbl0343.68031 MR429089 · Zbl 0343.68031
[2] J. J. HWANG, Y. C. CHOW, F. D. ANGERS and C. Y. LEE, Scheduling Precedence Graphs in Systems with Interprocessor Communications Times, S.I.A.M. Comput, 1989, 18, pp. 244-257. Zbl0677.68026 MR986664 · Zbl 0677.68026
[3] R. M. KARP, Reducibilities Among Combinational Problems in Complexity of Computer Computations, R. E. MILLER and J. W. THATCHER Eds., Plenum Press, New York, 1972. Zbl0366.68041 MR378476 · Zbl 0366.68041
[4] J. K. LENSTRA, Private Communication, cited in M. R. GAREY and D. S. JOHNSON Eds, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. FREEMAN, San Francisco, 1979. MR519066
[5] V. J. RAYWARD-SMITH, The complexity of Preemptive Scheduling Given Interprocessor Communication Delays, Inform. Proc. Letters, 1987 a, 25, pp. 123-125. MR896154
[6] V. J. RAYWARD-SMITH, UET Scheduling with Unit Inerprocessor Communication Delays, Discrete Appl. Math., 1987 b, 18, pp. 55-71. Zbl0634.90031 MR905178 · Zbl 0634.90031
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.