Heuristic algorithms for two machine re-entrant flow shop

This paper focuses on a two machine re-entrant flow shop scheduling problem with the objective of minimizing makespan. In the re-entrant flow shop considered here, each job has the processing route (M₁, M₂, M₁, M₂, …, M₁, M₂). We present heuristic algorithms, some are modified from existing algorithms and some are newly developed. Extensive computational experiments are performed to evaluate the performance of the heuristics. Results of the experiments show that the performance of heuristics is significantly affected by the distribution of workloads on machines and some of them are excellent.