Two-machine flow shop problems with a single server

Scheduling models that allow the handling of pre-operational setup have been a source of major interests because of their practical relevance and theoretical impacts. Two-stage flow-lines have drawn much attention to researchers as they are simple, yet practical and can be easily extended to represent more complex situations. In this paper, two-machine flow-shop problems with a single setup server are surveyed. These problems have been shown to be NP-complete with special cases that are polynomial-time solvable. Several heuristics are proposed to solve the problems in general case, including simulated annealing, Tabu search, genetic algorithms, GRASP, and other hybrids. The results on small inputs are compared with the optimal solutions and results on large inputs are compared to a lower bound. Experiments show that the heuristics developed, obtain nearly optimal solutions.