Main content

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

Show full item record

Title: Efficient Two-Stage Genetic Algorithms for Comprehensive Multi-Objective Flexible Job Shop Scheduling Problems
Author: Rooyani, Danial
Department: School of Engineering
Program: Engineering
Advisor: Defersha, Fantahun
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.
Date: 2023-04
Terms of Use: All items in the Atrium are protected by copyright with all rights reserved unless otherwise indicated.
Related Publications: Danial Rooyani and Fantahun M. Defersha. An E cient Two-Stage Genetic Algorithm for Flexible Job-Shop Scheduling. IFAC-PapersOnLine, 52(13):2519{2524, 2019. ISSN 24058963. doi: 10.1016/j.ifacol.2019.11.585Danial Rooyani and Fantahun Defersha. A Two-Stage Multi-Objective Genetic Algorithm for a Flexible Job Shop Scheduling Problem with Lot Streaming. Al- gorithms, 15(7):246, jul 2022. ISSN 1999-4893. doi: 10.3390/a15070246Fantahun M. Defersha and Danial Rooyani. An e cient two-stage genetic algorithm for a exible job-shop scheduling problem with sequence dependent attached/detached setup, machine release date and lag-time. Computers and Industrial Engineering, 147:106605, sep 2020. ISSN 03608352. doi: 10.1016/j.cie.2020.106605

Files in this item

Files Size Format View Description
Rooyani_Danial_202304_PhD.pdf 9.872Mb PDF View/Open Thesis

This item appears in the following Collection(s)

Show full item record

The library is committed to ensuring that members of our user community with disabilities have equal access to our services and resources and that their dignity and independence is always respected. If you encounter a barrier and/or need an alternate format, please fill out our Library Print and Multimedia Alternate-Format Request Form. Contact us if you’d like to provide feedback:  (email address)