An adaptive branch and bound approach for transforming job shops into flow shops

In this paper we address the problem of transforming a job shop layout into a flow shop with the objective of minimizing the length of the resulting flow-line. First, we present five properties of the problem under consideration that are employed for constructing a branch and bound algorithm. The approach is named adaptive since the development of the children nodes depends on the particular instance in order to try tightening the lower bounds and hence performing faster. The computational experiments carried out show the approach to be effective for a variety of problem sizes.