Efficient Two-Stage Genetic Algorithms for Comprehensive Multi-Objective Flexible Job Shop Scheduling Problems

Abstract

Among all the different scheduling problems, the Job shop Scheduling Problem (JSP) and Flexible job shop Scheduling Problem (FJSP) are the most popular and difficult optimization problems. FJSP is an expansion of JSP where an operation has a set of eligible machines, unlike only a single machine at JSP. JSP and FJSP are classified as non-polynomial-hard (NP-hard) problems that exact algorithms cannot guarantee finding the optimum solution in a finite time. So several heuristic and metaheuristic techniques have been developed to solve them, including Genetic Algorithm (GA), which is by far the most popular one. However, the quest for more efficient and effective algorithms continues. Regular GA (RGA) for solving FJSP determines both assignments of operations to machines and their sequences simultaneously through a random process guided by the principles of natural selection and evolution. In this research, we develop a Two- Stage Genetic Algorithm (2SGA), with the first stage being different from RGA for FJSP found in the literature. The first stage has a unique solution encoding that only determines the operation sequence for assignment and then uses a greedy approach to assign the machine with the quickest completion time to each operation, considering the current machine load and process time. The first stage creates a high-quality initial population for the second stage that follows the common approach of RGA for FJSP to enable the algorithm to search the entire solution space by including solutions that might have been excluded because of the greedy nature of the first stage. The efficiency of 2SGA compared to RGA and some other common algorithms has been successfully tested using published FJSP benchmark problems and randomly generated examples. We also applied 2SGA to more comprehensive FJSP models with several features, including detached or attached sequence-dependent setup, machine release date, process lag time, lot streaming, outsourcing option, and subassembly requirement. Numerous comprehensive sample problems have been generated to show that 2SGA out- performs the RGA in different aspects like convergence speed and solution quality. We also noted that the superiority of the 2SGA over RGA is much greater when solving large-size and more complex problems, rendering it a viable choice for solving practical problems typically encountered in industries. We also showed that further performance improvement of the 2SGA can be achieved using parallel computation. Parallel computation is considered the most effective method to improve GA performance. However, we have demonstrated using several numerical examples that the sequential version of the 2SGA (using a single CPU) outperforms a parallel implementation of the RGA that uses many CPUs. This shows that 2SGA is potentially a game-changing concept. The vast majority of scheduling algorithms consider only one or two objectives from a very limited list of performance metrics, while industries seek to optimize various performance measures simultaneously. Hence in this research, we expanded the 2SGA for the FJSP model to incorporate multiple (up to 10) objectives. Numerical examples are presented to illustrate the greater need for multi-objective optimization in larger problems due to their interaction and relevance in providing better solution quality. The results show the strong capability of 2SGA to jointly optimize all the objective functions and how it outperforms the RGA. However, 2SGA is not able to minimize the Earliness/Tardiness (E/T) objectives due to its greedy nature. This can be a pragmatic issue for 2SGA since job shops usually receive orders with due dates. So we have modified the 2SGA solution encoding further to include the intentional delay of the jobs and illustrated how it could address comprehensive multi-objective E/T FJSPs.