Approximability of average completion time scheduling on unrelated machines

Research output: Contribution to JournalArticleAcademicpeer-review


We show that minimizing the average job completion time on unrelated machines is APX-hard if preemption of jobs is allowed. This provides one of the last missing pieces in the complexity classification of machine scheduling with (weighted) sum of completion times objective. The proof is based on a mixed integer linear program. This means that verification of the reduction is partly done by an ILP-solver. This gives a concise proof which is easy to verify. In addition, we give a deterministic 1.698-approximation algorithm for the weighted version of the problem. The improvement is made by modifying and combining known algorithms and by the use of new lower bounds. These results improve on the known NP-hardness and 2-approximability.

Original languageEnglish
Pages (from-to)135-158
Number of pages24
JournalMathematical Programming
Issue number1
Publication statusPublished - 2017


Dive into the research topics of 'Approximability of average completion time scheduling on unrelated machines'. Together they form a unique fingerprint.

Cite this