Solving Re-entrant No-wait Flexible Flowshop Scheduling Problem; Using the Bottleneck-based Heuristic and Genetic Algorithm

Document Type: Research Paper


1 School of Engineering, Urmia University, Oroumieh, West Azerbaijan Province, Oroumieh, Iran

2 Faculty of Industrial and Mechanical Engineering, Qazvin Branch, Islamic Azad University, Qazvin, Iran

3 Technical and Vocational University, Tehran, Tehran Province, Iran


In this paper, we study the re-entrant no-wait flexible flowshop scheduling problem with makespan minimization objective and then consider two parallel machines for each stage. The main characteristic of a re-entrant environment is that at least one job is likely to visit certain stages more than once during the process. The no-wait property describes a situation in which every job has its own processing sequence with the constraint that no waiting time is allowed among operations within any jobs. This study develops a bottleneck-based heuristic (BBFFL) to solve a flexible flowshop problem including a bottleneck stage. Also, a genetic algorithm (GA) based on heuristics for the problem is presented. First, the mathematical model for the problem is proposed, and then the suggested algorithms are explained. For small-scale, the results of the BBFFL and GA are compared to the results derived from the GAMS. For large-scale problems, the results of the GA and BBFFL are compared with each other. For small-scale problems, the algorithms have a close performance but the BBFFL is likely to generate much better in finding solutions in large-scale problems.