Simple Approximation Algorithms for Minimizing the Total Weighted Completion Time of Precedence-Constrained Jobs

Abstract

We consider the precedence-constrained scheduling problem to minimize the total weighted completion time. For a single machine several $2$-approximation algorithms are known, which are based on linear programming and network flows. We show that the same ratio is achieved by a simple weighted round-robin rule. Moreover, for preemptive scheduling on identical parallel machines, we give a strongly polynomial $3$-approximation, which computes processing rates by solving a sequence of parametric flow problems. This matches the best known constant performance guarantee, previously attained only by a weakly polynomial LP-based algorithm. Our algorithms are both also applicable in non-clairvoyant scheduling, where processing times are initially unknown. In this setting, our performance guarantees improve upon the best competitive ratio of $8$ known so far.