Scheduling multi-stage flowshop problems: A brief review

The multi-stage flowshop problem, whether regular (meaning a single machine per stage) or hybrid (meaning more than one machine in at least one stage) has attracted many researchers. Scheduling in such environment with two or more stages tends to be NP-hard in general, with very few notable exceptions, even when the machines at each stage are identical and there are no more than two machines in any stage. To tackle these NP-hard problems efficiently, one seeks heuristic approaches, preferably with small worst case performance bounds. In the absence of such bounds, one seeks empirical evidence on the performance of the proposed heuristics, based on well-designed Monte Carlo sampling experiments. Hybrid flowshops typically result from the adjunction of parallel machines to at least one stage to increase the production capacity or to solve a bottleneck problem. In this paper, recent research in deterministic flowshop and hybrid flowshop scheduling will be reviewed from the point of view of complexity, exact and approximate algorithms, worst case analysis and heuristics design.