A Branch and Bound Algorithm for a Multi-Mode Project Scheduling Problem With a Single Non-Renewable Resource

Introduction

Project scheduling is an important step of project management that defines the timings of and resource allocations to the project activities. Critical path method (CPM) finds the minimum project completion time schedule in polynomial time under the presence of unlimited resources. However, since unlimited resources are unrealistic, previous studies mostly considered resource allocations. Slowinski (1980) categorizes basic resource types as renewable, non-renewable and doubly-constrained. Renewable resources have three characteristics: (i) they are temporarily available for distinct time periods, (ii) they can be allocated to activities at time of availability, and (iii) they can be re-used after the completion of these activities. Among the examples of renewable resources are labor and machine. Non-renewable resources are accumulated over the entire project and consumed with usage. Non-renewable resources could be the budget of the project or any type of physical inventory used through the execution of the project. Doubly-constrained resources are constrained both on usage and total consumption such as the project budget with a limit on cash flows per period.

This research draws upon work in both the discrete time/cost trade-off problems (DTCTP) and the multi-mode resource-constrained project scheduling (MRCPS) problems. DTCTP have discrete activity durations which are non-increasing function of a single non-renewable resource. One variant of the DTCTP is the deadline problem that minimizes the total resource cost subject to a specified deadline on the project completion time. Demeulemeester et al. (1998) present an exact branch and bound procedure to solve the deadline problem. Akkan et al. (2005) use column generation techniques based on network decomposition and develop upper and lower bounds. Hafizoglu and Azizoglu (2010) propose optimization and approximation algorithms that are based on the optimal linear programming relaxation solutions. The budget problem, another variant of the DTCTP, assumes a limited resource that is released at the beginning of the project as a lump sum. The budget problem minimizes the project completion time and is shown to be strongly NP-hard by De et al. (1997). Hazir et al. (2010) propose a Benders Decomposition-based exact algorithm. Degirmenci and Azizoglu (2013) present branch and bound based optimization and heuristic algorithms. Skutella (1998), Ranjbar and Kianfar (2007), Ranjbar et al. (2009) propose heuristic solutions. De et al. (1995) and Vanhoucke and Debels (2007) review the DTCTP and discuss their potential extensions.

In the presence of the resource constraints, the problems are referred to as the resource constrained project scheduling (RCPS) problems. Demeulemeester and Herroelen (1992), Brucker et al. (1998) and Mingozzi et al. (1998) present exact algorithms for the RCPS problems under the presence of renewable resources. Carlier and Rinnooy Kan (1982) present a polynomial time algorithm that finds the optimal solution with a single non-renewable resource and progressive resource arrivals. Sepil and Ortac (1997) propose three different heuristic rules for a RCPS problem variant with the objective of maximization of the net present value (NPV) of the cash flows associated with the project. Review studies of the RCPS problems with their variants and extensions are by Herroelen et al. (1998), Kolisch and Padman (2001), Hartmann and Briskorn (2010). Herroelen and Leus (2005) provide a comprehensive review of the RCPS problem under uncertainty.