A fast branch-and-bound algorithm with an improved lower bound for solving the multiprocessor scheduling problem

This paper proposes a fast branch-and-bound algorithm for solving the multiprocessor scheduling problem. The key point of our method is the proposal of an efficient quadratic algorithm for calculating the Fernandez and Bussell´s (1973) lower bound. In the following, we discuss about the trade-off between the cost for calculating a lower bound and the size of pruned subtrees. Several experiments are conducted to evaluate the goodness of the proposed method.