A modified modeling approach and a heuristic procedure for the multi-mode resource constrained project scheduling problem with activity splitting

Department of Industrial Engineering, Amirkabir University of Technology, Hafiz St. 424, P.O. Box 15875-4413, Tehran, Iran.
torinofm@yahoo.com; aseifi@aut.ac.ir; mks63@aut.ac.ir

Received: 23 April 2014
Accepted: 17 April 2015

Abstract

This paper presents a new heuristic method for solving multi-mode resource constrained project scheduling problems with renewable resources. Assumptions such as resource vacation and activity splitting are also considered. The proposed heuristic determines one mode for the execution of each activity first, so that the multi-mode problem is reduced to a single-mode one. Our method is compared to two of the existing methods in terms of computational time and solution quality. The results show that while it can outperform one of them (especially as the size of the problem grows), it is outperformed by the other for tested instances with low complexity, but can yield good results for tested instances with higher values of this parameters. This quality may be useful in real-world scheduling problems. We also validate the first phase of our method, i.e., mode selection, with numerical experiments. Our results indicate that better mode vectors selected in the first phase lead to better makespans for the MRCPSP. Moreover, we correct some erroneous constraints in the mathematical model of the problem. We implement the mathematical programming model of the problem in GAMS, and show that solving it to optimality requires much more computational effort compared to our method.