Christoph Schuster : 

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

Dissertation angenommen durch: Gerhard-Mercator-Universität Duisburg, Fakultät für Naturwissenschaften, Institut für Mathematik, 2003-04-04

BetreuerIn: Prof. Dr. Günter Törner , Gerhard-Mercator-Universität Duisburg, Fakultät für Naturwissenschaften, Institut für Mathematik

GutachterIn: Prof. Dr. Günter Törner , Gerhard-Mercator-Universität Duisburg, Fakultät für Naturwissenschaften, Institut für Mathematik
GutachterIn: Prof. Dr. Rainer Leisten , Gerhard-Mercator-Universität Duisburg, Fakultät für Wirtschaftswissenschaften, Institut für Logistik und Informationsmanagement

 
Schlüsselwörter in Englisch: np-hard, taboo search, flow shop   

  
   
 Klassifikation     
    MSC Primary: 90B35
Sachgruppe der DNB: 27 Mathematik		  
   
 Abstrakt     
   

Abstrakt in Deutsch

Gegenstand der vorliegenden Arbeit ist eine Untersuchung der Struktur des no-wait Job-Shop-Problems sowie die Ableitung schneller Algorithmen zu seiner approximativen Lösung. Die Basis des in dieser Arbeit verfolgten Ansatzes ist eine Problemzerlegung in ein Sequencing- und ein Timetabling-Problem, die auch von Macchiaroli et al. (1999) und Framinan (2002) verfolgt wurde. Dieser Zerlegungsansatz wird in der vorliegenden Arbeit jedoch sowohl vertieft als auch weiterentwickelt. Zunächst werden beide auftretenden Teilprobleme in dieser Arbeit als streng NP-hart nachgewiesen. Sodann werden die relevanten Timetabling-Probleme als gemischt-ganzzahlige Programme formuliert und ein schneller heuristischer Lösungsalgorithmus abgeleitet. Die Lösung des Sequencing-Problems bildet daher den Kern der weiteren Untersuchung. Zu seiner Lösung wird zunächst eine Klasse von Nachbarschaften definiert, die die bei solchen Problemen üblichen und auch von den oben genannten Quellen verwendeten jump-Nachbarschaften verallgemeinert. Im Zusammenhang mit dem gewählten Ansatz lassen sich für diese Nachbarschaften Struktursätze ableiten, die die Rechengeschwindigkeit von darauf basierenden Local Search Verfahren durch die Wiederverwendbarkeit von Zwischenresultaten vervielfachen. Unter Verwendung dieser Nachbarschaften werden dann verschiedene Klassen von Local Search Verfahren für das no-wait Job-Shop-Problem implementiert und kalibriert. Die Effizienz der Algorithmen wird an Hand von umfangreichen Experimenten an Benchmarkinstanzen von no-wait Job-Shop und no-wait Flow-Shop-Problemen sowie realen Probleminstanzen aus einem Unternehmen der Galvanoindustrie demonstriert. Dabei erweist sich das hier entwickelte Tabu Search Verfahren den vergleichbaren Algorithmen aus der Literatur als klar überlegen. 

Abstrakt in Englisch

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.