A fast algorithm for finding a lower bound of the solution of the Resource-Constrained Project Scheduling Problem tested on PSPLIB instances

We consider the intractable Resource-Constrained Project Scheduling Problem (RCPSP). It is assumed that the intensity functions of resource allocation and consumption are constant on specified time intervals and there are no deadlines. The procedure for calculating the lower bound for the RCPSP is constructed on the basis of the relaxation of the problem by replacing renewable resources with cumulative ones. The time complexity of this procedure depends on the number of activities $n$ as a function of $\mathcal O(n\log{n})$. From the analysis of numerical experiments (which are carried out on examples of problems from the electronic library PSPLIB), it follows that the proposed procedure is highly competitive, and in some series of instances gives results close to the best lower bounds published in the PSPLIB with dramatically small CPU time (milliseconds).