A Heuristic for a Scheduling Problem with Communication Delays

DOI10.1287/opre.45.1.145zbMath0892.90104OpenAlexW1985059007MaRDI QIDQ4367272

Alix Munier, Jean-Claude Konig

Publication date: 25 November 1997

Published in: Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/opre.45.1.145

zbMATH Keywords

makespaninterprocessor communication delayslist scheduling heuristicworst-case relative performance

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Related Items (13)

Scheduling in the presence of processor networks : complexity and approximation ⋮ Three, four, five, six, or the complexity of scheduling with communication delays ⋮ General scheduling non-approximability results in presence of hierarchical communications ⋮ Unnamed Item ⋮ Bicriteria approximation algorithms for scheduling problems with communications delays ⋮ An approximation algorithm for the precedence constrained scheduling problem with hierarchical communications. ⋮ Approximation algorithms for precedence-constrained identical machine scheduling with rejection ⋮ Complexity and approximation for precedence constrained scheduling problems with large communication delays ⋮ Inapproximability and polynomial-time approximation algorithm for UET tasks on structured processor networks ⋮ An approximation algorithm for scheduling dependent tasks on \(m\) processors with small communication delays ⋮ Scheduling \(UET\)-tasks on a star network: complexity and approximation ⋮ Polynomial time approximation algorithms for machine scheduling: Ten open problems ⋮ An approximation algorithm for the precedence constrained scheduling problem with hierarchical communications

This page was built for publication: A Heuristic for a Scheduling Problem with Communication Delays