Two stage reentrant hybrid flow shop with setup times and the criterion of minimizing makespan

This paper discusses a two stage reentrant hybrid flowshop scheduling problem. The problem to be studied has two main stages: In stage one, there are g stations and in station k, there are m1k identical parallel machines and in stage two, there is a station with m2 identical parallel machines. The first stage is a reentrant shop which all jobs have the same routing over the machines of the shop and the same sequence is traversed several times to complete different levels of the jobs. Such scheduling problems occur in certain practical applications such as semiconductors, electronics manufacturing, airplane engine production, and petrochemical production. The criterion is to minimize the makespan of the system. Setup times are implemented between jobs in both stages and between levels in stage one. There has not been any study about this real area which has two separated stages with different setup times in each one. Because of the intractability of the reentrant hybrid flow shop model, some heuristic algorithms and a random key genetic algorithm (RKGA) are proposed and compared with a new hybrid genetic algorithm (HGA). Computational experiments are performed to illustrate that the proposed HGA provides the best solutions in comparison with other algorithms.