Incorporating the strength of MIP modeling in schedule construction

Eindhoven University of Technology, Department of Mathematics and Computer Science, P.O. Box 513, 5600 MB Eindhoven, The Netherlands; wscor@win.tue.nl

Received: 1 December 2008
Accepted: 17 June 2009

Abstract

Linear programming techniques can be used in constructing schedules but their application is not trivial. This in particular holds true if a trade-off has to be made between computation time and solution quality. However, it turns out that – when handled with care – mixed integer linear programs may provide effective tools. This is demonstrated in the successful approach to the benchmark constructed for the 2007 ROADEF computation challenge on scheduling problems furnished by France Telecom.

Résumé

L'application de techniques programmation linéaire pour la résolution de problème d'ordonnancement n'est pas trivial, particulièrement lorsque qu'un compromis entre qualité de la solution fournie et temps de calcul est recherché. Dans ce cas des heuristiques peuvent être couplées pour améliorer les performances des modèles de programmation linéaire. La combinaison de telles méthodes a montré son efficacité dans le cadre de la résolution du Challenge ROADEF 2007.