SPT is optimally competitive for uniprocessor flow
We show that the Shortest Processing Time (SPT) algorithm is (Delta + 1)/2-competitive for nonpreemptive uniprocessor total flow time with release dates, where Delta is the ratio between the longest and shortest job lengths. This is best possible for a deterministic algorithm and improves on the (Delta + 1)-competitive ratio shown by Epstein and van Stee using different methods. (C) 2004 Elsevier B.V. All rights reserved.
algorithms on-line algorithms scheduling