Scheduling identical parallel machines to minimize total weighted completion time (Q1317043)

A branch-and-bound algorithm is proposed for the problem of scheduling \(n\) jobs with known integer processing times and weights on \(m\) identical parallel machines with the objective to minimize total weighted completion time. The algorithm is based on a new lower bound which is derived by Lagrangean relaxation of the machine capacity constraints. Instead of determining the optimal parameter for the Lagrangean problem that gives the best lower bound a heuristic method is used. This allows to compute the lower bound efficiently. It is shown that the heuristic yields a lower bound that is exact when there is a single machine or when all jobs have unit processing times. To eliminates nodes from the search tree the authors present a new dominance rule. They give computational results which compare their branch-and-bound algorithm to previous ones and indicate the value of the new dominance rule.