What are the Most Effective, Robist, and Computationally Efficient Metaheuristic and Heuristic Optimization Algorithms for Solvin the Flexible Job Shop Problem?
No Thumbnail Available
URL
Journal Title
Journal ISSN
Volume Title
School of Business |
Bachelor's thesis
Electronic archive copy is available locally at the Harald Herlin Learning Centre. The staff of Aalto University has access to the electronic bachelor's theses by logging into Aaltodoc with their personal Aalto user ID. Read more about the availability of the bachelor's theses.
Authors
Date
2023
Department
Major/Subject
Mcode
Degree programme
Tieto- ja palvelujohtaminen
Language
en
Pages
68
Series
Abstract
The flexible job shop problem (FJSP) is a standard NP-hard combinatorial optimization problem that is important from a practical perspective. There are many solution methods available for FJSP, but in this study, I focus on the metaheuristic and heuristic scheduling algorithms. This choice is justified in chapter 3. In FJSP, there is a set of jobs that are divided into operations and a set of machines that process the operations. The jobs are independent of each other, but there are precedence constraints between operations belonging to the same job. The problem is to find a capable machine to process each operation and schedule the operations while preserving the precedence and other constraints. In this study, the focus is mainly on a single objective FJSP (makespan minimization), but many algorithms considered can also solve multiobjective FJSPs. The main idea of this study is to find and introduce briefly specific algorithms from the literature and compare them in benchmark problem sets of FJSP. According to Chaudhry & Khan (2016a), four of the most common algorithm paradigms in the field of FJSP are: hybrid, evolutionary algorithms, heuristics, and tabu search. These four were selected, but a slight modification was made: GA was selected to represent the wide field of evolutionary algorithms. In addition, the PSO and the ACO are included, since they are often combined with other algorithms to create powerful hybrid algorithms. The algorithms are compared in three main criteria: effectiveness, robustness, and computational efficiency. In addition, other aspects and elements and features of the algorithms i.e. neighborhood structure or elite strategy, are selectively discussed. In the comparison, four algorithms were identified that excelled in all three main criteria. Many more showed impressive performance on one or two criteria but did not make it to the former group due to the lack of data, which prevented examination of one or more main criteria. In chapter 6, the implications and limitations of this study were discussed. In addition, future research directions were given to enable even better and more fair comparisons between algorithms in the field of FJSP. Finally, in chapter 7, some conclusions and remarks were made. It was found that the best algorithms considered in this study differed much more in computational efficiency than in solution quality. In addition, it was observed that no algorithm paradigm shows clear dominance in FJSP, quite the opposite, the best algorithms are a diverse group with many unique features.Description
Thesis advisor
Hekkala, RiittaKeywords
metaheuristic, heuristic, GA, TS, PSO, ACO, hybrid algorithm, FJSP