This article is cited in 1 scientific paper (total in 1 paper)
A stochastic greedy algorithm for the resource-constrained project scheduling problem
E. N. Goncharov
S. L. Sobolev Institute of Mathematics, SB RAS, 4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia
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 . 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.
resource constrained project scheduling problem, limited resource, renewable resource, heuristic algorithm.
PDF file (276 kB)
E. N. Goncharov, “A stochastic greedy algorithm for the resource-constrained project scheduling problem”, Diskretn. Anal. Issled. Oper., 21:3 (2014), 11–24
Citation in format AMSBIB
\paper A stochastic greedy algorithm for the resource-constrained project scheduling problem
\jour Diskretn. Anal. Issled. Oper.
Citing articles on Google Scholar:
Related articles on Google Scholar:
This publication is cited in the following articles:
E. N. Goncharov, V. V. Leonov, “Genetic algorithm for the resource-constrained project scheduling problem”, Autom. Remote Control, 78:6 (2017), 1101–1114
|Number of views:|