2 BRANCH-AND-BOUND ALGORITHMS FOR THE PERMUTATION FLOW-SHOP PROBLEM

The objective of this paper is to present two exact methods for the pe rmutation flow shop problem. The first method is based on immediate se lections and optimal adjustments of heads and tails. The second method consists in recursively enumerating jobs potentially processed first (inputs) and jobs which would be processed last (outputs) on machines. It is found that this second method gives better results than the fir st. However, the first method becomes more efficient when initial head s and tails are added.