Geodesic
A stochastic greedy algorithm for the resource-constrained project scheduling problem
Diskretnyj analiz i issledovanie operacij, Tome 21 (2014) no. 3, pp. 11-24

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

We consider the resource constrained project scheduling problem (RCPSP) with precedence and resource constraints. All resources are renewable and the objective is to find a schedule that meets all resource and precedence constraints and minimizes the makespan. We propose a fast stochastic algorithm developed by the greedy algorithm based on deterministic solutions to this problem with the low-time complexity. Quality of this algorithm has been analyzed in a number of computational experiments with the standard sets J60 and J120 for the RCPSP from the PSPLIB [23]. The proposed algorithm takes some of the best positions among greedy algorithms and showed the best result on the set J60 from PSPLIB with the limit of schedules 50000. It is competitive among all the algorithms being second only to genetic algorithms and to combined ones based on them. Ill. 1, tab. 4, bibliogr. 33.
Keywords: resource constrained project scheduling problem, limited resource, renewable resource
Mots-clés : heuristic algorithm. 
@article{DA_2014_21_3_a2,
     author = {E. N. Goncharov},
     title = {A stochastic greedy algorithm for the resource-constrained project scheduling problem},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {11--24},
     publisher = {mathdoc},
     volume = {21},
     number = {3},
     year = {2014},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2014_21_3_a2/}
}
TY  - JOUR
AU  - E. N. Goncharov
TI  - A stochastic greedy algorithm for the resource-constrained project scheduling problem
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2014
SP  - 11
EP  - 24
VL  - 21
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2014_21_3_a2/
LA  - ru
ID  - DA_2014_21_3_a2
ER  - 
%0 Journal Article
%A E. N. Goncharov
%T A stochastic greedy algorithm for the resource-constrained project scheduling problem
%J Diskretnyj analiz i issledovanie operacij
%D 2014
%P 11-24
%V 21
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2014_21_3_a2/
%G ru
%F DA_2014_21_3_a2
E. N. Goncharov. A stochastic greedy algorithm for the resource-constrained project scheduling problem. Diskretnyj analiz i issledovanie operacij, Tome 21 (2014) no. 3, pp. 11-24. http://geodesic.mathdoc.fr/item/DA_2014_21_3_a2/