A min-sum 3/2-approximation algorithm for scheduling unrelated parallel machines

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

Fabián A. Chudak

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

zbMATH Keywords

schedulingcombinatorial optimizationapproximation algorithms

Mathematics Subject Classification ID

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