Characterizing Token Delays of Timed Event Graphs for K-Cyclic Schedules

Tae Eog Lee, Hyun Jung Kim, Dong Hyun Roh, Ramavarapu S. Sreenivas

Research output: Contribution to journalArticlepeer-review


A timed discrete event system, which repeats identical work cycles, has task delays due to synchronization between work cycles. Real such systems tend to operate mostly in a K-cyclic timing regime, where a sequence of identical timing patterns is repeated for every K cycles. Therefore, the task delays fluctuate and repeat a sequence of K different values, and hence have higher risk of violating an upper limit. Task delays correspond to token delays at the system's timed event graph model. We therefore examine token delays in K-cyclic schedules of a timed event graph, an essential class of Petri nets. We first identify all possible K-cyclic schedules and define their initial phases. We then develop a closed-formula on the token delays on a path for a K-cyclic schedule, which can be computed by the longest path lengths between the nodes in an associated directed graph. We also present a formula for 1-cyclic schedules. The formulae can be used for computing statistics on K-different token delays, maximizing or minimizing the token delays with regard to all possible initial phases, and verifying task delay constraints, if any.

Original languageEnglish (US)
Article number7470632
Pages (from-to)961-966
Number of pages6
JournalIEEE Transactions on Automatic Control
Issue number2
StatePublished - Feb 2017


  • Discrete event system
  • K-cyclic schedule
  • Petri net
  • task delay
  • timed event graph
  • token delay.

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Computer Science Applications
  • Electrical and Electronic Engineering


Dive into the research topics of 'Characterizing Token Delays of Timed Event Graphs for K-Cyclic Schedules'. Together they form a unique fingerprint.

Cite this