Return to Index
Operations Research Models and Methods
Models Section


ATM Machine

Model Components

Analytical Results

Example Problem
Model Components
The For CTMC's, all the information concerning the model is entirely determined by the current state. It is said to have no memory because the future realization depends only on the current state and in no way on the past. The advantage that results when a process can be classified as Markovian is that its cost and performance can be easily calculated.


The Exponential Distribution


Suppose that arrivals to the ATM are governed by an exponential distribution with a mean of 0.5 minutes. When an arrival occurs, the expected time to the next arrival is 0.5 minutes. Suppose one minute goes by and no customers appear. We might be tempted to say that the arrival is late and that one should occur at any time. For the exponential distribution this would be wrong. In fact, the expected time to the next arrival is still 0.5 minutes due to the memoryless property of the distribution. No matter how long the wait without an arrival, the remaining time still has an exponential distribution with the same expected value as at the start. The exponential distribution is a continuous probability distribution with a single positive parameter called the rate. It models the random variable that is the time between events t, where the rate of occurrence of the events is . The density function and cumulative distribution for the general exponential distribution are

The mean and variance of the distribution are

Fig. 2 plots f(t) for = 2. The function begins at l and decreases toward 0, which it approaches asymptotically. Since the random variable is time, f(t) = 0 for t < 0. The duration of an activity represented by this distribution will most often be quite short, but occasionally it will assume large values. The probability that the activity will take 0.5 minute or less, for example, is roughly 63%. The standard deviation of the exponential distribution is equal to its mean. This is relatively large for most physical activities, so one might consider the exponential somewhat extreme in terms of variability.

Figure 2. The exponential distribution

When all activity durations of a stochastic process have exponential distributions, all activity completion times depend only on the current state. They do not depend on how that state was reached or how long the system has resided there. Thus a stochastic process in which all activities are exponentially distributed is a CTMC. The exponential distribution is the only continuous distribution that has the memorlyless property.


Rate Matrix


For queueing problems like the ATM example, we typically use as the arrival rate with the mean time between arrivals given by . For the service activity we use as the service rate with being the mean time for the service activity. For the ATM example = 2/min and = 2.5/min. For CTMC's, activities are well represented by their rate of occurrence, so rather than using a state-transition network like the one in Fig. 1, we use a rate network as in Fig. 3. The rate network is easily constructed from the state-transition network by replacing the activity designation by the rate for the activity.

Figure 3. The rate network

For computational purposes, we introduce the rate matrix R whose element is the transition rate from state i to j. The general matrix shown below has maximum state index K but for some problems the matrix might have infinite dimension. (Note that in this chapter we use K rather than m as the maximum state index to conform with the queueing literature.)

General rate matrix

The rate matrix for the ATM example is shown below.

Rate matrix for the ATM

The rate matrix for the ATM example allows only arrivals for state 0 and so has one nonzero entry.

State 5 allows only service completions and similarly has one nonzero entry.

Every other state allows both events. We have shown the general rate matrix and the rate matrix for the example with 0's on the main diagonal. For most situations this will be true. When computing the steady-state probabilities it doesn't matter whether the diagonal elements are 0. For some problems there may be events that cause the system to remain in its current state and experience some economic effect. In these cases, positive transition rates may be placed on the diagonal.


Return to Top

tree roots

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