A two-stage Hybrid Flowshop Problem (FSm1, m2) is a two-center shop with several parallel machines per center and n jobs to be processed on at most one machine per center. The objective consists of minimizing the maximum completion time. Two two-phase methods based on Simulated Annealing and Tabu Search are proposed. The results are compared with solutions provided by existing heuristics, and with a new derived lower bound. These comparisons show the superiority of the derived lower bound and the efficiency of the proposed heuristic. The Tabu search based heuristic yields the optimal solution for 35% of the problems. Its average relative error is 0.82%.
