Scheduling a Two Stage Proportionate Flexible Flow Shop with Dedicated Machines and No Buffers

In this paper, we study a scheduling problem derived from an application in the chemical processing industry. At the chemical plant we consider, a single base reactor prepares different starting products for several distinct production lines, each consisting of a number of further, specialized reactors. Importantly, there are no buffers, so after completion a job may block a reactor from processing further jobs, if no successor reactor is ready to start it. First, we show how to model the scheduling problem as a special version of the well-known flexible flow shop problem. Then we prove that in the general version of the problem it is strongly NP-hard to minimize the makespan. Towards a solution, we propose and compare several different construction heuristics.