Lower Bounds and Flat Graphs of Precedence Relations for the Resource-Constrained Project Scheduling Problem
We consider some special cases of the NP-hard resource-constrained projects cheduling problem (RCPSP) to minimize the makespan. We show that a well-known lowerbounds for the problem may yield bad approximation ratios or its calculation is an NP-hardproblem too. We conjecture that the ratio of the optimal makespan of RCPSP to that of the preemptive version of the problem is less than 2. We also provide some new estimates of the optimal makespan of RCPSP.