Nested Temporal Networks with Alternatives

Roman Bartak, Ondrej Cepek

Temporal networks play a crucial role in modeling temporal relations in planning and scheduling applications. Recently, several extensions of temporal networks were proposed to integrate non-temporal information such as resource consumption or logical dependencies. Temporal Networks with Alternatives were proposed to model alternative and parallel processes, however the problem of deciding which nodes can be consistently included in such networks is NP-complete. In this paper we propose a tractable subclass of Temporal Networks with Alternatives that can still cover a wide range of real-life processes, while the problem of deciding node validity is solvable in polynomial time. We also present an algorithm that can effectively recognize whether a given network belongs to the proposed sub-class.

Subjects: 3.6 Temporal Reasoning; 1.12 Scheduling

Submitted: May 15, 2007

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.