Online Scheduling of a Single Machine to Minimize Total Weighted Completion Time
研究了不允许抢占的单机在线调度问题，目标是最小化总加权完工时间。通过改进最短加权处理时间规则，证明竞争比为2，并解决了最小竞争比的开放问题。
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.