Semi-Markov Processes

A Primer

by Bennett L. Fox

Download eBook for Free

FormatFile SizeNotes
PDF file 1.3 MB

Use Adobe Acrobat Reader version 10 or higher for the best experience.

An introduction to semi-Markov processes (SMPs) for an audience primarily interested in applications. SMPs, useful in problems of inventory control and queueing, result from a union of renewal processes and Markov chains; they consider only the states corresponding to instantaneous regeneration points and do so in continuous, rather than discrete, time. The presentation is deliberately unconventional to permit a more heuristic discussion of the subject. The approach used eliminates all nonzero holding times and is thus not the same as the state definition used in more fully rigorous treatments of probability theory in general and SMPs in particular. The underlying mathematics remains the same, however, and the approach permits the focus to be on aspects of problem-solving interest. The states are defined so that they can be represented graphically by nodes of a network with stochastic arc lengths; for example, traversing an arc might correspond to a customer completing service. In specifying the states, a detailed description is often required to make all decision points regeneration points, and linear programs with hundreds or thousands of constraints may result. Generally, analysis shows that the constraint matrix is sparse and structured so as to be amenable to decomposition.

This report is part of the RAND Corporation Research memorandum series. The Research Memorandum was a product of the RAND Corporation from 1948 to 1973 that represented working papers meant to report current results of RAND research to appropriate audiences.

This document and trademark(s) contained herein are protected by law. This representation of RAND intellectual property is provided for noncommercial use only. Unauthorized posting of this publication online is prohibited; linking directly to this product page is encouraged. Permission is required from RAND to reproduce, or reuse in another form, any of its research documents for commercial purposes. For information on reprint and reuse permissions, please visit

The RAND Corporation is a nonprofit institution that helps improve policy and decisionmaking through research and analysis. RAND's publications do not necessarily reflect the opinions of its research clients and sponsors.