Applying hierarchical tabu search to an adapted version of the flexible job shop problem

Applying hierarchical tabu search to an adapted version of the flexible job shop problem

Jansen, Robin (TU Delft Electrical Engineering, Mathematics and Computer Science)

van den Houten, K.C. (mentor)
de Weerdt, M.M. (mentor)
Özkan, B. (graduation committee)

Delft University of Technology

Computer Science and Engineering

CSE3000 Research Project

2022-06-24

The scheduling departments of batch manufacturing plants have to repeatedly solve a complex scheduling problem for the operation of their production lines. This problem can be modeled as a flexible job shop problem (FJSP) in which a set of operations has to be assigned to a set of machines and then the order of operations on each machine has to be determined. The main difference to the general FJSP is that there are changeover times that appear between two sequential operations on the same machine. To solve this extended problem, a hierarchical tabu search method has been chosen. This algorithm makes use of a global selection initialization procedure as well as two neighborhood functions for the assignment and sequencing sub-problems. The objective of this project is to show the effectiveness of tabu search on this version of FJSP compared to a mathematical model serving as a baseline. The initialization procedure performs well compared to the baseline on larger instances while the neighborhood functions worsen the initially found result. This is also the case for a random initialization method which leads to believe that these neighborhood functions are non-optimal and should be replaced which could not have been achieved due to time constraints.

Flexible job shop
Hierarchical
Tabu search
Mixed integer linear programming

http://resolver.tudelft.nl/uuid:b24cb80f-dd03-4bf1-92b9-1d7f0e16015b

Student theses

bachelor thesis

© 2022 Robin Jansen