Approximate algorithms for unrelated machine scheduling to minimize makespan

DOI10.3934/JIMO.2016.12.771MaRDI QIDQ747046zbMATH OpenOpenAlexFDO

Authors Xianzhao Zhang, Cuixia Miao, Dachuan Xu, Donglei Du

Publication date 22 October 2015

Published in Journal of Industrial and Management Optimization (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.3934/jimo.2016.12.771

zbMATH Keywords

linear programmingapproximation algorithmschedulingroundingunrelated parallel machine

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Recommendations

• An absolute approximation algorithm for scheduling unrelated machines
• Approximation algorithms for scheduling unrelated parallel machines
• Exact and approximation algorithms for makespan minimization on unrelated parallel machines
• Approximation schemes for scheduling and covering on unrelated machines
• scientific article; zbMATH DE number 1187166
• Improved approximation schemes for scheduling unrelated parallel machines
• Approximating scheduling unrelated parallel machines in parallel
• An efficient approximation algorithm for minimizing makespan on uniformly related machines.
• Improved Approximation Schemes for Scheduling Unrelated Parallel Machines

Cites work

• scientific article; zbMATH DE number 1330032 (Why is no real title available?)
• An approximation algorithm for the generalized assignment problem
• An optimal rounding gives a better approximation for scheduling unrelated machines
• Approximation Algorithms for Unrelated Machine Scheduling with an Energy Budget
• Approximation algorithms for scheduling unrelated parallel machines
• Graph balancing: a special case of scheduling unrelated parallel machines
• Machine scheduling with resource dependent processing times
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Parallel-machine scheduling problem under the job rejection constraint (extended abstract)
• Strong LP Formulations for Scheduling Splittable Jobs on Unrelated Machines
• The design of approximation algorithms

Cited in

(9)

• Approximation results for makespan minimization with budgeted uncertainty
• A new approximation algorithm for unrelated parallel machine scheduling with release dates
• Algorithms for single-machine scheduling problem with deterioration depending on a novel model
• An efficient approximation algorithm for minimizing makespan on uniformly related machines.
• scientific article; zbMATH DE number 437570 (Why is no real title available?)
• An optimal rounding gives a better approximation for scheduling unrelated machines
• 2-approximation algorithm for a generalization of scheduling on unrelated parallel machines
• Makespan minimization for scheduling unrelated parallel machines: a recovering beam search approach
• Approximation Algorithms for Unrelated Machine Scheduling with an Energy Budget

This page was built for publication: Approximate algorithms for unrelated machine scheduling to minimize makespan

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