4.11 Time-Dependent Analysis of The M/M/m Queueing System

The applications of queueing theory that we have discussed so far in this chapter have almost invariably used the assumption of steady state and thus have ignored the time dimension. There are many situations, however, where it is precisely the fluctuation of congestion effects with time that we are most interested in.
        Consider, for example, the problem of determining personnel requirements for the operation of toll booths at a bridge, tunnel, or highway leading into a city. It would clearly be foolish to maintain the same number of open booths from, say, 2 to 4 A.m. as during the peak traffic hours of 7 to 9 A.M. This situation calls for an analysis that recognizes explicitly the fact that demand (i.e., the rate at which cars arrive at the toll-collection area) varies considerably over time. Similarly, in deciding on the number of police patrol units to be deployed over a 24-hour period, a police administrator would do well to take into account the fact that the rate of calls to police dispatchers is at a peak between 5 P.m. and midnight in most cities and then falls rapidly to very low levels during the early morning hours.
       One way to deal with such problems is to subdivide the time period of interest into shorter time periods, during which the demand rates and the service rates can be considered approximately constant and perform a separate queueing analysis for each of these shorter time periods, assuming that the steady-state results are valid within each of them. There are numerous examples of this type of analysis, including a classical one [EDIE 54] that was applied to the toll-booth problem that we have just described.
       This approach, however, may sometimes be inadequate: the demand and/or service rates may be changing too rapidly over time for the steadystate expressions (which assume the existence of "long-term equilibrium conditions") to be valid. The approach also fails if it happens that for one or more of the short periods of time average demand exceeds the service rate-a case for which no steady-state expressions exist.
       In some cases of this type, numerical solution techniques can often be of some help. We shall describe below one such technique as it applies to M/M/m queueing systems.
       The analysis below will be performed with reference to the center-for-emergency-calls example (see Section 4.6), for which it will be assumed that:

1. The arrival of calls at the M/M/m system is a Poisson process with a known time-dependent rate lambda.gif (179 bytes)(t) for 0 leq.gif (53 bytes) t leq.gif (53 bytes)T.

2. The m operators/servers are independent and identical, and service times are independent and negative exponential with mean mu.gif (189 bytes)neg1.gif (875 bytes) (mu.gif (189 bytes) is not a function of time).

3. The queueing system has a capacity of K (Kgeq.gif (61 bytes) m) and calls that find the system full are lost.

4. The state of the system at time t = 0 is known probabilistically (see below for further explanation).

       Let Pn(t), i = 0, 1, 2, . . . , K, denote the probability that at time t there are n calls present-being answered or waiting for an operator. Using the state-transition diagram 4.9, it is then simple to write a system of first-order differential equations that describe this queueing system [cf. (4.20) and (4.21)]:

form4.120a.gif (22251 bytes)

Given a set of probability values P(O) that describe the state of the queueing system at t = 0 [i.e., P(0) ={P0(0), P1(0), . . . Pk(0)} such that sumkn0.gif (1837 bytes)=1], the K + 1 equations (4.120) can be solved iteratively on a computer. To do this, one must choose a time interval At which is sufficiently small to be consistent with the Poisson assumptions for the arrival and service pro- cesses (i.e., the probability of two or more user arrivals or service com- pletions during At must be very small) and then use the approximation

form4.121.gif (5241 bytes)

        In this way, beginning with P(O), one first solves for P(delta.gif (63 bytes)t) = {P0(delta.gif (63 bytes)t), Pl(delta.gif (63 bytes)t), P2(delta.gif (63 bytes)t),. . . , PK(delta.gif (63 bytes)t)}, then for P(2delta.gif (63 bytes)t), P(3delta.gif (63 bytes)t), and so on, for the whole period of interest T. This type of numerical solution can be accomplished with the aid of standardized computer programs (such as the IBM Continuous System Modeling Program-CSMP) which are designed specifically for accurate iterative solution of systems of differential equations such as (4.120).
        Once the probabilities Pn(t) have been computed, other quantities of interest can be derived as well. For instance, for the expected number of calls in queue at time t, we have

form4.122.gif (14417 bytes)

Exercise 4.7 Argue the validity of (4.123). Why not use the expression Wq(t) = Lq(t)lamda.gif (291 bytes)(t) in this case?

        In urban problems, the foregoing time-dependent queueing model arises most often in situations where the demand rate, lambda.gif (179 bytes)(t), is periodic with period tau.gif (166 bytes) = 24 hours.) This, for example, would be the case for the toll-booth and police-allocation problems described at the beginning of this section. In that case it is reasonable to expect and it has been shown [KOOP 72] that the numerical solution of (4.120) will also become periodic eventually, independent of the starting conditions P(0), as long as 17

form4.124.gif (3338 bytes)

        In that case, we shall have Pn(t + tau.gif (166 bytes)) = Pn(t) for all t greater than some threshold value. For relatively low utilization systems, the probabilities P,(t) will converge to the periodic solution very quickly (e.g., after a few hours of the first day when tau.gif (166 bytes) = 24 hours.) Convergence, however, cannot be verified until (4.120) have been solved for a second (or third, or more, if necessary) day.
       Although, in order to obtain numerical solutions of (4.120) one must naturally have a finite number (= K + 1) of equations, one can still use a trial-and-error approach to obtain solutions for cases where no calls/users can be turned away [provided that (4.124) holds]. All one has to do is specify K to be sufficiently large so that at no time does Pk(t), the probability of a full system, exceed some acceptable value [e.g., Pk(t) < 10-4 for all t]. Problems with K as high as 600 have been solved at reasonable computer cost [HENG 75]. An application of the M/M/m time-dependent model to the deployment of police patrol cars through the day in New York City is described in [KOLE 75].

17 If (4.124) does not hold, the queueing system will eventually become saturated.