Computation - Operations Research Models and Methods

Computation

Markov Collection

Markov Data

Birth-Death

Finite Queue

Random Walk

	Markov 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 the event of either a birth or a death. A birth increases the population by one, and a death decreases the population by one. 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. 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 death rate is the parameter of the exponential distribution that governs the time to the next death. 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. There are various alternatives that 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 process reaches the maximum, the system immediately is purged. 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 event will be useful for some practical applications. 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 balk 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.
Creating a Data Page
		The Birth-Death dialog is to the left. The Model Name field accepts a name for the problem. A default name is provided, but it may be changed. We specify that the birth and death rates are constant (not affected by the population) by leaving the Different Rates box unchecked. The Max. State Index field specifies the maximum population, but this can be changed on the data table. Checking the Make Random Problem box fills the data form with random data when the Different Rates option is selected. On clicking the OK button, the Data worksheet is created and the data table is placed on this worksheet. The worksheet for this case is shown below. The data is placed in column F with titles describing the data in column D. White fields in Column E may be changed while the yellow fields contain formulas or features that determine the structure of the model and should not be changed.

	The maximum population determines the size of the model and the corresponding solution effort. Other table entries describe time and economic measures. When cost is the economic measure, a negative value indicates an income. Costs are specified for births, deaths, a fixed cost for purging and a variable cost of purging (it is multiplied by the population at the purge event), and a cost for holding an item in the system for one unit of the time measure. The discount rate is important for some applications and it should be a nonnegative value. The birth and death rates are specified per unit of the time measure (hours in this case). For the case considered here the birth and death rates are constant with respect to the population. The action entry, Purge, is colored yellow because it determines the form of the model that will be constructed. It cannot be changed, but all the white data cells can be changed and immediately reflected in the model. The DTMC model requires probabilities rather than transition rates, so to approximate the exponential distributions of the birth-death process we define a time interval that should be small relative to the rates. We use 0.01 for the example. In general: Event Transition probability = (Event Rate)(Time Interval) For the example with a time interval of 0.01, Birth Probability = 100.01 = 0.1 Death Probability = 120.01 = 0.12 The time interval chosen must be small enough that probabilities are considerably nearer to 0 than 1. The discrete approximation to the birth-death process assumes that only one event occurs in an interval. The assumption is better with very small intervals. The expression for cost model for one period is below. We use the notation IF(Event, Cost of Event, 0) to indicate that if the event occurs the cost of the event is expended during the period, otherwise the cost is zero. The cost depends on the population. Cost per period = (Population)(Holding Cost per period) + IF(Death, Cost of Death, 0) + IF(Birth, Cost of Birth, 0) + IF(Purge, Fixed Cost of Purge + (Variable Cost of Purge)*(Population), 0)
Building a Model
	The data form has a single red button. The Build Model button calls the Markov Models add-in to insert the model worksheet and build a general model. The Markov Data add-in then fills the form that describes the birth-death process. If you are not interested in the modeling process you may proceed by clicking the Build Matrix Model button. This button calls the Markov Analysis add-in for further analysis. The remainder of this page briefly describes the particular model of the DTMC birth-death process. More detail is found on the pages describing the Markov Models add-in. Part of the model is shown below. Generally yellow cells hold formulas that should not be changed and white cells hold parameters that define or limit the model. The first figure shows the part defining the states and events associated with this process. We call these the elements of the model.

	The VBA code of the Markov Data add-in specifies the number of state variables and event variables to include in the model. For this case there is one state variable, indicating the population. There are two event variables, indicating birth or death events. Note that events have only two values 0 or 1. The Event is represented by the vector consisting of cells L14:M14. Red outlines identify most of the cells that are filled by the Markov Data add-in. Some of the titles that are filled are not outlined in red to make the figure more readable. Others not outlined hold default values. You may be able to identify some of the data items in the model form. For example, cell F19, the maximum state value, holds a formula linking the Max Population cell to the data cell holding that parameter. Cells that show TRUE or FALSE hold logical expressions that determine whether states or events are Feasible (TRUE) or Not Feasible (FALSE). This model has a condition in cell K17 that shows the feasibility of an event is: =SUM(BD_1_MM_Event)=1 This evaluates to TRUE when the sum of L14 through M14 is equal to 1. An event with both a birth and a death in a single time interval is determined as not feasible and the associated transition is not included in the model. Although the event of neither a birth nor death is feasible, we do not require that transitions that do not change the state be explicitly defined.
