A polynomial algorithm to optimally schedule tasks on a virtual distributed system under tree-like precedence constraints.

*(English)*Zbl 0689.90045Considered 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

##### MSC:

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 |

##### Keywords:

tree-like precedence constraints; graph; distributed system; independent interchangeable processors; independent memory; polynomial algorithm; optimal job scheduling
PDF
BibTeX
XML
Cite

\textit{P. Chrétienne}, Eur. J. Oper. Res. 43, No. 2, 225--230 (1989; Zbl 0689.90045)

Full Text:
DOI

**OpenURL**

##### References:

[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.