Solution techniques for stochastic petri nets.
Yao Li · 1992
Stochastic Petri Nets (SPNs) are used in engineering and systems analysis to model communication systems, computer systems and software, flexible manufacturing systems, and other applications. The objective of this thesis is to improve the solution techniques for SPN, in particular, to solve or alleviate the state space explosion problem--the bottleneck of SPN analysis. Several solution techniques have been examined, ranging from separable SPN with product form solution, Norton's aggregation, a new approximate convolution algorithm for solving large, colored SPNs, to the core of this thesis--the iterative SPN decomposition technique. This technique uses the concept of divide and conquer. It iteratively solves several size-reduced auxiliary SPN models for performance measures of the original SPN. The structure of the auxiliary SPNs is obtained by aggregating some subnets in the original SPN according to some formal PN reduction rules while preserving the external black-box equivalence of the subnets such that the structural and behavioral properties of the unaggregated part are not affected. The rate parameters of the auxiliary models are obtained iteratively. This approximate technique has good accuracy and large computation reduction, and has been applied to a large application example with success. The major contribution of this thesis is the proposed iterative decomposition technique, which is applicable to general classes of SPNs, and to large models. For the technique, this thesis defines the black-box equivalence criterion for aggregating subnets in PN so that the desired structural and behavioral properties can be preserved, and several formal reduction rules that are shown to preserve the black-box equivalence. The iterative parameter tuning process can be regarded as a generalization of Jacobson and Lazowska's surrogate delay method to SPN domain by allowing multi-arc connections between subnets, several subnets aggregated separately in one auxiliary model, several auxiliary models to control the degree of the structural reduction, and local marking dependent or constant rate for an aggregated transition with degrees of accuracies and complexities.