Why Is the RCPSP So Difficult? (Part 1)

Despite the fact that it is generally known that the resource-constrained project scheduling problem is NP-hard, it is often still unclear why some algorithms can find an optimal solution for one project while seemingly impossible for another. As computers become more powerful, researchers frequently test their algorithms on increasingly larger projects, which are inherently more complex, without gaining much insight into why projects become more challenging to solve. In a quest to uncover the core difficulty for each project, this chapter sequentially manipulates and modifies a set of existing projects, making them not only smaller but also significantly more complex. Researchers are provided with a new set of projects, referred to as the CV set, containing 623 projects with a maximum of 30 activities, claimed to be highly challenging to solve. The goal is to encourage researchers to develop scheduling algorithms that work in innovative ways, propelling academic research in this challenging domain forward. This chapter is based on the article “Going to the core of hard resource-constrained project scheduling instances,” published in Computers and Operations Research.