Approximability of average completion time scheduling on unrelated machines
From MaRDI portal
Publication:507314
DOI10.1007/s10107-016-1004-8zbMath1357.90059OpenAlexW2340234317MaRDI QIDQ507314
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
schedulingapproximation algorithmunrelated machinestotal completion timepreemption\(\mathcal{APX}\)-hardness
Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35) Approximation algorithms (68W25)
Related Items
The benefit of preemption with respect to the \(\ell_p\) norm, Preemptive and non-preemptive scheduling on two unrelated parallel machines
Cites Work
- Maximum bounded 3-dimensional matching is MAX SNP-complete
- Polynomial time approximation algorithms for machine scheduling: Ten open problems
- Designing PTASs for MIN-SUM scheduling problems
- Single Machine Scheduling with Release Dates
- A PTAS for minimizing the weighted sum of job completion times on parallel machines
- Non-Approximability Results for Scheduling Problems with Minsum Criteria
- Convex quadratic and semidefinite programming relaxations in scheduling
- Approximability of Average Completion Time Scheduling on Unrelated Machines
- Open Shop Scheduling to Minimize Finish Time
- On Preemptive Scheduling of Unrelated Parallel Processors by Linear Programming
- Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
- Scheduling independent tasks to reduce mean finishing time
- Scheduling Unrelated Machines by Randomized Rounding
- A (2+ε)-approximation algorithm for the generalized preemptive open shop problem with minsum objective
- Approximation Bounds for a General Class of Precedence Constrained Parallel Machine Scheduling Problems
- Technical Note—Minimizing Average Flow Time with Parallel Machines
- Complexity of preemptive minsum scheduling on unrelated parallel machines
- Unnamed Item
- Unnamed Item
- Unnamed Item
