Estimation of Absolute Error for the Resources-Constrained Project Scheduling Problem
We consider some special cases of the NP-hard resource-constrained projectscheduling problem (RCPSP) to minimize the makespan. We conjecture that the ratioof the optimal makespan of RCPSP to that of the preemptive version of the problemis less than 2. We show that a well-known lower bounds for the problem may yield badapproximation ratios or its calculation is an NP-hard problem too. We also providesome new estimates of the optimal makespan of RCPSP.