ISBN 9783843903103

978-3-8439-0310-3, Reihe Mathematik

Cornelius Schwarz
Integrated Routing & Scheduling

134 Seiten, Dissertation Universität Bayreuth (2011), Softcover, A5

Zusammenfassung / Abstract

A routing and scheduling problem can be defined as a routing problem with a number of servers, for instance a vehicle routing problem, bringing along a synchronization of the servers due to some shared resources. An important application is the collision avoidance of industrial robots working in the same work station.

We will model possible collisions as shared renewable resources among the robots. Another example of shared resources are "laser sources". These are needed to supply

arc welding robots with energy needed for the processing of welding seams. Generally, laser sources are very expensive resources. Therefore, the question motivating our studies was: "Assuming a certain number of welding robots, welding seams, and laser sources; will it be possible to process all tasks within the predefined cycle time?"

In order to prove that it is impossible, we have to find a lower bound for the makespan of every feasible solution which is above the cycle time. In the worst case, the makespan minimum has to be calculated by an exact solution method. In contrast, any solution where all robots finish in time provides a positive answer. Therefore, the goal of the laser sharing problem (LSP) is to find a scheduled dispatch with minimal makespan.

When the tours of the robots are prescribed, the problem can be brought down to a pure scheduling problem. More precisely, it generalizes the well known job-shop scheduling problem allowing a task to be processed on more than one machine simultaneously, e.g. on a laser source and on a collision resource. We will prove that this problem, which we call LSP-T, is NP-hard, even for three robots with a single laser source and no collision resources at all. However, we also provide a polynomial algorithm for two robots and a pseudo-polynomial algorithm together with a FPTAS an arbitrary but constant number of robots.

In the general LSP the tour calculation is part of the optimization process. For integrating the tour calculation we propose a branch-and-bound algorithm, which we call the combinatorial branch-and-bound method (cbb). This method can solve instances on industrial relevant problem scales, i.e. 2-4 robots and about 30 jobs.