An iterative local constraint based analysis for solving the resource constrained project scheduling problem

Abstract

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.