A polynomial algorithm to optimally schedule tasks on a virtual distributed system under tree-like precedence constraints. (English) Zbl 0689.90045

Considered is a computer system with an unbounded number of independent interchangeable processors with independent memory. The paper deals with a job scheduling problem in which the jobs are depending from each other through a tree-like structure. This means that any “root” job cannot be performed before all “branch” jobs have been performed. In this situation the jobs running on different processors must communicate with each other because of the independent memory. We assume that the maximum communication time is less than the minimum task processing time. In this case the paper gives a polynomial algorithm for the optimal job scheduling problem.
Reviewer: A.P.Bosznay


90B35 Deterministic scheduling theory in operations research
68Q25 Analysis of algorithms and problem complexity
68N25 Theory of operating systems
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
90C90 Applications of mathematical programming
Full Text: DOI


[1] Coffman, E. G., Computer and Jobshop Scheduling Theory (1976), Wiley: Wiley New York · Zbl 0359.90031
[2] Rinnooy Kan, A. H.G., Machine scheduling problems: Classification, complexity and computation, (PhD thesis (1976), Nijhoff: Nijhoff The Hague) · Zbl 0309.90026
[3] Carlier, J., Problèmes d’ordonnancement è contraintes de ressources: Algorithmes et Complexité, (Thèse d’Etat (1984), Université Paris VI)
[4] Efe, K., Heuristic models of task assignment scheduling in distributed systems, Computer, 50-56 (1982)
[5] Lo, V. M., Heuristic algorithms for task assignment in distributed systems, (San Francisco, CA. San Francisco, CA, Proceedings of the International Conference on Distributed Computing Systems (1984)), 30-39
[6] Chow, I. C.K.; Abraham, J. A., Load balancing in distributed systems, IEEE Transactions on Software Engineering, SE 8, 401-412 (1982)
[7] Sinclair, J. B., Efficient computation of optimal assignments for distributed tasks, Journal of Parallel and Distributed Computing, 4, 342-362 (1987)
[8] Garey, M.; Johnson, D. S., Computers and Intractability, a Guide to the Theory of NP-Completeness (1979), W.H. Freeman and Company: W.H. Freeman and Company New York · Zbl 0411.68039
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.