ALCOMFT-TR-03-22

Luca Becchetti, Stefano Leonardi, Alberto Marchetti-Spaccamela and Kirk Pruhs
Semi-clairvoyant Scheduling
Rome. Work packages 2 and 4. September 2003.

Abstract: We continue the investigation initiated in [BMR1] of the quality of service (QoS) that is achievable by semi-clairvoyant online scheduling algorithms, which are algorithms that only require approximate knowledge of the initial processing time of each job, on a single machine. In [BMR1] it is shown that the obvious semi-clairvoyant generalization of the Shortest Processing Time is O(1)-competitive with respect to average stretch on a single machine. In [BMR1] it was left as an open question whether it was possible for a semi-clairvoyant algorithm to be O(1)-competitive with respect to average flow time on one single machine. Here we settle this open question by giving a semi-clairvoyant algorithm that is O(1)-competitive with respect to average flow time on one single machine. We also show a semi-clairvoyant algorithm on parallel machines that achieves up to contant factors the best known competitive ratio for clairvoyant on-line algorithms. In some sense one might conclude from this that the QoS achievable by semi-clairvoyant algorithms is competitive with clairvoyant algorithms.

It is known that the clairvoyant algorithm SRPT is optimal with respect to average flow time and is 2-competitive with respect to average stretch. Thus it is possible for a clairvoyant algorithm to be simultaneously competitive in both average flow time and average stretch. In contrast we show that no semi-clairvoyant algorithm can be simultaneously O(1)-competitive with respect to average stretch and O(1)-competitive with respect to average flow time. Thus in this sense one might conclude that the QoS achievable by semi-clairvoyant algorithms is not competitive with clairvoyant algorithms.

Postscript file: ALCOMFT-TR-03-22.ps.gz (157 kb).