A note on “An optimal online algorithm for single machine scheduling to minimize total general completion time”

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 ∑Cjα, where CjCj is the completion time of job JjJj and α⩾1α⩾1 is a constant. It has been shown in the paper by Liu et al., namely, “An optimal online algorithm for single machine scheduling to minimize total general completion time” (Liu et al., 2010) [2] that the lower bound on the competitive ratio of any online algorithm is α22α. The authors also attempted to prove that the online algorithm DSPT (Delayed Shortest Processing Time) is α22α-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 two-fold. 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 α22α-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.

► We study online scheduling of jobs with release times on a single machine.
► The objective is to minimize the total general completion time.
► A counterexample to a lemma in a published article is given.
► We explain the flaw in the argument of that lemma.
► DSPT (Delayed Shortest Processing Time) is an optimal online algorithm.