Dual decomposition of a single-machine scheduling problem

The paper designs a fast ascent direction algorithm for the Lagrangian dual problem of the single-machine scheduling problem of minimizing total weighted completion time subject to precedence constraints. It shows that designing such an algorithm is relatively simple if a scheduling problem is formulated in terms of the job completion times rather than as an 0-1 linear program. Also, the paper shows that upon termination of such an ascent direction algorithm it gets a dual decomposition of the original problem, which can be exploited to develop approximative and enumerative approaches for it. Computational results exhibit that in the present application the ascent direction leads to good Lagrangian lower and upper bounds.