Why Is the RCPSP So Difficult? (Part 2)

Due to the complexity of the resource-constrained project scheduling problem, researchers have increasingly turned to meta-heuristic scheduling algorithms over the past decades, rather than relying solely on exact methods. These meta-heuristics offer the advantage of not systematically exploring the vast solution space, as exact methods do. Instead, they use a structured process to search for near-optimal solutions. Despite containing random components, meta-heuristics are designed to find these near-optimal solutions more efficiently compared to a pure random search. In this chapter, a quest begins to quantify a project’s complexity based on this concept of randomness. The extent to which a random search deviates from solutions obtained by a robust meta-heuristic is examined. The difference between the pure random schedules and the near-optimal schedules is measured using the sigma distance metric. Additionally, a new dataset of 390 projects is introduced, each with varying values for this metric, covering a range from very easy to highly challenging projects for meta-heuristic solution approaches. This chapter is based on the article “New resource-constrained project scheduling instances for testing (meta-)heuristic scheduling algorithms,” published in Computers and Operations Research.