New characteristics of optimal solutions for the two-machine flowshop problem with unlimited buffers

Abstract

The two-machine flowshop problem with unlimited buffers with the objective of minimising the makespan (F2||Cmax) is addressed. Johnson’s algorithm finds optimal solutions (permutations) to this problem, but are not necessarily the only optimal solutions. We show in this paper that certain jobs that we define as Critical Jobs, must occupy specific positions in any optimal sequence, not only in Johnson’s solutions. We also prove that jobs that precede a critical job cannot be exchanged with jobs that succeed it in an optimal sequence, which reduces the number of enumerations necessary to identify all optimal solutions. The findings of this research can be useful in reducing the search space for optimal enumeration algorithms such as branch-and-bound.