A Greedy Algorithm for the Resource-Constrained ProjectScheduling Problem

The resource-constrained project scheduling problem (briefly RCPSP) is a general scheduling problem that includes precedence and resource constraints. Activities preemptions are not allowed. Resources are renewable and there is a unique way to perform the activities. The problem with renewable resources is NP-hard in the strong sense. We propose a new deterministic greedy algorithm. It is based on heuristics that use information obtained from a relaxing problem. The algorithm is tested with standard data sets given by Kolisch library PSPLIB for j60, j90, and j120 and found to be performing well.