An Efficient Two-Stage Genetic Algorithm for Flexible Job-Shop Scheduling

Flexible job shop Scheduling Problem (FJSP) is considered as an expansion of classical Job-shop Scheduling Problem (JSP) where operations have a set of eligible machines, unlike only a single machine at JSP. FJSP is classified as non-polynomial-hard (NP-hard) problem. Researchers developed different techniques including Genetic Algorithm (GA) that is widely used for solving FJSP. Regular GAs for FJSP determine both operation sequencing and machine assignment through genetic search. In this paper, we developed a highly efficient Two-Stage Genetic Algorithm (2SGA) that in the first stage, GA coding only determines the order of operations for assignment. But machines are assigned through an evaluation process that starts from the first operation in the chromosome and chooses machines with the shortest completion time considering current machine load and process time. At the end of the first stage, we have a high-quality solution population that will be fed to the second stage. The second stage follows the regular GA approach for FJSP and searches the entire solution space to explorer solutions that might have been excluded at the first stage because of its greedy approach. The efficiency of proposed 2SGA has been successfully tested using published benchmark problems and also generated examples of different sizes. The quality of the 2SGA solutions greatly exceeds regular GA, especially for larger size problems. (C) 2019, IFAC (International Federation of Automatic Control) Hosting by Elsevier Ltd. All rights reserved.