A polynomial algorithm to optimally schedule tasks on a virtual distributed system under tree-like precedence constraints
DOI10.1016/0377-2217(89)90216-6zbMATH Open0689.90045OpenAlexW2057461902MaRDI QIDQ582203FDOQ582203
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
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
graphdistributed systempolynomial algorithmindependent interchangeable processorsindependent memoryoptimal job schedulingtree-like precedence constraints
Applications of mathematical programming (90C90) Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Theory of operating systems (68N25)
Cites Work
Cited In (16)
- Sensitivity bounds for machine scheduling with uncertain communication delays
- Tree scheduling with communication delays
- A fully polynomial approximation scheme for a scheduling problem with intree-type precedence delays
- Scheduling inverse trees under the communication model of the LogP-machine
- Scheduling UET-UCT outforests to minimize maximum lateness
- The Boolean quadratic programming problem with generalized upper bound constraints
- Scheduling complete intrees on two uniform processors with communication delays
- A polynomially solvable class of quadratic semi-assignment problems
- 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
- A fixed-parameter algorithm for scheduling unit dependent tasks with unit communication delays
- Bounds and algorithms for a practical task allocation model (extended abstract)
- 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
- Parallel 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)
