Abstract
We consider the problem of scheduling tasks on flow shops when each task may also require the use of additional resources. It is assumed that all operations have unit lengths, the resource requirements are of 0–1 type and there is one type of the additional resource in the system. It is proved that when the number of machines is arbitrary, the problem of minimizing schedule length is NP-hard, even when only one unit of the additional resource is available in the system. On the other hand, when the number of machines is fixed, then the problem is solvable in polynomial time, even for an arbitrary number of resource units available. For the two machine case anO(n log 22 n) algorithm minimizing maximum lateness is also given. The presented results are also of importance in some message transmission systems.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
J. Błażewicz, Deadline scheduling of tasks with ready times and resource constraints, Inform. Process. Lett. 8 (1979) 60–63.
J. Błażewicz, J. Barcelo, W. Kubiak and H. Röck, Scheduling tasks on two processors with deadlines and additional resources. European J. on the Oper. Res. 26 (1986) 364–370.
J. Błażewicz, W. Cellary, R. Słowiński, J. Weglarz,Scheduling under Resource Constraints: Deterministic Models, Annuals of Operations Research 7 (J.C. Baltzer, Basel, 1986).
J. Błażewicz, W. Kubiak, H. Röck and J. Szwarcfiter, Minimizing mean flow time under resource constraints on parallel processors, Acta Informatica 24 (1987) 513–524.
J. Błażewicz, J.K. Lenstra and A.H.G. Rinnooy Kan, Scheduling subject to resource constraints: classification and complexity, Discrete Appl. Math. 5 (1983) 11–24.
M.R. Garey and D.S. Johnson, Complexity results for multiprocessor scheduling under resource constraints, SIAM J. on Comput. 4 (1975) 397–411.
M.R. Garey and D.S. Johnson,Computers and Intractability: A Guide to the Theory of NP-Completeness (W.H. Freeman, San Francisco, 1979).
R.L. Graham, E.L. Lawler, J.K. Lenstra and A.H.G. Rinnooy Kan, Optimization and approximation in deterministic sequencing and scheduling theory: a survey, Ann. Discrete Math. 5 (1979) 287–326.
H. Röck, Some new results in flow-shop scheduling, Zeitschrift für Oper. Res. 28 (1984) 1–16.
R. Słowiń, L'ordonnancement des tâches préemptives sur les processeurs indépendants en présence de réssources supplémentaires, RAIRO Informat. 15 (1981) 155–156.
J.D. Ullman, Complexity of sequencing problems, in:Computers and Job/Shop Scheduling Theory, ed. E.G. Coffman, Jr. (J. Wiley, New York, 1976).
D. de Werra, Preemptive scheduling linear programming and network flows, Siam J. Algebr. and Discrete Meth. 5 (1984) 11–20.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Błażewicz, J., Kubiak, W. & Szwarcfiter, J. Scheduling unit — time tasks on flow — shops under resource constraints. Ann Oper Res 16, 255–266 (1988). https://doi.org/10.1007/BF02283747
Issue Date:
DOI: https://doi.org/10.1007/BF02283747