Scheduling the fabrication and assembly of components in a two-machine flowshop

Abstract

In this paper we study the problem of scheduling the fabrication and assembly of components in a two-machine flowshop so as to minimize the makespan. Each job consists of a component unique to that job and a component common to all jobs. Both the unique and the common components are processed on the first machine. While the unique components are processed individually, the common components are processed in batches and a setup is needed to form each batch. The assembly operations of a job is performed on the second machine, and can only begin when both components for the job are available. We first show that the problem is NP-complete with either batch availability or item availability for the common components. We identify several properties of an optimal solution to the problem, and some polynomially solvable special cases.