Abstract
A branch-and-bound algorithm for a two-machine scheduling problem by Grabowski is generalized to the case of an arbitrary number of machines. The lower bounds are obtained by the relaxation of the capacity constraints on the machines. An approach to strengthen these lower bounds is developed. Computational experience with 6-, 10-, 15-, 20-, 30-, 40-, 50-job problems is presented.