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.