A preemptive bound for the Resource Constrained Project Scheduling Problem

A preemptive bound for the Resource Constrained Project Scheduling Problem

0.00 Avg rating0 Votes
Article ID: iaor2014732
Volume: 17
Issue: 3
Start Page Number: 237
End Page Number: 248
Publication Date: Jun 2014
Journal: Journal of Scheduling
Authors: , , ,
Keywords: project management, programming: linear
Abstract:

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 NP equ1 ‐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.

Reviews

Required fields are marked *. Your email address will not be published.