Approximability of average completion time scheduling on unrelated machines

• 成果类型: Article
• 署名作者: Sitters, Rene
• 署名单位: Vrije Universiteit Amsterdam; Centrum Wiskunde & Informatica (CWI)
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-016-1004-8
• 发表日期: 2017
• 页码: 135-158
• 关键词: parallel machines

摘要

We show that minimizing the average job completion time on unrelated machines is -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 -hardness and 2-approximability.