A “Branch-and-Bound” Algorithm for the Exact Solution of the Three-Machine Scheduling Problem

By combining Roy's graph-theoretical interpretation of the problem of job scheduling on machines and some general results of his theory with the “branch-and-bound” method recently applied by Little et al. to the travelling salesman problem an algorithm has been obtained for the exact solution of the scheduling problem in the case of three machines. The working of the algorithm has been illustrated by numerical examples and possibilities of further investigations have been indicated.