Resource temporal networks: definition and complexity
Philippe Laborie · International Joint Conference on Artificial Intelligence · 2003
This paper introduces the concept of Resource Temporal Network (RTN), a constraint network that subsumes both classical attributes used in A.I. Planning and capacity resources traditionally handled in Scheduling. After giving a formal definition of RTNs, we analyze their expressive power and study complexities of several fragments of the RTN framework. We show that solving an RTN is in general NP-Complete - which is not surprising given the expressivity of the framework - whereas computing a Necessary Truth Criterion is polynomial. This last result opens the door for promising algorithms to solve RTNs.