Browse Prior Art Database

Simulation Method for Delay Distributions in Discrete-Event Stochastic Systems

IP.com Disclosure Number: IPCOM000118243D
Original Publication Date: 1996-Nov-01
Included in the Prior Art Database: 2005-Apr-01
Document File: 4 page(s) / 191K

Publishing Venue

IBM

Related People

Shedler, GS: AUTHOR

Abstract

It is frequently useful to view a complex stochastic system that evolves over continuous time as making state transitions when events associated with the occupied state occur. Often the system is a discrete-event system in that the stochastic state transitions occur only at an increasing sequence of random times. Certain random time intervals correspond to delays in discrete-event stochastic systems, and simulation is often the only available means for analyzing sequences of such delays. Estimation procedures for the distribution of delays in discrete-event stochastic systems require measurement of individual delays. Available methods for measurement of individual delays (1,2) are based on the idea of "tagging" jobs in the system.

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

Simulation Method for Delay Distributions in Discrete-Event Stochastic
Systems

      It is frequently useful to view a complex stochastic system
that evolves over continuous time as making state transitions when
events associated with the occupied state occur.  Often the system is
a discrete-event system in that the stochastic state transitions
occur only at an increasing sequence of random times.  Certain random
time intervals correspond to delays in discrete-event stochastic
systems, and simulation is often the only available means for
analyzing sequences of such delays.  Estimation procedures for the
distribution of delays in discrete-event stochastic systems require
measurement of individual delays.  Available methods for measurement
of individual delays (1,2) are based on the idea of "tagging" jobs
in the system.  Because tagging increases the number of states and
may increase the number of events in the simulation, estimation
methods that require tagging may not be practical for simulations of
complex systems.  This invention describes a method that does not
require tagging jobs for measurement of delays in discrete-event
stochastic systems.  For definiteness, the method is described in the
context of simulations with an underlying stochastic process that can
be represented as a Generalized Semi-Markov Process (GSMP).  However,
the method is also applicable to simulations of discrete-event
systems represented in other formal systems such as stochastic Petri
nets with general firing times (3,4).

      Heuristically, a GSMP with unique trigger events is a
continuous time stochastic process that makes a state transition when
an event associated with the occupied state occurs.  Events
associated with a state compete to trigger the next state transition
and each trigger event has its own distribution for determining the
next state.  At each state transition of the GSMP, new events may be
scheduled.  For each of these new events, a clock that indicates the
time until the event is scheduled to occur is set according to an
independent (stochastic) mechanism.  If a scheduled event is not in
the set of events that triggers a state transition but is associated
with the next state, its clock continues to run; if such an event is
not associated with the next state, it is cancelled and the
corresponding clock reading is discarded.

      Let S be a finite or countably infinite set of "states" and
E = lbrc e sub 1 , e sub 2 , ..., e sub M rbrc be a finite set of
"events".  For s member of S, let s determines E(s) be a mapping from
S to the nonempty subsets of E; E(s) denotes the set of all events
that are scheduled to occur when the process is in state s.  When the
process is in state s, the occurrence of an event e member of E(s)
triggers a state transition to a state s prime.  Denote the
probability that the new state is s prime given that event e triggers
a state transition in  state s by p(s prime; s, e).  For each s...