A PTAS for minimizing the total weighted completion time on identical parallel machines

• 成果类型: Article
• 署名作者: Skutella, M; Woeginger, GJ
• 署名单位: Technical University of Berlin; Graz University of Technology
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.25.1.63.15212
• 发表日期: 2000
• 页码: 63-75
• 关键词: algorithms

摘要

We consider the problem of scheduling a set of n jobs on m identical parallel machines so as to minimize the weighted sum of job completion limes. This problem is NP-hard in the strong sense. The best approximation result known so far was a 1/2 (1 + root 2)-approximation algorithm that has been derived by Kawaguchi and Kyan back in 1986. The contribution of this paper is a polynomial time approximation scheme for this setting, which settles a problem that was open for a long time. Moreover, our result constitutes the first known approximation scheme for a strongly NP-hard scheduling problem with minsum objective.