Shop-Scheduling Problems with Transportation

Please use this identifier to cite or link to this item:
Open Access logo originally created by the Public Library of Science (PLoS)
Title: Shop-Scheduling Problems with Transportation
Authors: Knust, Sigrid
Thesis advisor: Prof. Dr. Peter Brucker
Thesis referee: Prof. Dr. Gerd Finke
Abstract: 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.
Subject Keywords: scheduling; transportation; job-shop problem; traveling salesman problem; complexity results; lower bounds; immediate selection; local search
Issue Date: 26-Sep-2000
Type of publication: Dissertation oder Habilitation [doctoralThesis]
Appears in Collections:FB06 - E-Dissertationen

Files in This Item:
File Description SizeFormat 
E-Diss12_thesis.psPräsentationsformat1,01 MBPostscript

Items in osnaDocs repository are protected by copyright, with all rights reserved, unless otherwise indicated.