Phase transitions in project scheduling

The analysis of the complexity of combinatorial optimization problems has led to the distinction between problems which are solvable in a polynomially bounded amount of time (classified in P) and problems which are not (classified in NP). This implies that the problems in NP are hard to solve whereas the problems in P are not. However, this analysis is based on worst-case scenarios. The fact that a decision problem is shown to be NP-complete or the fact that an optimization problem is shown to be NP-hard implies that, in the worst case, solving it is very hard. Recent computational results obtained with a well known NP-hard problem, namely the resource-constrained project scheduling problem, indicate that many instances are actually easy to solve. These results are in line with those recently obtained by researchers in the area of artificial intelligence, which show that many NP-complete problemsexhibit so-called phase transitions, resulting in a sudden and dramatic change of computational complexity based on one or more order parameters that are characteristic of the system as a whole. In this paper we provide evidence for the existence of phase transitions in various resource-constrained project scheduling problems. We discuss the use of network complexity measures and resource parameters as potential order parameters. We show that while the network complexity measures seem to reveal continuous easy-hard or hard-easy phase-transitions, the resource parameters exhibit an easy-hard-easy transition behaviour.status: publishe