Geodesic
A branch-and-cut algorithm for a resource-constrained scheduling problem
RAIRO - Operations Research - Recherche Opérationnelle, Tome 41 (2007) no. 3, pp. 235-251

Voir la notice de l'article provenant de la source Numdam

This paper is devoted to the exact resolution of a strongly NP-hard resource-constrained scheduling problem, the Process Move Programming problem, which arises in relation to the operability of certain high-availability real-time distributed systems. Based on the study of the polytope defined as the convex hull of the incidence vectors of the admissible process move programs, we present a branch-and-cut algorithm along with extensive computational results demonstrating its practical relevance, in terms of both exact and approximate resolution when the instance size increases.

DOI : 10.1051/ro:2007021
Classification : 90C57, 68M14
Keywords: polyhedral combinatorics, scheduling, branch-and-cut, distributed systems 
@article{RO_2007__41_3_235_0,
     author = {Sirdey, Renaud and Kerivin, Herv\'e L. M.},
     title = {A branch-and-cut algorithm for a resource-constrained scheduling problem},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {235--251},
     publisher = {EDP-Sciences},
     volume = {41},
     number = {3},
     year = {2007},
     doi = {10.1051/ro:2007021},
     mrnumber = {2348000},
     zbl = {1213.90126},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1051/ro:2007021/}
}
TY  - JOUR
AU  - Sirdey, Renaud
AU  - Kerivin, Hervé L. M.
TI  - A branch-and-cut algorithm for a resource-constrained scheduling problem
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2007
SP  - 235
EP  - 251
VL  - 41
IS  - 3
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/articles/10.1051/ro:2007021/
DO  - 10.1051/ro:2007021
LA  - en
ID  - RO_2007__41_3_235_0
ER  - 
%0 Journal Article
%A Sirdey, Renaud
%A Kerivin, Hervé L. M.
%T A branch-and-cut algorithm for a resource-constrained scheduling problem
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2007
%P 235-251
%V 41
%N 3
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/articles/10.1051/ro:2007021/
%R 10.1051/ro:2007021
%G en
%F RO_2007__41_3_235_0
Sirdey, Renaud; Kerivin, Hervé L. M. A branch-and-cut algorithm for a resource-constrained scheduling problem. RAIRO - Operations Research - Recherche Opérationnelle, Tome 41 (2007) no. 3, pp. 235-251. doi: 10.1051/ro:2007021

Cité par Sources :