Pre-emption in resource-constrained project scheduling

The Resource-Constrained Project Scheduling Project (RCPSP), together with some of its extensions, has been widely studied. A fundamental assumption in this basic problem is that activities in progress are non-preemptable. Very little effort has been made to uncover the potential benefits of discret...

Full description

Saved in:
Bibliographic Details
Published in:European journal of operational research 2008-09, Vol.189 (3), p.1136-1152
Main Authors: Ballestín, Francisco, Valls, Vicente, Quintanilla, Sacramento
Format: Article
Language:English
Subjects:
Algorithms
Double justification
Heuristic
Heuristic algorithms
Pre-emption
Project management
Resource constrained project scheduling
Serial SGS
Studies
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The Resource-Constrained Project Scheduling Project (RCPSP), together with some of its extensions, has been widely studied. A fundamental assumption in this basic problem is that activities in progress are non-preemptable. Very little effort has been made to uncover the potential benefits of discrete activity pre-emption, and the papers dealing with this issue have reached the conclusion that it has little effect on project length when constant resource availability levels are defined. In this paper we show how three basic elements of many heuristics for the RCPSP – codification, serial SGS and double justification – can be adapted to deal with interruption. The paper is mainly focussed on problem 1_PRCPSP, a generalization of the RCPSP where a maximum of one interruption per activity is allowed. However, it is also shown how these three elements can be further adapted to deal with more general pre-emptive problems. Computational experiments on the standard j30 and j120 sets support the conclusion that pre-emption does help to decrease project length when compared to the no-interruption case. They also prove the usefulness of the justification in the presence of pre-emption. The justification is a RCPS technique that can be easily incorporated into a wide range of algorithms for the RCPSP, increasing their solution quality – maintaining the number of schedules calculated.
ISSN:0377-2217
1872-6860
DOI:10.1016/j.ejor.2006.07.052