Approximability of average completion time scheduling on unrelated machines

DOI10.1007/S10107-016-1004-8MaRDI QIDQ507314zbMATH OpenOpenAlexFDO

Authors René A. Sitters

Publication date 3 February 2017

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/s10107-016-1004-8

zbMATH Keywords

approximation algorithmpreemptionschedulingtotal completion timeunrelated machines\(\mathcal{APX}\)-hardness

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35) Approximation algorithms (68W25)

Recommendations

• Approximability of Average Completion Time Scheduling on Unrelated Machines
• A PTAS for the average weighted completion time problem on unrelated machines.
• Approximation techniques for average completion time scheduling
• scientific article; zbMATH DE number 1754642
• A min-sum 3/2-approximation algorithm for scheduling unrelated parallel machines

Cites work

• scientific article; zbMATH DE number 1754639 (Why is no real title available?)
• scientific article; zbMATH DE number 871909 (Why is no real title available?)
• scientific article; zbMATH DE number 6472636 (Why is no real title available?)
• A (2+ε)-approximation algorithm for the generalized preemptive open shop problem with minsum objective
• A PTAS for minimizing the weighted sum of job completion times on parallel machines
• Approximability of Average Completion Time Scheduling on Unrelated Machines
• Approximation Bounds for a General Class of Precedence Constrained Parallel Machine Scheduling Problems
• Complexity of preemptive minsum scheduling on unrelated parallel machines
• Convex quadratic and semidefinite programming relaxations in scheduling
• Designing PTASs for MIN-SUM scheduling problems
• Maximum bounded 3-dimensional matching is MAX SNP-complete
• Non-approximability results for scheduling problems with minsum criteria
• On Preemptive Scheduling of Unrelated Parallel Processors by Linear Programming
• Open Shop Scheduling to Minimize Finish Time
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Polynomial time approximation algorithms for machine scheduling: Ten open problems
• Scheduling Unrelated Machines by Randomized Rounding
• Scheduling independent tasks to reduce mean finishing time
• Single machine scheduling with release dates
• Technical Note—Minimizing Average Flow Time with Parallel Machines

Cited in

(9)

• Experimental comparison of approximation algorithms for scheduling unrelated parallel machines
• A min-sum 3/2-approximation algorithm for scheduling unrelated parallel machines
• Preemptive and non-preemptive scheduling on two unrelated parallel machines
• Approximability of Average Completion Time Scheduling on Unrelated Machines
• Approximation results for a bicriteria job scheduling problem on a single machine without preemption
• A PTAS for the average weighted completion time problem on unrelated machines.
• The benefit of preemption with respect to the \(\ell_p\) norm
• Approximation algorithms for maximum weighted throughput on unrelated machines
• Unrelated machine scheduling of jobs with uniform Smith ratios

This page was built for publication: Approximability of average completion time scheduling on unrelated machines

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