Branch-and-Cut-and-Price algorithms for the preemptive RCPSP
RAIRO - Operations Research - Recherche Opérationnelle, Tome 52 (2018) no. 2, pp. 513-528.

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.

DOI : 10.1051/ro/2018031
Classification : 90C11, 90C27, 90C08, 90C90
Mots-clés : Resource-constrained precedence scheduling problem, Preemptive case, Antichain, Branch-and-Cut-and-Price algorithm
Fouilhoux, Pierre 1 ; Mahjoub, A.Ridha 1 ; Quilliot, Alain 1 ; Toussaint, Hélène 1

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://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] R. Alvarez-Valdés and J.M. Tamarit Goerlich. The project scheduling polyhedron: dimension, facets, and lifting theorems. Eur. J. Oper. Res. 67 (1993) 204–220 | DOI | Zbl

[2] P. Baptiste and S. Demassey. Tight LP bounds for resource constrained project scheduling. OR Spectrum 26 (2004) 251–262 | DOI | Zbl

[3] P. Brucker, A. Drexl, R. Möhring, K. Neumann and E. Pesch. Resource-constrained project scheduling: notation, classification, model, and methods. Eur. J. Oper. Res. 112 (1999) 3–41. | DOI | Zbl

[4] P. Brucker and S. Knust. A linear programming and constraint propagation-based lower bound for the rcpsp. Eur. J. Oper. Res. 127 (2000) 355–362. | DOI | Zbl

[5] J. Damay, A. Quilliot and E. Sanlaville. Linear programming based algorithms for preemptive and non-preemptive rcpsp. Eur. J. Oper. Res. 182 (2007) 1012–1022. | DOI | Zbl

[6] M.R. Garey and D.S. Johnson, Computers and Intractability: a Guide to the Theory of NP-Completeness, edited by W.H. Freeman (1979). | MR | Zbl

[7] S. Gualandi and F. Malucelli. Exact solution of graph coloring problems via constraint programming and column generation. INFORMS J. Comput. 24 (2011) 1–20.

[8] P. Hansen, M. Labbé and D. Schindl. Set covering and packing formulations of graph coloring: Algorithms and first polyhedral results. Discret. Optim. 6 (2009) 135–147. | DOI | MR | Zbl

[9] J.R. Hardin, G.L. Nemhauser and M.W.P. Savelsbergh, Strong valid inequalities for the resource-constrained scheduling problem with uniform resource requirements. Discret. Optim. 5 (2008) 19–35. | DOI | MR | Zbl

[10] W. Herroelen, E. Demeulemeester and B. De Reyck, An integrated classification scheme for resource scheduling. Technical report, Department of applied economics K.U.Leuven, (1999).

[11] R. Klein, Scheduling of Resource Constraints Projects. Kluwer Academic Publishers, Boston (1999). | MR | Zbl

[12] R. Kolish and A. Sprecher, http://www.om-db.wi.tum.de/psplib/.

[13] E. Malaguti, M. Monaci and P. Toth, An exact approach for the vertex coloring problem. Discret. Optim. 8 (2010) 174–190 | DOI | MR | Zbl

[14] A. Mehrotra and M. Trick, A column generation approach for graph coloring. INFORMS J. Comput. 8 (1996) 344–354. | DOI | Zbl

[15] A. Mingozzi, V. Maniezzo, S. Ricciardelli and L. Bianco, An exact algorithm for the resource-constrained project scheduling based on a new mathematical formulation. Manag. Sci. 44 (1998) 714–729. | DOI | Zbl

[16] A. Moukrim, A. Quilliot and H. Toussaint, 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] J.H. Patterson and W.D. Huber, A horizon-varying, zero-one approach to project scheduling problem. Manag. Sci. 20 (1974) 990–998. | DOI | Zbl

[18] J.H. Patterson and G.W. Roth, Scheduling a project under multiple resource constraints: a zero-one programming approach. AIIE Trans. 8 (1976) 449–455. | DOI

[19] A.A. Pritsker, L.J. Watters and P.M. Wolfe, Multi-project scheduling with limited resources: a zero-one programming approach. Manag. Sci. 16 (1969) 93–108. | DOI

Cité par Sources :