Scheduling identical parallel machines to minimize total weighted completion time

AbstractA branch and bound algorithm is proposed for the problem of scheduling jobs on identical parallel machines to minimize the total weighted completion time. Based upon a formulation which partitions the period of processing into unit time intervals, the lower bounding scheme is derived by performing a Lagrangean relaxation of the machine capacity constraints. A special feature is that the multipliers are obtained by a simple heuristic method which allows each lower bound to be computed in polynomial time. This bounding scheme, along with a new dominance rule, is incorporated into a branch and bound algorithm. Computational experience indicates that it is superior to known algorithms