Skip to main content
main-content

Über dieses Buch

Networks of queues arise frequently as models for a wide variety of congestion phenomena. Discrete event simulation is often the only available means for studying the behavior of complex networks and many such simulations are non­ Markovian in the sense that the underlying stochastic process cannot be repre­ sented as a continuous time Markov chain with countable state space. Based on representation of the underlying stochastic process of the simulation as a gen­ eralized semi-Markov process, this book develops probabilistic and statistical methods for discrete event simulation of networks of queues. The emphasis is on the use of underlying regenerative stochastic process structure for the design of simulation experiments and the analysis of simulation output. The most obvious methodological advantage of simulation is that in principle it is applicable to stochastic systems of arbitrary complexity. In practice, however, it is often a decidedly nontrivial matter to obtain from a simulation information that is both useful and accurate, and to obtain it in an efficient manner. These difficulties arise primarily from the inherent variability in a stochastic system, and it is necessary to seek theoretically sound and computationally efficient methods for carrying out the simulation. Apart from implementation consider­ ations, important concerns for simulation relate to efficient methods for generating sample paths of the underlying stochastic process. the design of simulation ex­ periments, and the analysis of simulation output.

Inhaltsverzeichnis

Frontmatter

Chapter 1. Discrete Event Simulation

Abstract
It appears to be the rule rather than the exception that usefully detailed stochastic models are sufficiently complex so that it is extremely difficult or impossible to obtain an exact analytic solution. Simulation is essentially a controlled statistical sampling technique that can be used to study complex stochastic systems when analytic techniques do not suffice. This book concentrates ondiscrete event digital simulationin which the behavior of a specified stochastic system is observed by sampling on a digital computer system and stochastic state transitions occur only at a set of increasing (random) time points.
Gerald S. Shedler

Chapter 2. Regenerative Simulation

Abstract
Heuristically, a regenerative stochastic process has the characteristic property that there exists a sequence of random time points, referred to as regeneration points or regeneration times, at which the process probabilistically restarts. Typically, the times at which a regenerative process probabilistically starts afresh occur when the process returns to some fixed state. The essence of regeneration is that the evolution of the process between any two successive regeneration points is a probabilistic replica of the process between any other two successive regeneration points. In the presence of certain mild regularity conditions, the regenerative structure guarantees the existence of a limiting distribution (“steady state”) for the process provided that the expected time between regeneration points is finite. Moreover, the limiting distribution of a regenerative process is determined (as a ratio of expected values) by the behavior of the process between any pair of successive regeneration points. These results have important implications (discussed in Section 2.3) for the analysis of simulation output.
Gerald S. Shedler

Chapter 3. Markovian Networks of Queues

Abstract
Networks of queues with priorities among job classes arise frequently as models for a wide variety of congestion phenomena. Simulation is usually the only available means for studying such networks. The underlying stochastic process of the simulation is defined in terms of a linear “job stack,” an enumeration by service center and job class of all the jobs.
Gerald S. Shedler

Chapter 4. Non-Markovian Networks of Queues

Abstract
In Chapter 3 we developed regenerative simulation methods for networks of queues with exponential service times and Markovian job routing. In this chapter, we derive analogous estimation procedures for networks with general service times. The development requires that we restrict attention to networks that have a “single state” in which all jobs are at the same service center with exactly one job in service. Regenerative cycles are defined in terms of entrances to the single state.
Gerald S. Shedler

Backmatter

Weitere Informationen