Shop scheduling problems with transportation

摘要

In this thesis scheduling problems with transportation aspects are studied. Classical scheduling models for problems with
\nmultiple operations are the so-called shop-scheduling models. In these models jobs consisting of different operations have
\nto be planned on certain machines in such a way that a given objective function is minimized. Each machine may process at
\nmost one operation at a time and operations belonging to the same job cannot be processed simultaneously. We generalize
\nthese classical shop-scheduling problems by assuming that the jobs additionally have to be transported between the
\nmachines. This transportation has to be done by robots which can handle at most one job at a time. Besides transportation
\ntimes which occur for the jobs during their transport, also empty moving times are considered which arise when a robot
\nmoves empty from one machine to another. Two types of problems are distinguished: on the one hand, problems without
\ntransportation conflicts (i.e. each transportation can be performed without delay), and on the other hand, problems where
\ntransportation conflicts may arise due to a limited capacity of transport robots.
\n
\nIn the first part of this thesis several new complexity results are derived for flow-shop problems with a single robot. Since
\nvery special cases of these problems are already NP-hard, in the second part of this thesis some techniques are developed
\nfor dealing with these hard problems in practice. We concentrate on the job-shop problem with a single robot and the
\nmakespan objective. At first we study the subproblem which arises for the robot when some scheduling decisions for the
\nmachines have already been made. The resulting single-machine problem can be regarded as a generalization of the
\ntraveling salesman problem with time windows where additionally minimal time-lags between certain jobs have to be
\nrespected and the makespan has to be minimized. For this single-machine problem we adapt immediate selection
\ntechniques used for other scheduling problems and calculate lower bounds based on linear programming and the technique
\nof column generation. On the other hand, to determine upper bounds for the single-machine problem we develop an efficient
\nlocal search algorithm which finds good solutions in reasonable time. This algorithm is integrated into a local search
\nalgorithm for the job-shop problem with a single robot. Finally, the proposed algorithms are tested on different test data and
\ncomputational results are presented.