Comments on 'Competitive analysis of a better on-line algorithm to minimize total completion time on a single-machine'

摘要

For the single machine scheduling problem of minimizing the total completion time, Montoya Torres (J Glob Opt 27:97-103,2003) presented a semi-online algorithm under the assumption that release dates are known in advance, and showed that it was -3~(1/2)-compet-itive. However, there are flaws in the proof, and the conclusion about the competitive ratio is not correct. In this note, we show that the semi-online algorithm cannot perform better than the best non-clairvoyant online algorithm with a competitive ratio of 2.