The authors consider flowshop environments that consist of multiple stages and multiple machines in each stage. The flowshops are flexible in the sense that a task within a stage can be processed by any of the machines in the stage. The authors refer to this design as the hybrid flowshop. The objective is to schedule a set of n jobs so as to minimize makespan. The problem is 𝒩𝒫-complete even in the case of a single stage. The authors develop a heuristic H for the 2-stage hybrid flowshop that has complexity 𝒪(nlogn) (where n is the number of jobs) and an error bound of 2-1/max{m1,m2} (where mi is the number of machines at stage i,i=1,2). This bound extends a recent bound for the case m1=1, m2=m and significantly improves all other results that have been developed for some special cases of the 2-stage hybrid flowshop. The authors develop five new lower bounds which are used in a computational experiment to show that the relative gap of H from optimality is small. They extend H to the case of more than two stages. The authors perform error bound analysis on the resulting heuristic H' whose complexity is 𝒪(knlogn) (where k is the number of stages). This is the first error bound analysis for the general hybrid flowshop problem and extends the current best error bound for the traditional k-machine flowshop problem.
