A note on %26quot;An optimal online algorithm for single machine scheduling to minimize total general completion time%26quot;

作者：Yu Sheng^*; Wong Prudence W H

来源：Information Processing Letters, 2012, 112(1-2): 55-58.

DOI：10.1016/j.ipl.2011.09.014

• Online algorithms
• Scheduling
• Total general completion time
• Delayed shortest processing time
• Competitive analysis

In this paper we study the problem of online scheduling of jobs with release times on a single machine to minimize the total general completion time Sigma C(j)(alpha), where C(j) is the completion time of job J(j) and alpha %26gt;= 1 is a constant, It has been shown in the paper by Liu et al., namely, %26quot;An optimal online algorithm for single machine scheduling to minimize total general completion time%26quot; (Liu et at, 2010) [2] that the lower bound on the competitive ratio of any online algorithm is 2(alpha). The authors also attempted to prove that the online algorithm DSPT (Delayed Shortest Processing Time) is 2(alpha)-competitive. Unfortunately, Lemma 2 in the paper, which is crucial in the proof, is indeed incorrect. This leaves the performance of DSPT as an open question. The contribution of this paper is twofold. First, we give a counterexample to this lemma and an explanation of the flaw in the argument.. Second, we give a proof that DSPT is 2(alpha)-competitive. Together with the lower bound by Liu et al., this implies that DSPT is an optimal online algorithm for minimizing the total general completion time.

• 出版日期2012-1-15
• 单位西安交通大学