A hybrid genetic and Lagrangian relaxation algorithm for resource-constrained project scheduling under nonrenewable resources

Abstract

Scheduling under nonrenewable resources is one of the challenging issues in project scheduling problems. There are many cases where the projects are subject to some nonrenewable resources. In most of the literature, nonrenewable resources are assumed to be available in full amount at the beginning of the project. However, in practice, it is prevalent that these resources are procured along the project horizon. This paper studies the generalized resource-constrained project scheduling problem (RCPSP) where, in addition to renewable resources, nonrenewable resources are considered, such as budget or consuming materials by the project activities. As the problem is NP-hard, some sub-algorithm elements are developed, which can be used in the structure of inexact approaches for solving the problem. These elements include constraint propagation, priority rules, schedule generation schemes, and local search improvement procedures. Also, a lower bounding algorithm is developed based on the Lagrangian Relaxation (LR) approach, and the problem is optimized by the Genetic Algorithm (GA). The hybrid GA–LR​ algorithm produces a result reasonably near to optimum solutions. Comprehensive computational experiments based on standard project scheduling problems are performed to evaluate these developments. The experiments showed the performance and robustness of the proposed algorithm.