SCHEDULING IDENTICAL PARALLEL MACHINES TO MINIMIZE TOTAL WEIGHTED COMPLETION-TIME

A 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 interval's, 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.