Multi-Mode Resource-Constrained Project-Scheduling Problem With Renewable Resources: New Solution Approaches

Abstract

We consider the multi-mode resource-constrained project scheduling problem (MRCPSP) with renewable resources.  In MRCPSP, an activity can be executed in one of many possible modes; each mode having different resource requirements and accordingly different activity durations.  We assume that all resources are renewable from period to period, such as labor and machines.  A solution to this problem basically involves two decisions – (i) The start time for each activity and (ii) the mode for each activity.  Given the NP-Hard nature of the problem, heuristics and metaheuristics are used to solve larger instances of this problem.  A heuristic for this type of problem involves a combination of two priority rules - one for each of the two decisions.  Heuristics generally tend to be greedy in nature.  In this study we propose two non-greedy heuristics for mode selection which perform better than greedy heuristics.  In addition, we study the effect of double justification and backward/forward scheduling for the MRCPS.  We also study the effect of serial vs. parallel scheduling.  We found that all these elements improved the solution quality.  Finally we propose an adaptive metaheuristic procedure based on neural networks which further improves the solution quality.  The effectiveness of these proposed approaches, compared to existing approaches in the literature, is demonstrated through empirical testing on two well-known sets of benchmark problems.