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.
Mots clés : Resource-constrained precedence scheduling problem, Preemptive case, Antichain, Branch-and-Cut-and-Price algorithm
@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://www.numdam.org/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://www.numdam.org/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://www.numdam.org/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. http://www.numdam.org/articles/10.1051/ro/2018031/
[1] and The project scheduling polyhedron: dimension, facets, and lifting theorems. Eur. J. Oper. Res. 67 (1993) 204–220 | DOI | Zbl
[2] and Tight LP bounds for resource constrained project scheduling. OR Spectrum 26 (2004) 251–262 | DOI | Zbl
[3] , , , and Resource-constrained project scheduling: notation, classification, model, and methods. Eur. J. Oper. Res. 112 (1999) 3–41. | DOI | Zbl
[4] and A linear programming and constraint propagation-based lower bound for the rcpsp. Eur. J. Oper. Res. 127 (2000) 355–362. | DOI | Zbl
[5] , and Linear programming based algorithms for preemptive and non-preemptive rcpsp. Eur. J. Oper. Res. 182 (2007) 1012–1022. | DOI | Zbl
[6] and , Computers and Intractability: a Guide to the Theory of NP-Completeness, edited by (1979). | MR | Zbl
[7] and Exact solution of graph coloring problems via constraint programming and column generation. INFORMS J. Comput. 24 (2011) 1–20.
[8] , and Set covering and packing formulations of graph coloring: Algorithms and first polyhedral results. Discret. Optim. 6 (2009) 135–147. | DOI | MR | Zbl
[9] , and , Strong valid inequalities for the resource-constrained scheduling problem with uniform resource requirements. Discret. Optim. 5 (2008) 19–35. | DOI | MR | Zbl
[10] , and , An integrated classification scheme for resource scheduling. Technical report, Department of applied economics K.U.Leuven, (1999).
[11] , Scheduling of Resource Constraints Projects. Kluwer Academic Publishers, Boston (1999). | MR | Zbl
[12] and , http://www.om-db.wi.tum.de/psplib/.
[13] , and , An exact approach for the vertex coloring problem. Discret. Optim. 8 (2010) 174–190 | DOI | MR | Zbl
[14] and , A column generation approach for graph coloring. INFORMS J. Comput. 8 (1996) 344–354. | DOI | Zbl
[15] , , and , An exact algorithm for the resource-constrained project scheduling based on a new mathematical formulation. Manag. Sci. 44 (1998) 714–729. | DOI | Zbl
[16] , and , Branch and price for preemptive resource constrained project scheduling problem based on interval orders in precedence graphs, in 6th Workshop on Computational Optimization, Kraków, Poland (2013).
[17] and , A horizon-varying, zero-one approach to project scheduling problem. Manag. Sci. 20 (1974) 990–998. | DOI | Zbl
[18] and , Scheduling a project under multiple resource constraints: a zero-one programming approach. AIIE Trans. 8 (1976) 449–455. | DOI
[19] , and , Multi-project scheduling with limited resources: a zero-one programming approach. Manag. Sci. 16 (1969) 93–108. | DOI
Cité par Sources :
