Asymptotic analysis of an on-line algorithm for the single machine completion time problem with release dates

In the single machine mean completion time problem with release dates, a set of jobs has to be processed non-preemptively on a single machine. No job can be processed before its release date, and the objective is to determine a sequence of the jobs on the machine which minimizes the sum of the completion times of all jobs. In this paper, we prove the asymptotic optimality of the shortest processing time among available job algorithms, in which at the completion time of any job, the next job to be scheduled is the shortest job among all those released but not yet processed. This algorithm is particularly attractive because it falls in the class of easy to implement and computationally inexpensive on-line algorithms.