Scheduling To Minimize Average Completion Time:
Off-line and On-line Algorithms

(Extended Abstract)

Leslie A. Hall, David B. Shmoys, and Joel Wein

Abstract

Time-indexed linear programming formulations have recently received a great deal of attention for their practical effectiveness in solving a number of single-machine scheduling problems. We show that these formulations are also an important tool in the design of approximation algorithms with good worst-case performance guarantees. We give simple new rounding techniques to convert an optimal fractional solution into a feasible schedule for which we can prove a constant-factor performance guarantee, thereby giving the first theoretical evidence of the strength of these relaxations.

Specifically, we consider the problem of minimizing the total weighted job completion time on a single machine subject to precedence constraints, and give a polynomial-time $(4+\epsilon)$-approximation algorithm, for any $\epsilon>0$; the best previously known guarantee for this problem was superlogarithmic. With somewhat larger constants, we also show how to extend this result to the case with release date constraints, and still more generally, to the case with $m$ identical parallel machines. We give two other techniques for problems in which there are release dates, but no precedence constraints: the first is based on other new LP rounding algorithms, whereas the second is a general framework for designing on-line algorithms to minimize the total weighted completion time.

postscript manuscript