Transitions
	A second part of the model describes transitions. With the system is some state, the occurrence of an event usually causes the state to change. This portion of the model indicates the events that might occur with associated cost and probability. Also the model must indicate the new sate reached when the event occurs. Starting in row 29 the model identifies three possible transitions, the purge transition, the birth transition, and the death transition. There are several ways to model a situation. The goal is to create a model that is clear, but also efficient in representation and computation. The example shows in cell F33 that the current state is equal to 10, the maximum population. The event is a vector of two cells, L33 and L34. It shows the birth event. The top part of the display in rows 30 to 37 shows some of the results of this combination of state and event in cells O33 through O35. O33 shows the name "P10/Birth". O34 shows the probability, 0.1. The "TRUE" in Cell O35 shows that at least one of the modeled transitions results in a feasible transition for this combination of state and event. In the present case the condition for the first transition, the Purge condition, is feasible. The cost of the transition is read from cell K46. That cell holds the formula: Transition Cost = Fixed Purge Cost + (State Value)(Variable Purge Cost). For this case, Transition Cost = 100+(10)(-20) = -100 The State Change formula in cell F44 computes that the population value will be reduced by 10. The Next State is subsequently computed as 0. Thus the purge transition changes the state from 10 to 0. The cost of this transition is -100, and its probability is 0.1. These values will ultimately be transferred to the transition probability matrix and transition cost matrix for a Markov Chain Analysis. All three event possibilities, (0,1), (1,0) and (0,0) result in the purge transition so the total probability of this transition will be 1.

	When more than one transition is feasible, the first transition encountered from top to button is the one chosen for inclusion in the transition set. This sometimes simplifies modeling. We describe the model feature more completely in the Markov Models section. The Markov Data add-in interacts with the model by setting certain cells to contain values and formulas. All the red outlined cells in the figure were set by the Markov Data add-in.
Build Matrix Model
	The casual user of the birth-death model described on this page need not interact with the model form. Every necessary function is performed by one of the add-ins. Changing the data on the table immediately changes the affected cells on the model form. Any change of the data requires the generation of the worksheets used for the markov analysis. This is accomplished by clicking on the Build Matrix Model button. Then the Markov Analysis add-in constructs the appropriate Excel worksheets and the Markov Models add-in inserts the data defined by the model. The probability transition matrix model for the example is shown below. Note that the state P_0 allows only the birth transition, to P_1, with probability 0.1. The remainder of the probability, 0.9 is assigned to the null event that leaves the system in the state P_0. The null event is not represented by a feasible transition in the model shown in this page except for the purge transition. Any probability not assigned by a defined transition is assigned to the cell indicating that the state does not change.

	The economic transition matrix is also constructed. Observe that the probability of returning from state P_10 to P_0 is 1 with a cost of -100. The State Costs shown in column E represent the holding costs in the model. The birth and death costs are shown in the Transition Cost Matrix. All these entries were inserted automatically.

	The Markov Analysis add-in allows several different analysis as indicated by the buttons on the Matrix page. The steady-state probabilities are shown below.

Summary
	This page has followed the development of the birth-death Markov process. The Markov Data add-in constructs a table holding data for the birth-death process. By clicking the Build Model button on the data page, the Markov Models add-in constructs the model worksheet and it is filled with the constants and formulas that implement the model. By clicking the Build Matrix Model button, the Markov Analysis add-in builds the probability and economic transition matrices and inserts the values describing the birth-death process. Note that all three add-ins must be installed for all the steps to work. There are three levels of user interaction with these add-ins. The simplest requires only the specification of the items in the data table. 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. Several other model types are included with the Markov Data add-in. They are described on the following pages. 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 Markov 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.