MINIMIZING MAKESPAN IN HYBRID FLOWSHOPS

We 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. We refer to this design as the hybrid flowshop. Our objective is to schedule a set of n jobs so as to minimize makespan. The problem is N P-complete even in the case of a single stage. We developed a heuristic H for the 2-stage hybrid flowshop that has complexity O (n log n) (where n is the number of jobs) and an error bound of 2 - 1/max{m1, m2} (where m(i) 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. We develop five new lower bounds which are used in a computational experiment to show that the relative gap of H from optimality is small. We extend H to the case of more than two stages. We perform error bound analysis on the resulting heuristic H' whose complexity is O (kn log n) (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.