For the most recent entries see the Petri Nets Newsletter.

Modelling and analysis of timed Petri nets using heaps of pieces.

Gaubert, S.; Mairesse, J.

In: IEEE Trans. Autom. Control, Vol. 44, No. 4, pages 683-697. 1999.

Abstract: We show that safe timed Petri nets can be represented by special automata over the (max,+) semiring, which compute the height of heaps of pieces. This extends to the timed case the classical representation á la Mazurkiewicz of the behavior of safe Petri nets by trace monoids and trace languages. For a subclass including all safe Free Choice Petri nets, we obtain reduced heap realizations using structural properties of the net (covering by safe state machine components). We illustrate the heap-based modeling by the typical case of safe jobshops. For a periodic schedule, we obtain a heap-based throughput formula, which is simpler to compute than its traditional timed event graph version, particularly if one is interested in the successive evaluation of a large number of possible schedules.

Keywords: Timed Petri nets; automata with multiplicities; heaps of pieces; (max,+) semiring; scheduling.


Do you need a refined search? Try our search engine which allows complex field-based queries.

Back to the Petri Nets Bibliography