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

DOI10.1016/0377-2217(89)90216-6MaRDI QIDQ582203zbMATH OpenOpenAlexFDO

Authors Philippe Chrétienne

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

distributed systemgraphindependent interchangeable processorsindependent memoryoptimal job schedulingpolynomial algorithmtree-like precedence constraints

Mathematics Subject Classification ID

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

Review text

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.

Recommendations

• Scheduling tasks and communications on a virtual distributed system
• Tree scheduling with communication delays
• Optimal scheduling of unit-time tasks on two uniform processors under tree-like precedence constraints
• Scheduling tasks with communication delays on parallel processors
• On Stochastic Scheduling with In-Tree Precedence Constraints

Cited in

(17)

• A polynomially solvable class of quadratic semi-assignment problems
• Scheduling tasks and communications on a virtual distributed system
• Scheduling inverse trees under the communication model of the LogP-machine
• A fully polynomial approximation scheme for a scheduling problem with intree-type precedence delays
• Tree scheduling with communication delays
• Scheduling complete intrees on two uniform processors with communication delays
• Lower bounds for the quadratic semi-assignment problem
• The Boolean quadratic programming problem with generalized upper bound constraints
• Scheduling UET-UCT outforests to minimize maximum lateness
• Scheduling unitary task systems with zero--one communication delays for quasi-interval orders
• A standard task graph set for fair evaluation of multiprocessor scheduling algorithms
• Optimal preemptive scheduling on a fixed number of identical parallel machines
• Fast r-flip move evaluations via closed-form formulae for Boolean quadratic programming problems with generalized upper bound constraints
• Parallel Machine Scheduling with Uncertain Communication Delays
• A fixed-parameter algorithm for scheduling unit dependent tasks with unit communication delays
• Bounds and algorithms for a practical task allocation model (extended abstract)
• Sensitivity bounds for machine scheduling with uncertain communication delays

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q582203)