A Parallel Branch and Bound Algorithm for the Resource Leveling Problem with Minimal Lags

Abstract

The efficient use of resources is a key factor to minimize the cost while meeting time deadlines and quality requirements; this is especially important in construction projects where field operations make fluctuations of resources unproductive and costly. Resource Leveling Problems (RLP) aim to sequence the construction activities that maximize the resource consumption efficiency over time, minimizing the variability. Exact algorithms for the RLP have been proposed throughout the years to offer optimal solutions; however, these problems require a vast computational capability (“combinatorial explosion”) that makes them unpractical. Therefore, alternative heuristic and metaheuristic algorithms have been suggested in the literature to find local optimal solutions, using different libraries to benchmark optimal values; for example, the Project Scheduling Problem LIBrary for minimal lags is still open to be solved to optimality for RLP. To partially fill this gap, the authors propose a Parallel Branch and Bound algorithm for the RLP with minimal lags to solve the RLP with an acceptable computational effort. This way, this research contributes to the body of knowledge of construction project scheduling providing the optimums of 50 problems for the RLP with minimal lags for the first time, allowing future contributors to benchmark their heuristics methods against exact results by obtaining the distance of their solution to the optimal values. Furthermore, for practitioners, the time required to solve this kind of problem is reasonable and practical, considering that unbalanced resources can risk the goals of the construction project. © 2016 Computer-Aided Civil and Infrastructure Engineering