An effective heuristic for project scheduling with resource availability cost

作者：Zhu, Xia; Ruiz, Ruben; Li, Shiyu; Li, Xiaoping^*

来源：European Journal of Operational Research, 2017, 257(3): 746-762.

DOI：10.1016/j.ejor.2016.08.049

• Project scheduling
• Heuristic
• 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.

• 出版日期2017-3-16
• 单位东南大学