Incorporating the strength of MIP modeling in schedule construction
RAIRO - Operations Research - Recherche Opérationnelle, Tome 43 (2009) no. 4, pp. 409-420.

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.

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.

DOI : 10.1051/ro/2009026
Classification : 90C11, 90B35
Keywords: scheduling, integer programming, lower bounds, hybrid methods
Mots clés : planification, programmation en nombres entiers, bornes inférieures, hybridisation
@article{RO_2009__43_4_409_0,
     author = {Hurkens, Cor A. J.},
     title = {Incorporating the strength of {MIP} modeling in schedule construction},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {409--420},
     publisher = {EDP-Sciences},
     volume = {43},
     number = {4},
     year = {2009},
     doi = {10.1051/ro/2009026},
     zbl = {1173.90405},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ro/2009026/}
}
TY  - JOUR
AU  - Hurkens, Cor A. J.
TI  - Incorporating the strength of MIP modeling in schedule construction
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2009
SP  - 409
EP  - 420
VL  - 43
IS  - 4
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ro/2009026/
DO  - 10.1051/ro/2009026
LA  - en
ID  - RO_2009__43_4_409_0
ER  - 
%0 Journal Article
%A Hurkens, Cor A. J.
%T Incorporating the strength of MIP modeling in schedule construction
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2009
%P 409-420
%V 43
%N 4
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ro/2009026/
%R 10.1051/ro/2009026
%G en
%F RO_2009__43_4_409_0
Hurkens, Cor A. J. Incorporating the strength of MIP modeling in schedule construction. RAIRO - Operations Research - Recherche Opérationnelle, Tome 43 (2009) no. 4, pp. 409-420. doi : 10.1051/ro/2009026. http://www.numdam.org/articles/10.1051/ro/2009026/

[1] D. Applegate and W. Cook, A computational study of the job-shop scheduling problem. ORSA J. Comput. 3 (1991) 149-156. | Zbl

[2] E.L. Lawler and J. Labetoulle, On preemptive scheduling of unrelated parallel processors by linear programming. J. Assoc. Comput. Mach. 25 (1978) 612-619. | MR | Zbl

[3] Y. Pochet and Laurence A. Wolsey, Production planning by mixed integer programming. Springer Series in Operations Research and Financial Engineering. Springer, New York (2006) xxiv+499 p. | MR | Zbl

Cité par Sources :