Can We Make the Projects Easier? (Part 1)

It is widely known that the values of various resource indicators can be used to predict whether a specific project is easy or difficult to solve for the resource-constrained project scheduling problem. These resource indicators exhibit the so-called phase transitions, where certain threshold values demonstrate a sudden change in complexity from easy to difficult (or vice versa). However, this chapter challenges these phase transitions by showing that these threshold values are not entirely reliable. A newly developed algorithm modifies projects in such a way that the entire set of possible solutions for each project remains unchanged, maintaining the same complexity, while significantly altering the values of the resource indicators. With an unaltered solution space but new resource indicator values, multiple versions of each project now exist, making it less clear what the phase transitions are for a given project. The chapter aims to identify the most reliable resource indicator value to predict this unaltered complexity, sharpening our understanding of phase transitions. This chapter is based on the article “An analysis of network and resource indicators for resource-constrained project scheduling problem instances,” published in Computers and Operations Research.