The Resource Constrained Project Scheduling Problem: A theoretical comparison between a recent formulation and the main time indexed linear programming based approaches
RAIRO - Operations Research - Recherche Opérationnelle, Tome 51 (2017) no. 3, pp. 519-532.

We compare, at a theoretical level, the RCPSP formulation proposed in [L. Bianco and M. Caramia, Flexible Services and Manufacturing 25 (2013) 6–24.] with the main time indexed linear programming based mathematical models existing in the literature. This paper was inspired by the results of the experimental comparison among these models conducted in our previous work; in fact, such results showed that the formulation proposed by Bianco and Caramia bested the competing approaches. Here, by means of a theoretical analysis, we show the reason for this behaviour.

Reçu le :
Accepté le :
DOI : 10.1051/ro/2016036
Classification : 90C11, 90B35, 90C90
Mots-clés : Project scheduling, resource constraints, precedence constraints, mathematical model
Bianco, Lucio 1 ; Caramia, Massimiliano 1

1 Dipartimento di Ingegneria dell’Impresa, Università di Roma “Tor Vergata”, Via del Politecnico, 1 - 00133 Roma, Italy.
@article{RO_2017__51_3_519_0,
     author = {Bianco, Lucio and Caramia, Massimiliano},
     title = {The {Resource} {Constrained} {Project} {Scheduling} {Problem:} {A} theoretical comparison between a recent formulation and the main time indexed linear programming based approaches},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {519--532},
     publisher = {EDP-Sciences},
     volume = {51},
     number = {3},
     year = {2017},
     doi = {10.1051/ro/2016036},
     mrnumber = {3661367},
     zbl = {1384.90064},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ro/2016036/}
}
TY  - JOUR
AU  - Bianco, Lucio
AU  - Caramia, Massimiliano
TI  - The Resource Constrained Project Scheduling Problem: A theoretical comparison between a recent formulation and the main time indexed linear programming based approaches
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2017
SP  - 519
EP  - 532
VL  - 51
IS  - 3
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ro/2016036/
DO  - 10.1051/ro/2016036
LA  - en
ID  - RO_2017__51_3_519_0
ER  - 
%0 Journal Article
%A Bianco, Lucio
%A Caramia, Massimiliano
%T The Resource Constrained Project Scheduling Problem: A theoretical comparison between a recent formulation and the main time indexed linear programming based approaches
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2017
%P 519-532
%V 51
%N 3
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ro/2016036/
%R 10.1051/ro/2016036
%G en
%F RO_2017__51_3_519_0
Bianco, Lucio; Caramia, Massimiliano. The Resource Constrained Project Scheduling Problem: A theoretical comparison between a recent formulation and the main time indexed linear programming based approaches. RAIRO - Operations Research - Recherche Opérationnelle, Tome 51 (2017) no. 3, pp. 519-532. doi : 10.1051/ro/2016036. http://www.numdam.org/articles/10.1051/ro/2016036/

R. Alvarez-Valdes and J.M. Tamarit, Project Scheduling Polyhedron: Dimension, Facets and Lifting Theorems. Eur. J. Oper. Res. 67 (1993) 204–220. | DOI | Zbl

L. Bianco and M. Caramia, A new formulation for the Project Scheduling problem under limited resources. Flex. Serv. Manuf. 25 (2013) 6–24. | DOI

J. Blazewicz, J.K. Lenstra and A.H.G. Rinnooy Kan, Scheduling subject to resource constraints: Classification and complexity. Discrete Appl. Math. 5 (1983) 11–24. | DOI | MR | Zbl

J.E. Kelley, The critical path method: Resource planning and scheduling. Industrial Scheduling, edited by J.F. Muth and G.L. Thompson. Prentice Hall, N.J. (1963) 347–365.

R. Klein, Scheduling of resource-constrained projects. Kluwer Academic Publisher, Amsterdam (2000). | MR | Zbl

A. Mingozzi, V. Maniezzo, S. Ricciardelli and L. Bianco, An Exact Algorithm for the Resource-Constrained Project Scheduling Problem Based on a New Mathematical Formulation. Manage. Sci. 44 (1997) 714–729. | DOI | Zbl

J.J. Moder, C.R. Philips and E.W. Davis, Project management with CPM, PERT and precedence diagramming. Van Nostrand Reinhold Company, 3rd edition (1983).

A.A.B. Pritsker, W.D. Watters and P.M. Wolfe, Multiproject Scheduling with Limited Resources: A Zero-One Programming Approach. Manage. Sci. 16 (1969) 93–108. | DOI

F.J. Radermacher, Scheduling of project networks. Ann. Oper. Res. 4 (1985) 227–252. | DOI | MR | Zbl

Cité par Sources :