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.
| Identifer | oai:union.ndltd.org:DUETT/oai:DUETT:duett-04242003-131618 |
| Date | 29 April 2003 |
| Creators | Schuster, Christoph J. |
| Contributors | Prof. Dr. Günter Törner, Prof. Dr. Rainer Leisten |
| Publisher | Gerhard-Mercator-Universitaet Duisburg |
| Source Sets | Dissertations and other Documents of the Gerhard-Mercator-University Duisburg |
| Language | German |
| Detected Language | English |
| Type | text |
| Format | text/html, application/pdf |
| Source | http://www.ub.uni-duisburg.de/ETD-db/theses/available/duett-04242003-131618/ |
| Rights | unrestricted, I hereby certify that, if appropriate, I have obtained and attached hereto a written permission statement from the owner(s) of each third party copyrighted matter to be included in my thesis, dissertation, or project report, allowing distribution as specified below. I certify that the version I submitted is the same as that approved by my advisory committee. Hiermit erteile ich der Universitaet Duisburg das nicht-ausschliessliche Recht unter den unten angegebenen Bedingungen, meine Dissertation, Staatsexamens- oder Diplomarbeit, meinen Forschungs- oder Projektbericht zu veroeffentlichen und zu archivieren. Ich behalte das Urheberrecht und das Recht das Dokument zu veroeffentlichen und in anderen Arbeiten weiterzuverwenden. |
Page generated in 0.002 seconds