zbMATH — the first resource for mathematics

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.)