Two branch and bound algorithms for the permutation flow shop problem

The objective of this paper is to present two exact methods for the permutation flow shop problem. The first method is based on immediate selections 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 first. However, the first method becomes more efficient when initial heads and tails are added.