Linear programming relaxation for scheduling problems

In this article we study linear programming relaxation for scheduling problems, and propose a 2-approximation algorithm based on relaxation of 3 linear programs for the single machine scheduling problem 1 | prec | ∑wjCj and a 2-approximation algorithm based on random relaxation of a linear program for the parallel machine scheduling problem R | rij | ∑wjCj. The later is a 3/2-approximation algorithm for the problem R ‖ ∑wjCj.