Project C5: Stochastic and nonlinear methods for solving resource constrained scheduling problems

DFG Research Center Matheon Technische Universität Berlin
Duration: October 2002 - May 2006
Project director: Prof. Dr. Rolf H. Möhring
Institut für Mathematik, Technische Universität Berlin, Straße des 17. Juni 136, 10623 Berlin, Germany.
Tel: +49 (0)30 - 2 45 94
email: moehring@math.tu-berlin.de
Researcher: Nicole Megow
See above.
Tel: +49 (0)30 - / 314 25739 
email: nmegow@math.tu-berlin.de
Support: DFG Research Center "Mathematics for Key Technologies" (Matheon)


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.

[1] P. Brucker, A. Drexl, R. H. Möhring, K. Neumann, and E. Pesch. Resource-constrained project scheduling: Notation, classification, models, and methods. European J. Oper. Res., 112:3-41, 1999.
[2] M. X. Goemans. Semidefinite programming in combinatorial optimization. Mathematical Programming B, 79:143-161, 1997.
[3] M. X. Goemans, M. Queyranne, A. S. Schulz, M. Skutella, and Y. Wang. Single machine scheduling with release dates. SIAM Journal on Discrete Mathematics.
[4] R. H. Möhring. Scheduling under uncertainty: Optimizing against a randomizing adversary. In K. Jansen and S. Khuller, editors, Approximation Algorithms for Combinatorial Optimization, pages 15-26. Springer Verlag, Lecture Notes in Computer Science, vol. 1913, 2000.
[5] R. H. Möhring and F. Stork Linear preselective policies for stochastic project scheduling. MMOR, 52:501-515, 2000.
[6] M. Skutella. Convex quadratic and semidefinite programming relaxations in scheduling. J. Assoc. Comp. Mach., 48:206-242, 2001.


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.


Project Output.

Publications
Posters
  • Stochastische und Nichtlineare Ansätze in der Ressourcenbeschränkten Projektplanung (2004, German). [PDF]
  • Stochastic and nonlinear methods for solving resource constrained project scheduling problems (2005). [PDF]
Newspaper articles
Industrial projects
Diploma Students
  • Andreas Schmidtke
  • Philip Kemmer, Dynamische Losgrössenoptimierung mit reihenfolgeabhängigen Umrüstzeiten, 2004.