Timed Petri net schedules. (English) Zbl 0667.68051

Carlier, J.; Chretienne, P.

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.

MSC:

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

Keywords:

timed Petri net schedules; polynomial algorithm; bounded Petri nets

Citations:

Zbl 0658.00014