Geodesic
A fast algorithm for finding a lower bound of the solution of the Resource-Constrained Project Scheduling Problem tested on PSPLIB instances
Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 27 (2021) no. 1, pp. 22-36

Voir la notice de l'article provenant de la source Math-Net.Ru

We consider the intractable Resource-Constrained Project Scheduling Problem (RCPSP). It is assumed that the intensity functions of resource allocation and consumption are constant on specified time intervals and there are no deadlines. The procedure for calculating the lower bound for the RCPSP is constructed on the basis of the relaxation of the problem by replacing renewable resources with cumulative ones. The time complexity of this procedure depends on the number of activities $n$ as a function of $\mathcal O(n\log{n})$. From the analysis of numerical experiments (which are carried out on examples of problems from the electronic library PSPLIB), it follows that the proposed procedure is highly competitive, and in some series of instances gives results close to the best lower bounds published in the PSPLIB with dramatically small CPU time (milliseconds).
Keywords: project management, Resource-Constrained Project Scheduling Problem, renewable resources, cumulative resources, lower bound.
Mots-clés : PSPLIB 
@article{TIMM_2021_27_1_a2,
     author = {E. Kh. Gimadi and E. N. Goncharov and A. A. Shtepa},
     title = {A fast algorithm for finding a lower bound of the solution of the {Resource-Constrained} {Project} {Scheduling} {Problem} tested on {PSPLIB} instances},
     journal = {Trudy Instituta matematiki i mehaniki},
     pages = {22--36},
     publisher = {mathdoc},
     volume = {27},
     number = {1},
     year = {2021},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMM_2021_27_1_a2/}
}
TY  - JOUR
AU  - E. Kh. Gimadi
AU  - E. N. Goncharov
AU  - A. A. Shtepa
TI  - A fast algorithm for finding a lower bound of the solution of the Resource-Constrained Project Scheduling Problem tested on PSPLIB instances
JO  - Trudy Instituta matematiki i mehaniki
PY  - 2021
SP  - 22
EP  - 36
VL  - 27
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/TIMM_2021_27_1_a2/
LA  - ru
ID  - TIMM_2021_27_1_a2
ER  - 
%0 Journal Article
%A E. Kh. Gimadi
%A E. N. Goncharov
%A A. A. Shtepa
%T A fast algorithm for finding a lower bound of the solution of the Resource-Constrained Project Scheduling Problem tested on PSPLIB instances
%J Trudy Instituta matematiki i mehaniki
%D 2021
%P 22-36
%V 27
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/TIMM_2021_27_1_a2/
%G ru
%F TIMM_2021_27_1_a2
E. Kh. Gimadi; E. N. Goncharov; A. A. Shtepa. A fast algorithm for finding a lower bound of the solution of the Resource-Constrained Project Scheduling Problem tested on PSPLIB instances. Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 27 (2021) no. 1, pp. 22-36. http://geodesic.mathdoc.fr/item/TIMM_2021_27_1_a2/