The Resource Constrained Project Scheduling Problem: A theoretical comparison between a recent formulation and the main time indexed linear programming based approaches
Bianco, Lucio1 ; Caramia, Massimiliano1
1 Dipartimento di Ingegneria dell’Impresa, Università di Roma “Tor Vergata”, Via del Politecnico, 1 - 00133 Roma, Italy.
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 = {https://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  - https://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 https://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. https://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

  • Sayah, David Continuous-time formulations for multi-mode project scheduling, Computers Operations Research, Volume 152 (2023), p. 106147 | DOI:10.1016/j.cor.2023.106147
  • Novikova, Tatyana; Evdokimova, Svetlana; Novikov, A. R D of the PERT basic model for project planning, Modeling of systems and processes, Volume 14 (2022) no. 4, p. 75 | DOI:10.12737/2219-0767-2021-14-4-75-81
  • Novikova, Tatyana; Evdokimova, Svetlana; Novikov, A. PERT method applicability to the project management process of the microelectronics design center, Modeling of systems and processes, Volume 15 (2022) no. 1, p. 77 | DOI:10.12737/2219-0767-2022-15-1-77-85
  • Song, Guopeng; Kis, Tamás; Leus, Roel Polyhedral Results and Branch-and-Cut for the Resource Loading Problem, INFORMS Journal on Computing, Volume 33 (2021) no. 1, p. 105 | DOI:10.1287/ijoc.2020.0957
  • Bianco, Lucio; Caramia, Massimiliano; Giordani, Stefano A chance constrained optimization approach for resource unconstrained project scheduling with uncertainty in activity execution intensity, Computers Industrial Engineering, Volume 128 (2019), p. 831 | DOI:10.1016/j.cie.2018.11.053
  • Riley, R. Christopher L.; Rego, Cesar Intensification, diversification, and learning via relaxation adaptive memory programming: a case study on resource constrained project scheduling, Journal of Heuristics, Volume 25 (2019) no. 4-5, p. 793 | DOI:10.1007/s10732-018-9368-y

Cité par 6 documents. Sources : Crossref