Bicriteria approximation algorithms for scheduling problems with communications delays

DOI10.1007/S10951-005-1637-6MaRDI QIDQ880503zbMATH OpenOpenAlexFDO

Authors Evripidis Bampis, Alexander Kononov

Publication date 15 May 2007

Published in Journal of Scheduling (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10951-005-1637-6

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Multi-objective and goal programming (90C29)

Recommendations

• scientific article; zbMATH DE number 1500535
• Scheduling jobs with communication delays: using infeasible solutions for approximation
• Complexity and approximation for precedence constrained scheduling problems with large communication delays
• An approximation algorithm for scheduling dependent tasks on m processors with small communication delays
• Approximation algorithms for UET scheduling problems with exact delays

Cites work

• A Heuristic for a Scheduling Problem with Communication Delays
• An approximation algorithm for scheduling dependent tasks on m processors with small communication delays
• scientific article; zbMATH DE number 1302193 (Why is no real title available?)
• scientific article; zbMATH DE number 1305482 (Why is no real title available?)
• scientific article; zbMATH DE number 1830735 (Why is no real title available?)
• scientific article; zbMATH DE number 1875417 (Why is no real title available?)
• scientific article; zbMATH DE number 2119733 (Why is no real title available?)
• scientific article; zbMATH DE number 816196 (Why is no real title available?)
• On the existence of schedules that are near-optimal for both makespan and total weighted completion time
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Scheduling jobs with communication delays: using infeasible solutions for approximation
• Three, four, five, six, or the complexity of scheduling with communication delays

Cited in

(16)

• A new approximation algorithm for UET-scheduling with chain-type precedence constraints.
• Approximation algorithms for scheduling with a limited number of communications
• Approximation algorithms for bicriteria scheduling problems on identical parallel machines for makespan and total completion time
• A new approach for bicriteria partitioning problem
• Approximation algorithms for UET scheduling problems with exact delays
• Approximation algorithms for the bi-criteria weighted MAX-CUT problem
• On the hardness of approximating the UET-UCT scheduling problem with hierarchical communications
• scientific article; zbMATH DE number 1500535 (Why is no real title available?)
• Scheduling jobs with communication delays: using infeasible solutions for approximation
• Scheduling \(UET\)-tasks on a star network: complexity and approximation
• An approximation algorithm for scheduling dependent tasks on m processors with small communication delays
• Approximation algorithms for coupled task scheduling minimizing the sum of completion times
• Inapproximability and polynomial-time approximation algorithm for UET tasks on structured processor networks
• Minimizing total completion time and makespan for a multi-scenario bi-criteria parallel machine scheduling problem
• Approximating multi-scenario efficient solutions for an uncertain bi-criteria parallel machine scheduling problem
• Complexity and approximation for precedence constrained scheduling problems with large communication delays

This page was built for publication: Bicriteria approximation algorithms for scheduling problems with communications delays

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