“Models and Methods for Project Scheduling and Traffic Management”

A course held by Prof. Rolf H. Möhring (moehring@math.tu-berlin.de)
 June 2 - 6, 2003 - CSC - Università degli Studi di Siena



Syllabus

June 2
Project scheduling with resource constraints and time windows
We will study a very general model in deterministic scheduling that covers most problems occurring in practical applications. It covers ordinary precedence constraints, time windows for jobs and arbitrary resource constraints. Topics covered include:
- NP-hardness and non-approximability
- IP-models and Lagrangean relaxation via min cut calculations
- LP-guided construction of good schedules

June 3
Scheduling under uncertainty
An important feature of scheduling are uncertainty aspects occurring during project execution. These are mostly neglected in practice and typically result in the underestimation of the makespan and the cost of a project. We will present methods to cope with these uncertainty aspects.
Project risk analysis under uncertainty
We will discuss risk measures that capture uncertainties of project execution and study methods for their computation. This turns out to be already quite involved in the simple case when no online decisions about resource allocations must be made. In particular we will study:
- the underestimation error of deterministic planning
- the complexity of computing statistical data of the makespan distribution
- algorithms for approximating the makespan distribution

June 4
Policies for scheduling under uncertainty
In the presence of uncertainty and scarce resources, scheduling must be done by an online process of iterative scheduling decisions that use the available information and aim at minimizing the scheduling objective in expectation. We will review common classes of policies and discuss their behaviour with respect to optimality, stability, and approximability. Topics covered include:
- a comparison of classes of policies
- combinatorial properties of policies and AND/OR networks
- performance guarantees for policies


June 5
Traffic Management - Network flow models for car traffic
Traffic management in large networks combines methods from combinatorial optimization and nonlinear optimization. We will first study
rush hour traffic with congestion, which leads to multicommodity network flows with convex objective. We study the main routing policies based on user equilibrium and system optimum, their computation, and how to include fairness into routing policies. Topics presented include
- user equilibrium and system optimum
- enforcing fairness on the system optimum
- computation of user equilibrium and system optimum under rush hour conditions


June 6
Dynamic traffic models and flows over time
Besides congestion, traffic has also a temporal dimension that is no longer captured by static flow theory, but requires a study of "flows over time". We will give an introduction into flows over time and cover the following topics
- the quickest flow problem
- flows over time with congestion
- approximation of flows over time

Slides

The complete slides of the lectures (14.7 Mb) can be downloaded from:
http://www.math.tu-berlin.de/~moehring/moehring-slides-siena.pdf

Participants

 Click here to see the list of participants

References 

=====================================
Project Scheduling
=====================================
Main Papers

Rolf H. Möhring, Andreas S. Schulz, Frederik Stork, and Marc Uetz,
Solving Project Scheduling Problems by Minimum Cut Computations
http://www.math.tu-berlin.de/coga/publications/techreports/2000/Report-680-2000.html

Rolf H. Möhring,
Scheduling under Uncertainty: Optimizing Against a Randomizing Adversary
http://www.math.tu-berlin.de/coga/publications/techreports/2000/Report-681-2000.html

Rolf H. Möhring,
Scheduling under uncertainty: Bounding the makespan distribution
http://www.math.tu-berlin.de/coga/publications/techreports/2000/Report-700-2000.html

Additional Papers

Rolf H. Möhring, Andreas S. Schulz, Frederik Stork, and Marc Uetz,
On Project Scheduling with Irregular Starting Time Costs
http://www.math.tu-berlin.de/coga/publications/techreports/2000/Report-664-2000.html

Rolf H. Möhring, Martin Skutella, and Frederik Stork,
Scheduling with AND/OR precedence constraints
http://www.math.tu-berlin.de/coga/publications/techreports/2000/Report-689-2000.html


=====================================
Traffic Management
=====================================
Main Papers

Ekkehard Köhler, Rolf H. Möhring, and Martin Skutella,
Traffic Networks and Flows Over Time
http://www.math.tu-berlin.de/coga/publications/techreports/2002/Report-752-2002.html

Olaf Jahn, Rolf H. Möhring, Andreas S. Schulz, and Nicolas E. Stier Moses,
System Optimal Routing of Traffic Flows with User Constraints in Networks with Congestion
http://www.math.tu-berlin.de/coga/publications/techreports/2002/Report-754-2002.html

Additional Papers

Ekkehard Köhler, Katharina Langkau, and Martin Skutella,
Time-Expanded Graphs for Flow-Dependent Transit Times
http://www.math.tu-berlin.de/coga/publications/techreports/2002/Report-762-2002.html

Ekkehard Köhler and Martin Skutella,
Flows over time with load-dependent transit times
http://www.math.tu-berlin.de/coga/publications/techreports/2001/Report-712-2001.html