A Heuristic Algorithm for the Flexible Job Shop Problem with Changeover Times
T. van Eijmeren (TU Delft - Electrical Engineering, Mathematics and Computer Science)
K.C. van den Houten – Mentor (TU Delft - Algorithmics)
Mathijs De Weerdt – Mentor (TU Delft - Algorithmics)
Burcu Özkan – Graduation committee member (TU Delft - Software Engineering)
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
In this paper a heuristic algorithm is described that can constructively produce solutions to a variant of the Flexible Job Shop Problem (FJSP) that introduces changeover times between each pair of two operations consecutively performed on a machine. The performance of the heuristic algorithm is compared to the performance of an exact solver. Seven heuristics are compared for the FJSP variant with changeovers. The main objective function used is the makespan of the created schedules. The difference that occurs in the quality of the seven heuristics is examined also when instead the total lateness across all jobs is chosen as objective function. It concludes that a heuristic algorithm allows for the creation of good feasible solutions to complex problem instances for the FJSP variation with changeover times in under 30 seconds and that it outperforms an exact algorithm for the FJSP with changeover for use cases where efficiency is important and runtime is limited.