First Passage Time Computation in Tagged GSPNs with Queue Places

This paper presents an extension of the generalized stochastic Petri net (GSPN) formalism that enables the computation of first passage time distributions. The tagged customer technique typical of queuing networks is adapted to the GSPN context by providing a formal definition and an automatic computation of the groups of tokens that can be identified as customers, i.e. classes of homogeneous entities behaving in a similar manner. Passage times are identified through the concept of events that correspond to the firing of transitions placed at the boundaries of a subnet. The extended model obtained with this specifications is translated into an ordinary GSPN by isolating a customer from the group and highlighting its path through the net thus obtaining a representation suited for the passage time analysis. Proofs are provided to show the equivalence between these models with respect to their steady-state distributions. An important and original aspect treated in this paper is the possibility of specifying several scheduling policies of tokens at places, an information not present in ordinary GSPN models, but that is vital for the precise computation of first passage time distributions as shown by a few results computed for a simple Flexible Manufacturing application.