H. Belouadah et Cn. Potts, SCHEDULING IDENTICAL PARALLEL MACHINES TO MINIMIZE TOTAL WEIGHTED COMPLETION-TIME, Discrete applied mathematics, 48(3), 1994, pp. 201-218
A branch and bound algorithm is proposed for the problem of scheduling
jobs on identical parallel machines to minimize the total weighted co
mpletion time. Based upon a formulation which partitions the period of
processing into unit time interval's, the lower bounding scheme is de
rived by performing a Lagrangean relaxation of the machine capacity co
nstraints. 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 r
ule, is incorporated into a branch and bound algorithm. Computational
experience indicates that it is superior to known algorithms.