Performance evaluation of Petri net models with large state spaces

This thesis presents the CGSPN methodology for the performance evaluation of generalized stochastic Petri nets with large state spaces, including colored Petri nets. Simulation and moment generating function analysis are used to generate approximate performance metrics without fully exploring the state space of the Petri net. The methodology is applied to colored Petri nets by using simulation to enumerate a partial reachability graph which is then analyzed using moment generating function (MGF) analysis. The convergence of this analysis technique is characterized by upper and lower bounds where the lower bound can be explicitly determined. Example models including a two machine one buffer batch system are analyzed to demonstrate the capabilities of the CGSPN methodology.;The partial reachability graph is constructed from paths taken by a simulator as it executes the Petri net. This reachability graph is then combined with transition information from the original Petri net to form a state machine Petri net (SMPN) which can then be analyzed via moment generating functions. This analysis involves computing an equivalent transfer function between two places of the SMPN. This equivalent transfer function then describes the distribution of passage time between the corresponding states of the system being modeled.;Dramatic improvements are made to the moment generating function methodology to support the analysis of large state space models. A straightforward reduction method is created, Extended Substitution Rules, which drastically reduces the time required to compute the equivalent transfer function. The method utilizes three reduction rules, generalized parallel substitution, generalized loop substitution and generalized sequence substitution. The computational complexity of this new method is analyzed and compared with Mason's rule, simple substitution rules, and system of linear equations. This analysis shows that the Extended Substitution Rules reduce the computational complexity of the reduction process from O((n-1)!2n!) to O(n3) or even O(n) in some cases.;The CGSPN methodology has been implemented in Java and closely integrated with Mathematica for symbolic manipulation of equations. The details of this implementation and associated software are presented.;The CGSPN methodology, including the improvements to SMPN reduction and handling of large equations, represents an innovative approach to the performance evaluation of Petri nets with large state spaces and colored Petri nets.