No-wait Job-Shop Scheduling : Komplexität und Local Search
This thesis deals with the structure of the no-wait job-shop problem as well as the derivation of fast approximation algorithms. These algorithms are based on a decomposition approach into a sequencing and a timetabling problem that was initially introduced by Macchiaroli et al. (1999). In the thesis the problems are derived from a mixed integer formulation of the original problem and proved to be NP-hard in the strong sense. After presenting a fast heuristic approach for the timetabling problem, the focus lies on the sequencing problem for which several local search algorithms are presented. The algorithms are tested on a wide variety of benchmark problems for the classical job-shop problem. Among the algorithms, the tabu search approach outperforms all other algorithms that can be found in the literature in objective value as well as computation time.
copy citation link