The authors consider the scheduling of two-stage flexible flowshops. This manufacturing environment involves two machine centres representing two consecutive stages of production. Each machine centre is composed of multiple parallel machines. Each job has to be processed serially through the two machine centres. In each machine centre, a job may be processed on any of the machines. There are n independent jobs to be scheduled without preemption. The jobs can wait in between the two machine centres and the intermediate storage is unlimited. The present objective will be to minimize the maximum completion time of the jobs. The authors formulate the problem as a mixed integer program. Given this probelm class is NP-hard in the strong sense, they present three lower bounds to estimate the optimal solution. The authors then propose a sequence-first, allocate-second heuristic approach for its solution. They heuristically decompose the problem by first creating a priority list to order the jobs and then assign the jobs to the available machines in each machine centre based on this order. The authors describe seven rules for the sequencing phase. The assignment phase consists of a heuristic which attempts to minimize each partial schedule length while looking ahead at the future assignment of the currently unscheduled jobs. The computational performance of the heuristic approach was evaluated by comparing the value of each heuristic variant to the best among the three lower bounds. Its effectiveness was tested on scenarios pertinent to flexible flowshop environments, such as cellular manufacturing, by conducting a computational study of over 3400 problems. The present computational results indicate that the most effective approach used Johnson’s rule to provide the priority list for job assignment. This provided integrality gaps which on the average were less than 0.73%.
