A min-sum 3/2-approximation algorithm for scheduling unrelated parallel machines
From MaRDI portal
Publication:1592284
DOI<73::AID-JOS18>3.0.CO;2-Q 10.1002/(SICI)1099-1425(199903/04)2:2<73::AID-JOS18>3.0.CO;2-QzbMath0963.90028OpenAlexW2015033265MaRDI QIDQ1592284
Publication date: 15 January 2001
Published in: Journal of Scheduling (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/(sici)1099-1425(199903/04)2:2<73::aid-jos18>3.0.co;2-q
Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)
Related Items
Unrelated Machine Scheduling with Stochastic Processing Times ⋮ A survey on offline scheduling with rejection ⋮ Heuristics for minimizing regular performance measures in unrelated parallel machine scheduling problems ⋮ On the relationship between combinatorial and LP-based lower bounds for NP-hard scheduling problems ⋮ Polynomial time approximation algorithms for machine scheduling: Ten open problems ⋮ Lift-and-Round to Improve Weighted Completion Time on Unrelated Machines ⋮ A PTAS for the average weighted completion time problem on unrelated machines.
Cites Work
- A PTAS for minimizing the weighted sum of job completion times on parallel machines
- Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
- Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms
- Scheduling independent tasks to reduce mean finishing time
- Technical Note—Minimizing Average Flow Time with Parallel Machines
