A branch and bound approach to two-stage hybrid flow shop scheduling problem with diverging jobs and time overlapping production

We consider a two-stage hybrid flow shop scheduling problem minimizing makespan. The problem has some features, namely, i) a job on upper stage can be split up into some sub-jobs on the lower stage, and ii) time overlapping production is permitted, which theoretical scheduling models have never contained. We regard it as a combinatorial optimization problem and propose methods of obtaining lower bound of makespan and an algorithm based on a branch and bound method. We also discuss efficiency of the algorithm by computational experiments. Motivation of this research is a real scheduling problem in the process industry.