Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6896580 | European Journal of Operational Research | 2015 | 24 Pages |
Abstract
In this paper we address the Preemptive Resource Constrained Project Scheduling Problem (PRCPSP). PRCPSP requires a partially ordered set of activities to be scheduled using limited renewable resources such that any activity can be interrupted and later resumed without penalty. The objective is to minimize the project duration. This paper proposes an effective branch-and-price algorithm for solving PRCPSP based upon minimal Interval Order Enumeration involving column generation as well as constraint propagation. Experiments conducted on various types of instances have given very satisfactory results. Our algorithm is able to solve to optimality the entire set of J30, BL and Pack instances while satisfying the preemptive requirement. Furthermore, this algorithm provides improved best-known lower bounds for some of the J60, J90 and J120 instances in the non-preemptive case (RCPSP).
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Aziz Moukrim, Alain Quilliot, Hélène Toussaint,