Approximability of average completion time scheduling on unrelated machines

DOI10.1007/S10107-016-1004-8zbMATH Open1357.90059OpenAlexW2340234317MaRDI QIDQ507314FDOQ507314

Authors: René A. Sitters 

Publication date: 3 February 2017

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

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

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

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)

Cites Work

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