A preemptive bound for the Resource Constrained Project Scheduling Problem

作者：Haouari Mohamed; Kooli Anis^*; Neron Emmanuel; Carlier Jacques

来源：Journal of Scheduling, 2014, 17(3): 237-248.

DOI：10.1007/s10951-013-0354-9

• Resource constrained project scheduling problem
• Destructive lower bounds
• Preemptive relaxation
• Linear programming

The Resource Constrained Project Scheduling Problem is one of the most intensively investigated scheduling 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 -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 precedence constraints, incompatible activity subsets, and nonpreemption constraints. We present the results of an extensive computational study that was carried out on 2,040 benchmark instances of PSPLIB, with up to 120 activities, and that provide strong evidence that the new proposed lower bound exhibits an excellent performance. In particular, we report the improvement of the best known lower bounds of 5 instances.

• 出版日期2014-6