A PTAS for minimizing the weighted sum of job completion times on parallel machines

DOI10.1145/301250.301356zbMath1345.90045OpenAlexW1969481001MaRDI QIDQ2819573

Gerhard J. Woeginger

Publication date: 29 September 2016

Published in: Proceedings of the thirty-first annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/301250.301356

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Approximation methods and heuristics in mathematical programming (90C59) Approximation algorithms (68W25)

Related Items (10)

Minimizing the total weighted completion time of fully parallel jobs with integer parallel units ⋮ Scheduling to Minimize Total Weighted Completion Time via Time-Indexed Linear Programming Relaxations ⋮ Scheduling Fully Parallel Jobs with Integer Parallel Units ⋮ Approximability of average completion time scheduling on unrelated machines ⋮ Designing PTASs for MIN-SUM scheduling problems ⋮ Polynomial time approximation algorithms for machine scheduling: Ten open problems ⋮ Scheduling fully parallel jobs ⋮ Lift-and-Round to Improve Weighted Completion Time on Unrelated Machines ⋮ A min-sum 3/2-approximation algorithm for scheduling unrelated parallel machines ⋮ A PTAS for the average weighted completion time problem on unrelated machines.

This page was built for publication: A PTAS for minimizing the weighted sum of job completion times on parallel machines