Shop-Scheduling Problems with Transportation

Bitte benutzen Sie diese Kennung, um auf die Ressource zu verweisen:
Titel: Shop-Scheduling Problems with Transportation
Autor(en): Knust, Sigrid
Erstgutachter: Prof. Dr. Peter Brucker
Zweitgutachter: Prof. Dr. Gerd Finke
Zusammenfassung: In this thesis scheduling problems with transportation aspects are studied. Classical scheduling models for problems with multiple operations are the so-called shop-scheduling models. In these models jobs consisting of different operations have to be planned on certain machines in such a way that a given objective function is minimized. Each machine may process at most one operation at a time and operations belonging to the same job cannot be processed simultaneously. We generalize these classical shop-scheduling problems by assuming that the jobs additionally have to be transported between the machines. This transportation has to be done by robots which can handle at most one job at a time. Besides transportation times which occur for the jobs during their transport, also empty moving times are considered which arise when a robot moves empty from one machine to another. Two types of problems are distinguished: on the one hand, problems without transportation conflicts (i.e. each transportation can be performed without delay), and on the other hand, problems where transportation conflicts may arise due to a limited capacity of transport robots. In the first part of this thesis several new complexity results are derived for flow-shop problems with a single robot. Since very special cases of these problems are already NP-hard, in the second part of this thesis some techniques are developed for dealing with these hard problems in practice. We concentrate on the job-shop problem with a single robot and the makespan objective. At first we study the subproblem which arises for the robot when some scheduling decisions for the machines have already been made. The resulting single-machine problem can be regarded as a generalization of the traveling salesman problem with time windows where additionally minimal time-lags between certain jobs have to be respected and the makespan has to be minimized. For this single-machine problem we adapt immediate selection techniques used for other scheduling problems and calculate lower bounds based on linear programming and the technique of column generation. On the other hand, to determine upper bounds for the single-machine problem we develop an efficient local search algorithm which finds good solutions in reasonable time. This algorithm is integrated into a local search algorithm for the job-shop problem with a single robot. Finally, the proposed algorithms are tested on different test data and computational results are presented.
Schlagworte: scheduling; transportation; job-shop problem; traveling salesman problem; complexity results; lower bounds; immediate selection; local search
Erscheinungsdatum: 26-Sep-2000
Enthalten in den Sammlungen:FB06 - E-Dissertationen

Dateien zu dieser Ressource:
Datei Beschreibung GrößeFormat 
E-Diss12_thesis.psPräsentationsformat1,01 MBPostscriptÖffnen/Anzeigen

Alle Ressourcen im repOSitorium sind urheberrechtlich geschützt, soweit nicht anderweitig angezeigt.