Computing Redundant Resources for the RCPSP

International audienceSeveral efficient lower bounds for the Resource Constrained Project Scheduling Problem (RCPSP) have been proposed recently. Some of them are based on the notion of redundant resource. In this paper we define a redundant function as an application f: [0, B] [0, B'] such that i 1 + i 2 + ...+i k B implies f(i 1 ) + f(i 2 ) +...+ f(i k ) B'. Then we explain that redundant functions are very useful for computing redundant resources. We also describe an algorithm for computing all maximal redundant functions. Computational results are reported