Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Simulation Algorithm for Passage Times in Stochastic Petri Nets

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

Publishing Venue

IBM

Related People

Haas, PJ: AUTHOR [+2]

Abstract

This article describes a simulation method for general characteristics of delays in a discrete event stochastic system specified as a stochastic Petri net. Stochastic Petri nets with timed and immediate transitions and general firing times provide building blocks for formal specification of discrete event stochastic systems on a finite or countable state space; see (1). "Passage times" in 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 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 52% of the total text.

Simulation Algorithm for Passage Times in Stochastic Petri Nets

       This article describes a simulation method for general
characteristics of delays in a discrete event stochastic system
specified as a stochastic Petri net.  Stochastic Petri nets with
timed and immediate transitions and general firing times provide
building blocks for formal specification of discrete event stochastic
systems on a finite or countable state space; see (1).  "Passage
times" in 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 stochastic
Petri net, strongly consistent point estimates and asymptotic
confidence intervals for general characteristics of limiting passage
times.

      A stochastic Petri net (SPN) is specified by a finite set of
"places" and a finite number of "transitions" along with a "normal
input function", an "inhibitor input function", and an "output
function" (each of which associates a set of places with a
transition).  A "marking" of an SPN is an assignment of "token"
counts (nonnegative integers) to the places of the net.  A transition
is "enabled" whenever there is at least one token in each of its
normal input places and no tokens in any of its inhibitor places;
otherwise, it is "disabled".  An enabled transition "fires" by
removing one token per place from a random subset of its normal input
places and depositing one token per place in a random subset of its
output places. There are two types of transitions:  "immediate
transitions" that always fire instantaneously and "timed transitions"
that never fire instantaneously.  The "marking process" of an SPN
records the marking as it evolves over continuous time.  SPNs are
particularly well suited to representation of concurrency,
synchronization, and communication.

      To study passage times in an SPN, we assign to each token in
the net a "label" taking values in a countable set and work with
"labelled stochastic Petri nets" (LSPNs).  The label assigned to a
given token is determined according to a stochastic mechanism when
the token is deposited in a place and may, but need not, remain fixed
until the token is removed from the place.  The augmented marking
process of an LSPN records the marking and labelling as they evolve
over continuous time.  This process is defined in terms of a general
state space Markov chain (GSSMC) that describes the net at successive
marking and labelling change epochs; see (2, Sec.2).

      Specified is a passage time in terms of the underlying GSSMC of
the augmented marking process.  Distinguished state transitions of...