Project description.

Background.

The efficient utilization of scarce resources is a major challenge within production planning [1]. When modeled adequately, these problems lead to inherently hard computational problems. Moreover, deterministic models for project scheduling suffer from the fact that theyassume complete information and neglect random influences. The last years have witnessed a very fast development in the area of nonlinear convex programming relaxations [2]. The use of such relaxations has led to theoretical approximatin results but also to practically efficient methods for some problems. A similarly rapid development has taken place w.r.t. online models or models with random data [4].

Expertise.

Expert knowledge has been gained within the project group Project planning with limited resources sponsored by the DFG, a project within the BMBF program Mathematische Verfahren zur Lösung von Problemstellungen in Industrie und Wirtschaft (in cooperation with BASF AG), and during a project in cooperation with ATOSS Software AG.

Research program.

The aim of the project is to develop new methods for solving resource constrained project scheduling problems. One line of our research will be based on recently developed convex quadratic programming relaxations [6]. Due to the surprisingly compact size of those relaxations, there is well founded hope that this approach has the potential to outperform known methods which are usually based on linear formulations in a huge number of time-indexed variables and constraints. The other line of research will follow recent investigations on stochastic scheduling problems [4]. These are a special type of online models, in which scheduling is done by policies consisting of a sequential process of decisions that are based on the observed past and a priori knowledge of the distribution of processing times. A far reaching goal is to find a good policy in expectation and then analyze its cost distribution. Currently, this is only possible for very restricted classes of policies [5], as both the determination of an optimal policy and the evaluation of its distribution are computationally hard.

References.

Achievements.

We proposed stochastic online scheduling model that naturally combines the two classical models for dealing with incomplete information in scheduling: stochastic scheduling and online scheduling. We consider simple online scheduling policies for that model on a single machine and on identical parallel machines, respectively, and prove performance guarantees that match the currently best known performance guarantees for stochastic scheduling (Megow, Uetz, Vredeveld 2004 and 2005). As a side product we even improve some of them (see above and Megow, Schulz 2004).

Furthermore, we worked on a scheduling problem with generalized precedence constraints called AND/OR constraints. We provide a polynomial-time algorithm to verify feasibility of given constraints and complexity results in Möhring, Skutella, Stork (2004). Approximation algorithms with constant performance guarantee and inapproximability results for scheduling AND/OR-networks on parallel identical machines are published in Erlebach, Kääb, Möhring (2004).

Our expertise on handling incomplete information in optimization has also been successfully applied to an online server problem. In Gutierrez, Krumke, Megow, Vredeveld (2005), we study the problem where requests with deadlines appear online in a metric space. One or more servers are to be guided through the metric space such that the number of requests, reached before their deadline, is maximized. We study the problem on restriced metric spaces and provide competitive online algorithms for the uniform metric space. Our online investigations are complemented by complexity results for the offline problem.

Members of project C6 introduced us to the online target date assignment problem (OnlineTDAP) which they had derived from a real-world problem as it occurs in a dispatching call-center for service technicians of "Hermes Technischer Kundendienst". We propose general assignment strategies for several variants of the underlying OnlineTDAP and prove constant worst case competitive

On the side of industrial application, a model has been developed and implemented for the complex scheduling problem of optimally allocating lot sizes in the engine production for Smart cars of DaimlerChrysler in Berlin Marienfelde. Therefore, an LP-model has been derived from a quadratic formulation of the complex real-world problem (Kemmer 2004). The model has been tested for application in practice and it has been shown that in a relatively stable working production line all requirements can be met and the solution is found in reasonable time.

Cooperations.

• We obtained our results on stochastic online scheduling and the online server problem in cooperation with the Matheon project C3. On the online target date assignment problem we have been working jointly with members of projects C3 and C6. Both cooperations result from Tandem Workshops on Online Optimization (C3, C5, C6, B8) and on the TDAP (introduced by C6).
  R.H. Möhring co-organized a Dagstuhl Seminar on "Optimization with Incomplete Information" in which participated members of Matheon projects B6, C3, C5, C6, B8) C7 and D6.


• We successfully cooperated on scheduling with incomplete information with Marc Uetz (Universiteit Maastricht) and Andreas S.Schulz (MIT, Cambridge). Moreover, we discussed related topics during mutual visits of Rene Sitters, Leen Stougie (Universiteit Eindhoven) and Maria Minkoff (MPI Saarbrücken).

Project Output.