Suitability of Genetic Algorithms for solving Flexible Job Shop Problems
M.V. Ivanov (TU Delft - Electrical Engineering, Mathematics and Computer Science)
Mathijs M. Weerdt – Mentor (TU Delft - Algorithmics)
K.C. van den Houten – Mentor (TU Delft - Algorithmics)
Burcu Ozkan – Graduation committee member
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
Abstract
The aim of this research paper is to present two genetic algorithms targeted at solving the Flexible Job Shop Problem (FJSP). The first one only tackles a single objective - the schedule makespan, while the second one takes into account multiple objectives for the problem. Each schedule is represented by two integer vectors - one for the machine assignments and one for the operation sequence. Special care is taken to only produce valid schedules when generating the starting population and applying the mutation and crossover operations for further populations. A Mixed Integer Linear Programming (MILP) solution to the FJSP is presented and used as a benchmark for the feasibility of the genetic algorithms. The algorithms are tested on a set of 13 provided problem instances. The results showcase that genetic algorithms outperform the MILP implementation for large problem instances and produce solutions much faster.