A preemptive bound for the resource constrained project scheduling problem

International audienceThe Resource Constrained Project Scheduling Problem is one of the most intensively investigated schedul- ing problems. It requires scheduling a set of interrelated activities, while considering precedence relationships, and limited renewable resources allocation. The objective is to minimize the project duration. We propose a new destructive lower bound for this challenging NP -hard problem. Starting from a previously suggested LP model, we propose several original valid inequalities that aim at tightening the model representation. These new inequalities are based on prece- dence constraints, incompatible activity subsets, and nonpre- emption constraints. We present the results of an extensive computational study that was carried out on 2,040 bench- mark instances of PSPLIB , with up to 120 activities, and that provide strong evidence that the new proposed lower bound exhibitsanexcellentperformance.Inparticular,wereportthe improvement of the best known lower bounds of 5 instance