Simple Approximation Algorithms for Minimizing the Total Weighted Completion Time of Precedence-Constrained Jobs
share
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.
READ FULL TEXT