Online scheduling of a single machine to minimize total weighted completion time

• 成果类型: Article
• 署名作者: Anderson, EJ; Potts, CN
• 署名单位: University of New South Wales Sydney; University of Southampton
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.1040.0092
• 发表日期: 2004
• 页码: 686-697
• 关键词: release dates

摘要

This paper considers the online scheduling of a single machine in which jobs arrive over time, and preemption is not allowed. The goal is to minimize the total weighted completion time. We show that a simple modification of the shortest weighted processing time rule has a competitive ratio of two. This result is established using a new proof technique that does not rely explicitly on a lower bound on the optimal objective function value. Because it is known that no online algorithm can have a competitive ratio of less than two, we have resolved the open issue of determining the minimum competitive ratio for this problem.