Timed Petri net schedules. (English) Zbl 0667.68051

Advances in Petri nets, APN, Proc. 8th Eur. Workshop, Zaragoza/Spain 1987, Lect. Notes Comput. Sci. 340, 62-84 (1988).
[For the entire collection see Zbl 0658.00014.]
In this paper, we define timed Petri net schedules and study some of their properties. We prove that the set of schedules issued from a firable sequence of the underlying Petri net has a minimum element we call earliest schedule of the sequence. We then propose a polynomial algorithm to compute it. In order to study earliest schedules, we introduce next a graph we cal earliest state graph. Finally, for bounded Petri nets, we prove that earliest schedules issued from periodic infinite sequences are K-periodic and constitute a dominant subset.


68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)


Zbl 0658.00014