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

DOI10.1016/0377-2217(89)90216-6zbMath0689.90045OpenAlexW2057461902MaRDI QIDQ582203

Publication date: 1989

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0377-2217(89)90216-6

zbMATH Keywords

graph polynomial algorithm distributed system independent interchangeable processors independent memory optimal job scheduling tree-like precedence constraints

Mathematics Subject Classification ID

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

Related Items (13)

Tree scheduling with communication delays ⋮ Scheduling complete intrees on two uniform processors with communication delays ⋮ Parallel Machine Scheduling with Uncertain Communication Delays ⋮ The Boolean quadratic programming problem with generalized upper bound constraints ⋮ Sensitivity bounds for machine scheduling with uncertain communication delays ⋮ Fast r-flip move evaluations via closed-form formulae for Boolean quadratic programming problems with generalized upper bound constraints ⋮ Lower bounds for the quadratic semi-assignment problem ⋮ Optimal preemptive scheduling on a fixed number of identical parallel machines ⋮ Scheduling UET-UCT outforests to minimize maximum lateness ⋮ Scheduling unitary task systems with zero--one communication delays for quasi-interval orders ⋮ A polynomially solvable class of quadratic semi-assignment problems ⋮ Scheduling inverse trees under the communication model of the LogP-machine ⋮ A standard task graph set for fair evaluation of multiprocessor scheduling algorithms

Cites Work

This page was built for publication: A polynomial algorithm to optimally schedule tasks on a virtual distributed system under tree-like precedence constraints