|Duration:||June 2010 - May
heads:||Rolf H. Möhring |
Marco E. Lübbecke 
|Support:||DFG Research Center
"Mathematics for Key Technologies" (Matheon
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.
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.
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?
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.
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.
|Author||Günther, Elisabeth and Maurer, Olaf and Megow, Nicole and Wiese, Andreas|
|Institution||Technische Universität Berlin, Institut für Mathematik|
|Abstract||We propose a new approach to competitive analysis by introducing the novel concept of online approximation schemes. Such scheme algorithmically constructs an online algorithm with a competitive ratio arbitrarily close to the best possible competitive ratio for any online algorithm. We study the problem of scheduling jobs online to minimize the weighted sum of completion times on parallel, related, and unrelated machines, and we derive both deterministic and randomized algorithms which are almost best possible among all online algorithms of the respective settings. Our method relies on an abstract characterization of online algorithms combined with various simplifications and transformations. We also contribute algorithmic means to compute the actual value of the best possible competitive ratio up to an arbitrary accuracy. This strongly contrasts all previous manually obtained competitiveness results for algorithms and, most importantly, it reduces the search for the optimal competitive ratio to a question that a computer can answer. We believe that our method can also be applied to many other problems and yields a completely new and interesting view on online algorithms.|
|Bibtex Type of Publication||Preprint|
- 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 
- Ship Traffic Optimization for the Kiel Canal
Wasser- und Schifffahrtsamt Kiel-Holtenau .
- 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.