Timed Partial Order Inference Algorithm Conference Proceeding uri icon



  • In this work, we propose the model of timed partial orders (TPOs) for specifying workflow schedules, especially for modeling manufacturing processes. TPOs integrate partial orders over events in a workflow, specifying ``happens-before'' relations, with timing constraints specified using guards and resets on clocks -- an idea borrowed from timed-automata specifications. TPOs naturally allow us to capture event ordering, along with a restricted but useful class of timing relationships. Next, we consider the problem of mining TPO schedules from workflow logs, which include events along with their time stamps. We demonstrate a relationship between formulating TPOs and the graph-coloring problem, and present an algorithm for learning TPOs with correctness guarantees.; We demonstrate our approach on synthetic datasets, including two datasets inspired by real-life applications of aircraft turnaround and gameplay videos of the Overcooked computer game. Our TPO mining algorithm can infer TPOs involving hundreds of events from thousands of data-points within a few seconds. We show that the resulting TPOs provide useful insights into the dependencies and timing constraints for workflows.

publication date

  • September 1, 2024

has restriction

  • bronze

Date in CU Experts

  • January 30, 2024 10:32 AM

Full Author List

  • Watanabe K; Fainekos G; Hoxha B; Lahijanian M; Prokhorov D; Sankaranarayanan S; Yamaguchi T

author count

  • 7

Other Profiles

International Standard Serial Number (ISSN)

  • 2334-0835

Electronic International Standard Serial Number (EISSN)

  • 2334-0843

Additional Document Info

start page

  • 639

end page

  • 647


  • 33


  • 1