Three, four, five, six, or the complexity of scheduling with communication delays

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

zbMATH Keywords

makespanprecedence constraintscommunication delaysidentical parallel processors

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Deterministic scheduling theory in operations research (90B35) Parallel numerical computation (65Y05)

Related Items (22)

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 ⋮ A Fixed-Parameter Algorithm for Scheduling Unit Dependent Tasks with Unit Communication Delays ⋮ Scheduling interval ordered tasks with non-uniform deadlines ⋮ 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

This page was built for publication: Three, four, five, six, or the complexity of scheduling with communication delays