Return to Index
Operations Research Models and Methods
Computation Section
Subunit Dynamic Programming Data
 - Birth-Death Process

A wide range of situations, such as warehousing and cross-docking operations, population infestations, and the servicing of customers on a hotline, can be described in terms of fairly simple stochastic processes.  This section concentrates on an important special case called the birth-death process.

For the birth-death process, the population is the number of entities that comprise some system. The population ranges from 0 to a specified maximum population. Population changes with either a birth event or a death event. A birth increases the population by one, and a death decreases the population by one. The figure below shows the state network for a birth death system. The numbers in the circles indicate the population state variable.

State Network when the system is purged when an arrival occurs at the maximum population

The times between events are governed by exponential distributions. The birth rate is the parameter of the exponential distribution that describes the time to the next birth. The birth rate is the inverse of the mean time between birth events. The death rate is the parameter of the exponential distribution that governs the time to the next death. The death rate is the inverse of the mean time between death events. Birth and death rates may be constant or depend on the population value.

Since the maximum population is finite, it is necessary to define what happens when the population reaches this maximum. Various alternatives could be modeled. The process could simply terminate. The process could continue to operate, but births would be neglected. Our models have two options, the purge option and the balk option. The purge option assumes that when the maximum population is reached, the system is purged with the next arrival. That is, the population returns to state 0. This is called the purge event. There is a fixed cost of the purge as well as a variable cost that is linear with the number purged. The purge model could represent a batch process that is triggered when the population reaches a maximum amount.

The balk option assumes that when the process reaches the maximum, the next arrival will balk and not enter the system. There is a charge for this event to represent the cost of the lost arrival. If some other rule of operation is more appropriate, the model can be rather easily changed to represent the alternative.

State Network when arrivals balk when the population is at the maximum value

Although we use the terms population, birth, and death, the models described here not limited to biological populations. Many other applications are readily apparent. For example we could consider a call center where the population is the number of customers waiting or in service, a birth is the arrival of a new call, and a death is the completion of a service.

Several different models are described on this page. The CTMC and the DTMC involve no decisions. The purpose of an analysis is to determine the probability distribution of the states. The MDP adds the action of either purge or balk to each state and dynamic programming determines the optimum decision at each state.




There are three levels of user interaction with these add-ins. The simplest requires only the specification of the items in the data table provided by the DP Data add-in. Clicking the appropriate buttons first creates the model and then builds the matrix for analysis. The user of these Excel add-ins need not deal with the complexities of VBA to create and solve large Markov Models.

The second level of interaction is accomplished by changing some of the parameters on the model page. By simple modifications of the Markov model worksheets, many alternative assumptions can be addressed.

The third level of interaction requires moderate ability to program the VBA code of the DP Data add-in. The source code is open, and the interested user can modify the source code of the add-in to create almost any kind of Markov model.

The next two pages describe the data and model for the Markov Chain. The following page is about the Markov Decision Process based on the birth-death process.

Return to Top

tree roots

Operations Research Models and Methods
by Paul A. Jensen
Copyright 2004 - All rights reserved