Computing First Passage Time Distributions in Stochastic Well-Formed Nets

This paper proposes a method to compute first passage time distribution measures in Stochastic Well-Formed Net (SWN), which extends a previous approach developed for Generalized Stochastic Petri Nets (GSPN) using P-semiflows to identify the ``customers'' circulating into the system. As in the case of GSPNs, the method comprises three steps: identification of a set of colored tokens circulating in the net, called ``customers'', for which it is possible to compute the first passage time distribution; identification of the measure of interest by selection of a subnet where the ``customers'' can flow and spend time; generation of all the required information to apply classical passage time computation methods for Markov chains. Despite these similarities, the paper is original as it discusses the differences that are due to the complexity of dealing with colored tokens typical of SWNs. In particular, an algorithm for computing the P-semiflows which identify the ``customers'' of these models is provided, overcoming the difficulty of finding P-semiflows for colored PNs (in particular for SWNs) in parametric form, by exploiting the peculiarities of the objective of this investigation. Finally, the approach extends the SWN notation in order to provide a way to ease the modeler in the specification of customer scheduling policies that may affect the computation of the first passage time distribution. This extension, inspired by the QPN formalism, adds to SWN some ``syntactic sugar'' that allows to include in the model queueing places which are automatically replaced by appropriate submodels, before proceeding with the solution of the model.