Logistics and scheduling are central issues on networks. Four top researchers will discuss some of the important themes. Gerhard Woeginger (Rheinisch-Westfälische Technische Hochschule Aachen) will give the keynote lecture. The other lectures are given by Rolf Möhring (Technische Universität Berlin), Guido Schaefer (CWI/VU) and Vincenzo Bonifaci (IASI-CNR).
The track will discuss logistic and scheduling problems and methods from an algorithmic and mathematical point of view, with applications in traffic and transportation.
Parametrized Complexity for Scheduling
The typical input to a typical scheduling problem consists of a lot of data:
job processing times, release dates, precedence constraints, deadlines,
weights for measuring the urgency of a job, machine speeds, machine
unavailability times, etc.
The talk looks at this situation from the view point of parametrized
complexity: What are the crucial parameters that determine the computational
complexity of the scheduling problem? How does the problem behave, if these
parameters are moderately small? What if these parameters are frozen?
The talk presents a variety of positive and negative results, develops the
necessary tools, and gives many examples.
Traffic management and routing in logistic systems are optimization problems by nature. One wants to utilize the available street or logistic network in such a way that the network “load” is minimized or the “throughput” is maximized. The aspects of “time” and “congestion” play a crucial role in these problems and require new techniques that need to integrate dynamic network flows and scheduling.
The lecture will illustrate this on the example of the Kiel Canal problem, which came up in a project with the German Federal Waterways and Shipping Administration. It is a hard optimization problem that deals with routing bidirectional ship traffic on the Kiel Canal, the world’s busiest artificial waterway with more passages than the Panama and Suez Canal together. The problem arises from scarce resources (locations) at which large ships can only pass each other in opposing directions. This requires decisions on who should wait for whom (scheduling), in which siding to wait (packing) and when and how far to steer a ship between sidings (routing), and all this for online arriving ships at both sides of the canal.
The combination of routing and scheduling (without the packing) leads to a new class of scheduling problems dealing with scheduling bidirectional traffic on a path, and we will address recent complexity and approximation results for this class.
For the full problem, we need a feasible assignment of parking slots within sidings over time that is consistent with the scheduling decisions between the sidings and the routing. To that end, we use a routing algorithm that we had developed earlier for routing automated guided vehicles in a container terminals (cooperation with HHLA), which we will also illustrate.
Computational experiments on real traffic data with results obtained by human expert planners show that our combinatorial algorithm improves upon manual planning by 25%. It was subsequently used to identify bottlenecks in the canal and to make suggestions for enlarging the capacity of critical sections of the canal to make it suitable for future traffic demands.
(joint work with Elisabeth Lübbecke and Marco E. Lübbecke)
Congestion games constitute an important class of games which capture many applications in network routing, resource allocation and scheduling. Intuitively, these games model situations in which several independent agents (or players) compete over a limited number of resources, where each resource has a cost that increases with the number of players using it. The goal of each player is to allocate a feasible subset of the resources such that her individual cost is minimized.
In a seminal paper, Rosenthal (1973) establishes the existence of pure Nash equilibria in congestion games by exhibiting an exact potential function whose local minima coincide with the set of pure Nash equilibria of the game. This correspondence has helped to shed light on several important aspects of congestion games in recent years. In particular, it is exploited crucially to show that finding pure Nash equilibria is a computationally hard problem in general.
In our recent work, we investigate structural properties of congestion games which allow us to efficiently compute global minima of Rosenthal's potential function. To this aim, we use a polyhedral description to represent the strategy sets of the players and identify two general properties which are sufficient for our results to go through. In addition, we show that the resulting pure Nash equilibria provide attractive social cost approximation guarantees. Our contributions thus provide an efficient algorithm to find an approximately optimal Nash equilibrium for a large class of polytopal congestion games.
In this talk, we review some of the classical results and elaborate in a bit more detail on our recent results on polytopal congestion games (joint work with Pieter Kleer).
Parallel Scheduling with Hierarchical Processor Affinities
We propose a model for scheduling jobs in a parallel machine setting that takes into account the cost of migrations, by assuming that the processing time of a job may depend on the specific set of machines among which the job is migrated. For the makespan minimization objective, the model generalizes classical scheduling problems such as unrelated parallel machine scheduling, as well as novel ones such as semi-partitioned and clustered scheduling. In the case of a hierarchical family of machines, we derive a compact integer linear programming formulation of the problem and leverage its fractional relaxation to obtain a polynomial-time approximation algorithm.
We also discuss a related online scheduling problem, where the goal is to guarantee an effective allocation of jobs to machines during the entire schedule.