Timed petri nets: A solution to the minimum-time-reachability problem between two states of a timed-event graph
Event graphs are a special class of Petri nets [4]. They are used to model a system of processes linked together by synchronization constraints. What makes them simpler than general Petri nets is that whenever some processes are ready to execute, all of them can simultaneously begin to execute without any conflict. A timed Petri net is a Petri net for which known execution times are associated with transitions (i.e., processes) The model was first introduced by Ramchandani [ 11, who studied strongly periodic executions of strongly connected timed-event graphs. In [5], a formal mathematical model for timed Petri nets is given. From this model, properties of the set of initial states feasible with respect to a given controlled execution are derived. A study of the asymptotic behavior of the “earliest” controlled execution of a timed-event graph is done, from which exact asymptotic frequencies can be computed. The main concern of this paper is the study of the reachability relation for timed-event graphs. We give an algorithm to solve the reachability problem and we compute the minimal reachability time from a source state to a sink state.