Flexibility and decoupling in Simple Temporal Networks

摘要

We propose a new metric to determine the flexibility of a Simple Temporal Network (STN). After reviewing some existing flexibility metrics, we conclude that these metrics fail to capture the dependencies between events specified in the STN. As a consequence, these metrics will usually overestimate the available flexibility in such a system. We propose to use an intuitively more acceptable flexibility metric. This metric is based upon the notion of an interval schedule for an STN. Such an interval schedule specifies an interval for every event in the STN in such a way that, for every event, we are free to choose a starting time within its interval independently from the choice made for other events. We show that an interval schedule that maximizes our flexibility metric is computable in low-order polynomial time. As byproducts of this flexibility metric, we discuss simple solutions to problems in STNs with uncertainty (STNUs) and temporal decoupling in STNs. With respect to the latter we show that after computing our flexibility metric, we get a decomposition of the STN almost for free. Even more importantly, we show that contrary to popular belief, such a decomposition does not affect the flexibility of the original STN.