Browse Prior Art Database

Simulation Algorithm for Passage Times in Colored Stochastic Petri Nets

IP.com Disclosure Number: IPCOM000108523D
Original Publication Date: 1992-Jun-01
Included in the Prior Art Database: 2005-Mar-22
Document File: 3 page(s) / 142K

Publishing Venue

IBM

Related People

Haas, PJ: AUTHOR [+2]

Abstract

Disclosed is a simulation method for general characteristics of delays in a discrete event stochastic system specified as a colored stochastic Petri net (CSPN). Colored stochastic Petri nets with general firing times provide building blocks for concise formal specification of discrete event stochastic systems containing many subsystems of similar structure or behavior; see [1,2]. "Passage times" in colored stochastic Petri nets are random times that correspond to delays in discrete event stochastic systems. The algorithm provides a means for obtaining, by discrete event simulation of a colored stochastic Petri net, strongly consistent point estimates and asymptotic confidence intervals for general characteristics of limiting passage times.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 49% of the total text.

Simulation Algorithm for Passage Times in Colored Stochastic Petri Nets

       Disclosed is a simulation method for general
characteristics of delays in a discrete event stochastic system
specified as a colored stochastic Petri net (CSPN).  Colored
stochastic Petri nets with general firing times provide building
blocks for concise formal specification of discrete event stochastic
systems containing many subsystems of similar structure or behavior;
see [1,2].  "Passage times" in colored stochastic Petri nets are
random times that correspond to delays in discrete event stochastic
systems. The algorithm provides a means for obtaining, by discrete
event simulation of a colored stochastic Petri net, strongly
consistent point estimates and asymptotic confidence intervals for
general characteristics of limiting passage times.

      A CSPN is specified by a finite set of "places", a finite
number of "transitions", and a finite set of "colors", along with an
"input incidence function" and an "output incidence function".  A
"marking" of a CSPN is an assignment of nonnegative integers to the
places  of the net, and represents the number of "tokens" of each
color in each place.  A transition is "enabled" in a color whenever
each place in the net contains a sufficient number of tokens of each
color, as specified by the input incidence function. A transition
that is enabled in a color "fires" in the color by removing from each
place a deterministic number (possibly zero) of tokens of each color,
as specified by the input incidence function, and depositing in each
place a deterministic number (possibly zero) of tokens of each color,
as specified by the output incidence function. Tokens are removed and
deposited instantaneously.  For each place, the number of tokens of a
color that are removed and deposited depends only upon the transition
that fires, the "firing color" and the place itself.  The color of a
token in a place remains fixed until the token is removed from the
place.  There are two types of transitions: "immediate transitions"
that always fire instantaneously and "timed transitions" that never
fire instantaneously.  The "marking process" of a CSPN records the
marking as it evolves over continuous time and is defined in terms of
a general state space Markov chain (GSSMC) that describes the net at
successive marking change epochs; see (3, Section 2).

      CSPNs with general firing time distributions provide building
blocks for formal specification of discrete event stochastic systems
and are well suited to representation of concurrency,
synchronization, and communication.  The primary appeal of CSPNs for
modeling is that they permit concise specification of stochastic
systems that contain many subsystems of similar structure or
behavior.  CSPNs have a natural graphical representation that
facilitates modeling, and the dynamic behavior of a CSPN can be
inferred almost entirely from the graph.  Techniques for determining...