Voir la notice de l'article provenant de la source Numdam
We deal here with a scheduling problem GPPCSP (Generalized Parallelism and Preemption Constrained Scheduling Problem) which is an extension of both the well-known Resource Constrained Scheduling Problem and the Scheduling Problem with Disjunctive Constraints. We first propose a reformulation of GPPCSP: according to it, solving GPPCSP means finding a vertex of the Feasible Vertex Subset of an Antichain Polyhedron. Next, we state several theoretical results related to this reformulation process and to structural properties of this specific Feasible Vertex Subset (connectivity, ...). We end by focusing on the preemptive case of GPPCSP and by identifying specific instances of GPPCSP which are such that any vertex of the related Antichain Polyhedron may be projected on its related Feasible Vertex Subset without any deterioration of the makespan. For such an instance, the GPPCSP problem may be solved in a simple way through linear programming.
@article{RO_2008__42_3_325_0,
author = {Damay, Jean and Quilliot, Alain and Sanlaville, Eric},
title = {Polyhedral reformulation of a scheduling problem and related theoretical results},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {325--359},
publisher = {EDP-Sciences},
volume = {42},
number = {3},
year = {2008},
doi = {10.1051/ro:2008024},
mrnumber = {2444491},
zbl = {1152.90437},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.1051/ro:2008024/}
}
TY - JOUR AU - Damay, Jean AU - Quilliot, Alain AU - Sanlaville, Eric TI - Polyhedral reformulation of a scheduling problem and related theoretical results JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2008 SP - 325 EP - 359 VL - 42 IS - 3 PB - EDP-Sciences UR - http://geodesic.mathdoc.fr/articles/10.1051/ro:2008024/ DO - 10.1051/ro:2008024 LA - en ID - RO_2008__42_3_325_0 ER -
%0 Journal Article %A Damay, Jean %A Quilliot, Alain %A Sanlaville, Eric %T Polyhedral reformulation of a scheduling problem and related theoretical results %J RAIRO - Operations Research - Recherche Opérationnelle %D 2008 %P 325-359 %V 42 %N 3 %I EDP-Sciences %U http://geodesic.mathdoc.fr/articles/10.1051/ro:2008024/ %R 10.1051/ro:2008024 %G en %F RO_2008__42_3_325_0
Damay, Jean; Quilliot, Alain; Sanlaville, Eric. Polyhedral reformulation of a scheduling problem and related theoretical results. RAIRO - Operations Research - Recherche Opérationnelle, Tome 42 (2008) no. 3, pp. 325-359. doi: 10.1051/ro:2008024
Cité par Sources :