### Inhalt des Dokuments

Duration: | June 2010 - May 2014 |
---|---|

Project heads: | Rolf H. Möhring Marco E. Lübbecke |

Researcher: | Elisabeth Günther |

Support: | DFG Research Center "Mathematics for Key Technologies" (Matheon) |

### Background

Scheduling deals with allocating tasks to scarce resources over time whereas routing demands for decisions concerning space, typically in a network. In several optimization problems we see both aspects, like in the classical vehicle routing problem with time windows. Yet, so far the two concepts are treated rather separately than in a truly integrated way.

Material flows in logistics ask for an integrated approach. They involve the complex situation that the capacity or availability of resources changes over time and depends on the routing of the tasks or even of the resources themselves in a (logical or physical) network.

### Research program

This project's goal is to combine scheduling theory and algorithms with the complicated resource and task dependencies which stem from routing decisions in networks, and which are present in various logistics applications. The work program to be accomplished comprises three major areas.

1.Theory:

Scheduling theory has much to offer on resource capacities (also varying over time), sequence dependent setup cost, or e.g., flow shops. However, a theoretical notion of “inter-dependency” of resources and tasks through time and space is not known and shall be developed in this project. When clarifying the complexity status, a different interpretation of dependency is to consider network flows as performing the “movement of flow” by capacitated resources (machines) which move along the network themselves. The possibly conflicting machines can be considered as adversaries which brings us in the realm of games on networks.

Further interesting questions occur when thinking of the “degree of interdependency” between routing and scheduling. What is its influence on the optimization potential that may be gained by an integrated treatment? Can we characterize in which situations one of the two aspects is more influential? Will (modest) separation of the two aspects lead to approximation algorithms for the integrated problem?

2. Models:

Currently, it is not even clear how to accurately model a situation where the cost of a schedule can be evaluated only when the *whole* schedule is known by, say, an integer program. Even for combinatorial relaxations, models are far from being tractable, even with large-scale techniques like branch-and-price. In order to actually compute solutions we need to identify suitable relaxations or decomposition approaches. As a starting point we will consider resource constraint scheduling where the competition for scarce resources can be interpreted via a *static conflicts* graph. When we incorporate routing decisions for tasks over time, conflicts become dynamic, and a possible representation is given by dynamic conflict graphs. Identifying suitable parameters of this dynamics may be the key to good algorithms. Here we will use our expertise from B8 to obtain approximate solutions, e.g., with the help of condensed time-expanded (dynamic) conflicts graphs.

3. Applications:

Not all practical situations bear the full complexity of integrated scheduling and flows. For theoretical and computational reasons it is important to study special cases, e.g., cases with a simple network topology or limited resource dependencies. One such case is the control of ship traffic through the Kiel canal (German: Nord-Ostsee-Kanal), which is considered the world`s busiest artificial waterway. Bi-directional ship traffic, in particular entering, passing, overtaking, safety distances, and waiting at turnouts, is precisely regulated, but the actual scheduling is done manually by experienced helmsmen. The Wasser- und Schifffahrtsamt Kiel-Holtenau will engage with us is a project to develop optimization algorithms for an improved traffic control and for an optimized design of the enlargement of the canal capacity scheduled for 2010--2012.

A more complex industrial application with PSI-BT involves the scheduling of several cranes in a steel yard in order to transport steel slabs between various locations. We see this problem as a prototype of integrated scheduling and routing. To solve this problem, we will also build on our computational work for Swiss Federal Railways where a first approach to flow conservation over time was developed.

Related applications, which all have their interpretation in our general setting, are railroad shunting problems, scheduling laser welding robots (C30), or the integration of line planning and timetabling in public transport (B15). We will revisit these (and the theoretical and algorithmic results obtained) when developing a unified view.

### Publications

Günther, Elisabeth and König, Felix G. and Megow, Nicole

**Scheduling and Packing Malleable and Parallel Tasks with Precedence Constraints of Bounded Width**.

*Journal of Combinatorial Optimization*, Vol. 27, pp. 164-181, 2014.
[pdf]

Günther, Elisabeth and Maurer, Olaf and Megow, Nicole and Wiese, Andreas

**A New Approach to Online Scheduling: Approximating the Optimal Competitive Ratio**.

In *Proceedings of the 24st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2013)*, pp. 118-128, 2013.
[pdf]

Gellert, Torsten J. and König, Felix G.

**1D Vehicle Scheduling with Conflicts**.

In *Proceedings of the Workshop on Algorithm Engineering and Experiments, ALENEX 2011*, pp. 107-115, Society for Industrial and Applied Mathematics, 2011.

### Extended abstracts

Günther, Elisabeth and Lübbecke, Marco E. and Möhring, Rolf H.

**Challenges in Scheduling when Planning the Ship Traffic on the Kiel Canal**.

In *Proceedings of the 10th Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP 2011)*, 2011.
[pdf]

Günther, Elisabeth and Lübbecke, Marco E. and Möhring, Rolf H.

**Ship Traﬃc Optimization for the Kiel Canal**.

In *Proceedings of the Seventh Triennial Symposium on Transportation Analysis (TRISTAN 2010)*, 2010.
[pdf]

### Technical reports

Lübbecke, Elisabeth and Lübbecke, Marco E. and Möhring, Rolf H.

**Ship Traffic Optimization for the Kiel Canal**.

Preprint 4681, Optimization Online, 2014.

Günther, Elisabeth and Maurer, Olaf and Megow, Nicole and Wiese, Andreas

**A New Approach to Competitive Analysis: Approximating the Optimal Competitive Ratio**.

Preprint 031, Technische Universität Berlin, Institut für Mathematik, 2011.
[pdf]

### Posters

- Scheduling Material Flows in Logistics Networks, 2010

[download]

### Cooperations

- Matheon B13: Optimization under Uncertainty in Logistics and Scheduling
- Matheon B18: Applications of Network Flows in Evacuation Planning
- Matheon B23: Robust Optimization for Network Applications
- Matheon C30: Automatic reconfiguration of robotic welding cells
- ZIB, KOSMOS - Optimal routing of rail freight traffic

### Diploma students

- Martin Luy, Algorithmen zum Scheduling von Schleusenvorgängen am Beispiel des Nord-Ostsee-Kanals, 2010.
- Robert Pankrath, Algorithmen für die Verkehrsflussoptimierung auf dem Nord-Ostsee-Kanal, 2010.
- Torsten Gellert, Steuerung von Kränen auf einer Schiene: Optimierung von 1-dimensionalen Transportsystemen, 2009.