DUAL DECOMPOSITION OF A SINGLE-MACHINE SCHEDULING PROBLEM

We design a fast ascent direction algorithm for the Lagrangian dual pr oblem of the single-machine scheduling problem of minimizing total wei ghted completion time subject to precedence constraints. We show that designing such an algorithm is relatively simple if a scheduling probl em is formulated in terms of the job completion times rather than as a n 0-1 linear program. Also, we show that upon termination of such an a scent direction algorithm we get a dual decomposition of the original problem, which can be exploited to develop approximative and enumerati ve approaches for it. Computational results exhibit that in our applic ation the ascent direction leads to good Lagrangian lower and upper bo unds.