We present a new linear programming relaxation for the problem of minimizing the sum of weighted completion times of precedence-constrained jobs. Given a set of n jobs, each job j has processing time pj and weight wj. There is also a partial order ≺ on the execution of the jobs: if j≺k, job k may not start processing before job j has been completed. For Cj representing the completion time of job j, the objective is to minimize the weighted sum of completion times, ∑jwjCj. The new relaxation is simple and compact, has exactly two variables per inequality and half-integral extreme points. An optimal solution can be found via a minimum cut computation, which provides a new 2-approximation algorithm in the complexity of a minimum cut on a graph. As a by-product, we also introduce another new 2-approximation algorithm for the problem.
