Three, four, five, six, or the complexity of scheduling with communication delays
From MaRDI portal
Publication:1342284
DOI10.1016/0167-6377(94)90024-8zbMath0816.90083OpenAlexW2169878774MaRDI QIDQ1342284
Jan Karel Lenstra, Hoogeveen, J. A., Bart Veltman
Publication date: 13 February 1995
Published in: Operations Research Letters (Search for Journal in Brave)
Full work available at URL: https://ir.cwi.nl/pub/5391
Abstract computational complexity for mathematical programming problems (90C60) Deterministic scheduling theory in operations research (90B35) Parallel numerical computation (65Y05)
Related Items
Scheduling in the presence of processor networks : complexity and approximation, General scheduling non-approximability results in presence of hierarchical communications, Unnamed Item, Bicriteria approximation algorithms for scheduling problems with communications delays, Preemptive scheduling of independent jobs on identical parallel machines subject to migration delays, An approximation algorithm for the precedence constrained scheduling problem with hierarchical communications., Approximation algorithms for precedence-constrained identical machine scheduling with rejection, A complete 4-parametric complexity classification of short shop scheduling problems, Complexity and approximation for precedence constrained scheduling problems with large communication delays, An EPTAS for scheduling fork-join graphs with communication delay, An approximation algorithm for scheduling dependent tasks on \(m\) processors with small communication delays, Scheduling \(UET\)-tasks on a star network: complexity and approximation, Scheduling UET-UCT outforests to minimize maximum lateness, Polynomial time approximation algorithms for machine scheduling: Ten open problems, Complete Complexity Classification of Short Shop Scheduling, On the complexity of scheduling with large communication delays, Scheduling inverse trees under the communication model of the LogP-machine, An approximation algorithm for the precedence constrained scheduling problem with hierarchical communications, A very difficult scheduling problem with communication delays, On the hardness of approximating the UET-UCT scheduling problem with hierarchical communications
Cites Work
- Unnamed Item
- Multiprocessor scheduling with communication delays
- UET scheduling with unit interprocessor communication delays
- Towards an Architecture-Independent Analysis of Parallel Algorithms
- C.P.M. Scheduling with Small Communication Delays and Task Duplication
- Complexity of Scheduling under Precedence Constraints
- Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
- A Heuristic for a Scheduling Problem with Communication Delays
- The Complexity of Scheduling Trees with Communication Delays
