Premium
An iterative local constraints based analysis for solving the resource constrained project scheduling problem
Author(s) -
Özdamar Linet,
Ulusoy Gündüz
Publication year - 1996
Publication title -
journal of operations management
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 3.649
H-Index - 191
eISSN - 1873-1317
pISSN - 0272-6963
DOI - 10.1016/0272-6963(95)00015-1
Subject(s) - computer science , mathematical optimization , dynamic priority scheduling , fair share scheduling , scheduling (production processes) , rate monotonic scheduling , flow shop scheduling , iterative and incremental development , genetic algorithm scheduling , iterative method , schedule , algorithm , mathematics , software engineering , operating system
In this paper, a new heuristic iterative scheduling approach is proposed for the resource constrained project scheduling problem. Well‐known dispatching rules and a decision‐making process called Local Constraint Based Analysis (LCBA), previously tested in a single pass forward parallel scheduling algorithm, are imbedded in the iterative scheduling algorithm. LCBA evaluates and selects the activities competing for scarce resources by considering the currently active temporal and resource constraints imposed by the network/resource characteristics. The iterative scheduling algorithm proposed here makes consecutive forward/backward scheduling passes which improve the project duration obtained by the single forward scheduling pass. Extensive experimentation has been done on a set of 188 benchmark problems from the literature. The results demonstrate that all the methods imbedded in the iterative algorithm improved the project duration significantly. It is observed that LCBA's average project duration deviation from the optimal duration is of the magnitude of 1% using the iterative scheduling algorithm. Among all the methods which have been tested, LCBA and a list rule, Weighted Resource Utilization and Precedence (WRUP), are the ones which have benefited most from the iterative algorithm. It is also observed that for various cash flow schemes the project Net Present Value (NPV) is improved through the use of the iterative scheduling algorithm.