Temporal Flexibility Revisited: Maximizing Flexibility by Computing Bipartite Matchings

Simon Mountakis, Tomas Klos, Cees Witteveen

Research output: Chapter in Book/Conference proceedings/Edited volumeConference contributionScientificpeer-review

3 Citations (Scopus)

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.
Original languageEnglish
Title of host publicationProceedings Twenty-Fifth International Conference on Automated Planning and Scheduling
Pages174 - 178
Publication statusPublished - 2015
Event25th International Conference on Automated Planning and Scheduling - Jerusalem, Israel
Duration: 7 Jun 201511 Jun 2015

Conference

Conference25th International Conference on Automated Planning and Scheduling
CountryIsrael
CityJerusalem
Period7/06/1511/06/15

Keywords

  • Flexibility
  • Simple Temporal Networks

Cite this