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.
| Identifer | oai:union.ndltd.org:uni-osnabrueck.de/oai:repositorium.ub.uni-osnabrueck.de:urn:nbn:de:gbv:700-2000092637 |
| Date | 26 September 2000 |
| Creators | Knust, Sigrid |
| Contributors | Prof. Dr. Peter Brucker, Prof. Dr. Gerd Finke |
| Source Sets | Universität Osnabrück |
| Language | English |
| Detected Language | English |
| Type | doc-type:doctoralThesis |
| Format | application/zip, application/postscript |
| Rights | http://rightsstatements.org/vocab/InC/1.0/ |
Page generated in 0.0021 seconds