A stochastic greedy algorithm for the resource-constrained project scheduling problem

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.