Minimizing average completion time in the presence of release dates

A natural and basic problem in scheduling theory is to provide good average quality of service to a stream of jobs that arrive over time. In this paper we consider the problem of schedulingn jobs that are released over time in order to minimize the average completion time of the set of jobs. In contrast to the problem of minimizing average completion time when all jobs are available at time 0, all the problems that we consider are NP-hard, and essentially nothing was known about constructing good approximations in polynomial time. We give the first constant-factor approximation algorithms for several variants of the single and parallel machine models. Many of the algorithms are based on interesting algorithmic and structural relationships between preemptive and nonpreemptive schedules and linear programming relaxations of both. Many of the algorithms generalize to the minimization of averageweighted completion time as well. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.This work was performed under US Department of Energy contract number DE-AC04-76AL85000.Research partly supported by NSF Award CCR-9308701, a Walter Burke Research Initiation Award and a Dartmouth College Research Initiation Award.Research partially supported by NSF Research Initiation Award CCR-9211494 and a grant from the New York State Science and Technology Foundation, through its Center for Advanced Technology in Telecommunications.