No-wait Job-Shop Scheduling: Komplexität und Local Search

by Schuster, Christoph J.

Abstract (Summary)
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.
Bibliographical Information:

Advisor:Prof. Dr. Günter Törner; Prof. Dr. Rainer Leisten

School:Universität Duisburg-Essen, Standort Essen

School Location:Germany

Source Type:Master's Thesis

Keywords:mathematik universitaet duisburg essen


Date of Publication:04/29/2003

© 2009 All Rights Reserved.