An effective heuristic for project scheduling with resource availability cost

The resource constrained project scheduling problem (RCPSP) is widely studied in the literature and has a host of applications in practice. As a variant of the RCPSP, the resource availability cost problem (RACP), which has the aim of minimizing the availability costs of renewable resources in order to complete a project subject to a given deadline, is considered in this paper. We divide the RACP into two sub-problems: the sequencing problem and the resource decision problem, and propose a multi-start iterative search heuristic (MSIS) to solve it. For the sequencing problem, an iterative search framework is constructed to effectively search the activity sequences. A two stage resource adjustment procedure and a backward peak elimination procedure is developed for solving the resource decision problem. MSIS is compared with three existing algorithms on both PSPLib and RanGen data sets involving 1380 instances. A complete calibration of the different parameters and operators of MSIS by means of a design of experiments approach is given. Experimental and statistical results show that MSIS outperforms the other three algorithms in both effectiveness and efficiency by a significant margin.