A Lagrangean Based Branch and Bound Algorithm for Single Machine Sequencing with Precedence Constraints to Minimize Total Weighted Completion Time

The single machine sequencing problem is considered in which there are precedence constraints on the jobs. The objective is to minimize the sum of weighted completion times. A lower bound is obtained by successively performing a Lagrangean relaxation of appropriate constraints. Each Lagrange multiplier is chosen to provide the maximum increment to the lower bound subject to retaining the nonnegativity of the coefficients of the variables. When no further suitable constraints can be introduced into the Lagrangean function, the variables having zero cost coefficient are used to obtain a feasible sequence which provides an upper bound. The gap between the lower and upper bound is reduced by removing some constraints from the Lagrangean function and replacing them with others. This lower bounding procedure is used in a branch and bound algorithm. Computational results indicate that the algorithm can satisfactorily solve problems with up to 100 jobs.