Combinatorial Algorithms for Minimizing the Weighted Sum of Completion Times on a Single Machine?

Abstract. In this paper we study the problem of minimizing the weighted sum of completion times of jobs with release dates on a single machine. We develop two algorithms that rely on “the simplest [linear program] relaxation ” [8]. For the first algorithm we consider the online setting where we gain knowledge of a job on its release date and produce a schedule as the machine processes jobs. We develop an online dual fitting algorithm with an approximation guarantee of 3. This is the first online algorithm to use this LP as a lower bound. For the second algorithm we work in the off-line setting and develop a primal-dual algorithm with an approximation guarantee of 2.42. This algorithm provides the current best upper bound on the integrality gap of this simple LP formulation.