Applying decomposition and aggregation theory to the analysis of stochastic Petri nets and queueing networks.

Abstract

In this thesis, a class of Stochastic Petri Nets, called Local Balance Stochastic Petri Nets, and a class of queuing networks, called product form queueing networks are investigated. The parametric analysis of Stochastic Petri Nets in general is also studied. The major analysis tool used in this thesis is the Simon and Ando's Decomposition and Aggregation theory. Local Balance Stochastic Petri Nets have the property that their equilibrium state probability distributions have product form solutions. In this thesis, we extend the boundary of the Local Balance Stochastic Petri Nets, propose a systematic test procedure, as well as a C language program to identify this class of Stochastic Petri Nets, and prove that the Stochastic Petri Nets that have passed the test have product form solutions. Simon and Ando's Decomposition and Aggregation theory is then applied to the analysis of Local Balance Stochastic Petri Nets. A Decomposition by Subnet method is proposed. The analysis of a Local Balance Stochastic Petri Net is decomposed into the analysis of subnets. The results are combined to obtain the analysis for the original system. Through the Decomposition by Subnet method, a Norton's theorem for Local Balance Stochastic Petri Nets is developed. By decomposing according to a particular subnet, an aggregated net is constructed. This is that subnet with marking dependent firing rates. We show that the aggregated net may concisely and exactly represent the original Stochastic Petri Net. One of the applications of the Norton's theorem is to facilitate parametric analysis of Local Balance Stochastic Petri Nets. When a Stochastic Petri Net is not a Local Balance Stochastic Petri Net, the concept of "Ideal Aggregate" is used to develop efficient parametric analysis of it. By following a systematic way of constructing the infinitesimal matrix, the transition rate of interest is confined into a small diagonal submatrix. According to the algorithm, every time that particular rate takes a new value, only a Markov Chain of the order of the small diagonal submatrix needs to be analyzed. As a result, computational time requirements are greatly reduced. For the product form queueing networks, we first improve the efficiency of the Distribution Analysis by Chain (DAC) algorithm. We show that the calculation of marginal queue length distribution and throughput in each recursion may be avoided. As a result, computational time requirements are reduced. In addition, the improved algorithm has the benefits with regard to reducing possible numerical errors. Simon and Ando's Decomposition and Aggregation theory is used to develop an Independent Decomposition and Aggregation method for the analysis of product form queueing methods. The queueing network is first transformed into a network with nodes of Infinite Server types. That network is then decomposed independently chain by chain. Through the Independent Decomposition and Aggregation method, an algorithm called Adaptive Convolution By Chain (ACCAL) is derived. It is efficient in dealing with networks that have many chains and a few nodes. Compared with other algorithms, ACCAL has a smaller number of operations. In addition, ACCAL first converts the network into an equivalent one that may be analysed more efficiently. There are three independent parts in the algorithm that may be executed in parallel on a multiprocessor system to further improve the efficiency. The adaptive nature of the parallel processing characteristic distinguish ACCAL from other algorithms. (Abstract shortened by UMI.)