Geodesic
Local search algorithm for~the~resource-constrained project~scheduling~problem
Diskretnyj analiz i issledovanie operacij, Tome 29 (2022) no. 4, pp. 15-37

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

We consider the resource-constrained project scheduling problem (RCPSP). The problem accounts for technological constraints of activities precedence together with resource constraints. All resources are renewable. Activities preemptions are not allowed. This problem is NP-hard in the strong sense. We present a new local search algorithm that uses a Tabu-list and two type of neighborhoods. The algorithm is evaluated using three data bases of instances of the problem: 480 instances of 60 activities, 480 of 90, and 600 of 120 activities respectively, taken from the PSPLIB library available online. Numerical experiments demonstrate that the proposed algorithm produces better results than existing algorithms in the literature for large-sized instances. For some instances from the dataset j120, the best known heuristic solutions were improved. Tab. 4, bibliogr. 47.
Keywords: resource-constrained project scheduling problem, renewable resources, Tabu search, variable neighborhood search
Mots-clés : PSPLIB. 
@article{DA_2022_29_4_a1,
     author = {E. N. Goncharov},
     title = {Local search algorithm for~the~resource-constrained project~scheduling~problem},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {15--37},
     publisher = {mathdoc},
     volume = {29},
     number = {4},
     year = {2022},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2022_29_4_a1/}
}
TY  - JOUR
AU  - E. N. Goncharov
TI  - Local search algorithm for~the~resource-constrained project~scheduling~problem
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2022
SP  - 15
EP  - 37
VL  - 29
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2022_29_4_a1/
LA  - ru
ID  - DA_2022_29_4_a1
ER  - 
%0 Journal Article
%A E. N. Goncharov
%T Local search algorithm for~the~resource-constrained project~scheduling~problem
%J Diskretnyj analiz i issledovanie operacij
%D 2022
%P 15-37
%V 29
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2022_29_4_a1/
%G ru
%F DA_2022_29_4_a1
E. N. Goncharov. Local search algorithm for~the~resource-constrained project~scheduling~problem. Diskretnyj analiz i issledovanie operacij, Tome 29 (2022) no. 4, pp. 15-37. http://geodesic.mathdoc.fr/item/DA_2022_29_4_a1/