Voir la notice de l'article provenant de la source Numdam
In this article, we address the preemptive Resource-Constrained Precedence Scheduling Problem. We propose two mixed integer formulations containing an exponential number of variables and inequalities. An antichain is a set of pairwise incomparable elements with respect to the precedence constraints. In the first formulation, the integer variables are associated with the antichains. For the second, the integer variables are limited to a particular subset of antichains. We propose two Branch-and-Cut-and-Price algorithms for each of these formulations. We introduce some valid inequalities in order to reinforce the second formulation. Finally, we give some computational results on instances of the PSPLIB and compare the formulations.
Fouilhoux, Pierre 1 ; Mahjoub, A.Ridha 1 ; Quilliot, Alain 1 ; Toussaint, Hélène 1
@article{RO_2018__52_2_513_0,
author = {Fouilhoux, Pierre and Mahjoub, A.Ridha and Quilliot, Alain and Toussaint, H\'el\`ene},
title = {Branch-and-Cut-and-Price algorithms for the preemptive {RCPSP}},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {513--528},
publisher = {EDP-Sciences},
volume = {52},
number = {2},
year = {2018},
doi = {10.1051/ro/2018031},
mrnumber = {3880541},
zbl = {1398.90108},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.1051/ro/2018031/}
}
TY - JOUR AU - Fouilhoux, Pierre AU - Mahjoub, A.Ridha AU - Quilliot, Alain AU - Toussaint, Hélène TI - Branch-and-Cut-and-Price algorithms for the preemptive RCPSP JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2018 SP - 513 EP - 528 VL - 52 IS - 2 PB - EDP-Sciences UR - http://geodesic.mathdoc.fr/articles/10.1051/ro/2018031/ DO - 10.1051/ro/2018031 LA - en ID - RO_2018__52_2_513_0 ER -
%0 Journal Article %A Fouilhoux, Pierre %A Mahjoub, A.Ridha %A Quilliot, Alain %A Toussaint, Hélène %T Branch-and-Cut-and-Price algorithms for the preemptive RCPSP %J RAIRO - Operations Research - Recherche Opérationnelle %D 2018 %P 513-528 %V 52 %N 2 %I EDP-Sciences %U http://geodesic.mathdoc.fr/articles/10.1051/ro/2018031/ %R 10.1051/ro/2018031 %G en %F RO_2018__52_2_513_0
Fouilhoux, Pierre; Mahjoub, A.Ridha; Quilliot, Alain; Toussaint, Hélène. Branch-and-Cut-and-Price algorithms for the preemptive RCPSP. RAIRO - Operations Research - Recherche Opérationnelle, Tome 52 (2018) no. 2, pp. 513-528. doi: 10.1051/ro/2018031
Cité par Sources :