Linear programming & metaheuristic approach for scheduling in the hybrid flowshop with resource constraints

This paper deals with the problem of preemptive scheduling in a two-stage flowshop with parallel unrelated machines and additional renewable resources. The objective is the minimization of makespan. The problem is NP-hard. Heuristic algorithms are proposed which join the linear programming based procedures with metaheuristic algorithms: genetic, simulated annealing and tabu search algorithm. The performance of the proposed algorithms is experimentally evaluated by comparing the solutions with a lower bound on the optimal makespan. Results of a computational experiment show that these algorithms are able to produce good solutions in short computation time and that the metaheuristics significantly improve the results for the most difficult problems.