zbMATH — the first resource for mathematics

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 New York
[2] Rinnooy Kan, A.H.G., Machine scheduling problems: classification, complexity and computation, () · Zbl 0309.90026
[3] Carlier, J., Problèmes d’ordonnancement è contraintes de ressources: algorithmes et complexité, ()
[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, (), 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 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. 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.