Effective upper and lower bounds for a two-stage reentrant flexible flow shop scheduling problem

Flow shop scheduling is important in modern industrial manufacturing to improve production efficiency. This paper studies a realistic two-stage reentrant flexible flow shop scheduling problem (TSRFFS) with broad applications in aircraft scheduling, manufacturing, and the medical industry, etc. Given a flow shop with a single machine in Stage 1, a set of parallel machines in Stage 2, and a set of jobs to be processed, the TSRFFS aims to determine the completion time of jobs in Stage 1 and then that in Stage 2, and finally returns to Stage 1, as well as determine the job-to-machine assignment in Stage 2 such that all jobs are served and the total processing time of jobs (makespan) is minimized. The optimal solution properties are investigated, based on which a mixed integer programming mathematical model and a greedy random constructive heuristic for near optimal solutions are proposed. By solving series of a revised parallel machine scheduling problem (Pm||Cmax), a lower bound method is developed. Extensive numerical experiments on 1560 random instances with up to 1000 jobs and 50 realistic airport simulation instances were conducted to demonstrate the effectiveness of the proposed algorithms. The average gap between the proposed upper bound and the best lower bounds is approximately 1.78%, and the average gap between the proposed lower bound and the best upper bounds is 0.91%, which far outperforms state-of-the-art approaches in terms of solution quality and computational time.