Scheduling to minimize total weighted completion time via Time-indexed linear programming relaxations

We study approximation algorithms for problems of scheduling precedence constrained jobs with the objective of minimizing total weighted completion time, in identical and related machine models. We give algorithms that improve upon many previous 15- to 20-year-old state-of-the-art results. A major theme in these results is the use of time-indexed linear programming relaxations, which are quite natural for their respective problems. We also consider the scheduling problem of minimizing total weighted completion time on unrelated machines. The recent breakthrough result of [N. Bansal, A. Srinivasan, and O. Svensson, in Proceedings of the 48th Annual ACM Symposium on Theory of Computing, ACM, 2016, pp. 156-167] gave a (1.5-c)-approximation for the problem, based on a two-round lift-and-project of the SDP relaxation for the problem. Our main result is that a (1.5-c)-approximation can also be achieved using a natural and considerably simpler time-indexed linear programming relaxation for the problem. We hope this relaxation can provide new insights into the problem.