Temporal Flexibility Revisited: Maximizing Flexibility by Computing Bipartite Matchings

Authors

  • Simon Mountakis Delft University of Technology
  • Tomas Klos Delft University of Technology
  • Cees Witteveen Delft University of Technology

DOI:

https://doi.org/10.1609/icaps.v25i1.13720

Keywords:

Flexibility, Simple Temporal Networks

Abstract

We discuss two flexibility metrics for Simple Temporal Networks (STNs): the so-called naive flexibility metric based on the difference between earliest and latest starting times of temporal variables, and a recently proposed concurrent flexibility metric. We establish an interesting connection between the computation of these flexibility metrics and properties of the minimal distance matrix DS of an STN S: the concurrent flexibility metric can be computed by finding a minimum weight matching of a weighted bipartite graph completely specified by DS, while the naive flexibility metric corresponds to computing a maximum weight matching in the same graph. From a practical point of view this correspondence offers an advantage: instead of using an O(n5) LP-based approach, reducing the problem to a matching problem we derive an O(n3) algorithm for computing the concurrent flexibility metric.

Downloads

Published

2015-04-08

How to Cite

Mountakis, S., Klos, T., & Witteveen, C. (2015). Temporal Flexibility Revisited: Maximizing Flexibility by Computing Bipartite Matchings. Proceedings of the International Conference on Automated Planning and Scheduling, 25(1), 174-178. https://doi.org/10.1609/icaps.v25i1.13720