Home Business & Finance The mathematics of financial models

# M/M/fr Queue

In this section, I will generalize the discussions for the M/M/l and M/M/2 queue by considering the instance when there are k (where k = 1,2,3,...) servers to attend to the queue.

Probability of Having n Customers in the Queue Using similar notations, one can arrive at the following analogs of equations (9.5a) to (9.5c). (9.8a) (9.8b)  (9.8c) (9.8d)

Taking limits as , one can arrive at the following analogs of equations (9.6a) to (9.6c). (9.9a) (9.9b) (9.9c)

As earlier, for the queue to reach stationarity conditions (i.e., be time independent and stabilize), one needs to set equations (9.9a) to (9.9c) to 0. Doing this yields (9.10)

where p was defined as for the M/M/l queue and Expected Waiting Time To find the expression for the expected waiting time, I will, as in the M/M/2 queue, first find the expected number of customers in the queue waiting to be served. To do this, observe that Applying equation (9.7c), it readily follows that the (9.11)

Percentage Of Downtime To calculate this quantity, it is important to first observe that the servers would have nothing to do if there is no one in the queue. The percentage of downtime is simply given by the expression P0. Furthermore, the percentage of time the servers would all be busy is given by the expression # Numerical Example

To illustrate, consider the instance when the service rate of any passenger agent in an airport is 8 passengers/hour, while the arrival rate of the passengers is 6 passengers/hour. Using equation (9.11), one can obtain the expected waiting time in Table 9.5 for a varying number of passenger agents.

As can be seen from Table 9.5, the waiting time for a newly arriving passenger drops drastically from 30 minutes to about 9 minutes by making two passenger agents available to serve the queue. Furthermore, the relative

TABLE 9.5 Impact of the Number of Servers on Waiting Time

 Number of Passenger Agents Expected Waiting Time (minutes) 1 30.00 2 8.73 3 7.65 4 7.52 5 7.50 FIGURE 9.4A Probability of Moving from State 0 to State 1

value gained by adding a subsequent passenger agent is very small compared to that gained by moving from one to two passenger agents. In addition to this, it can be shown that when there is one passenger agent the percentage of downtime is about 25 percent, and when there are two passenger agents downtime is about 45 percent.

Since there are costs associated with the deployment of passenger agents, the airline has to decide if it is worthwhile to have passenger agents possibly idly waiting for passengers (a common scene in the airport when there is very little traffic) and incurring unnecessary overhead costs or if it is more worthwhile to reduce the costs by bringing more agents in only if they can be put to work immediately upon arrival.

It is in this space where the notion of real options becomes useful, as the airline needs to decide how to optimally expand the operation to bring in more passenger agents so as to minimize the cost of the operations, while ensuring that any waiting time constraints are satisfied.

As outlined in equations (9.3a) and (9.3b) for the M/M/l queue, the probabilities associated with jumps to different states over a time interval Δt are given in Figures 9.4a and 9.4b.

Figure 9.4a shows the generation of states (with the appropriate probabilities) starting with 0 passengers in the queuing system, while Figure 9.4b shows the generation of states (with the appropriate probabilities) starting with an arbitrary state i (where i = 1, 2, 3, ...) when the expressions for , and α are given as follows: (9.12a) (9.12b) (9.12c) FIGURE 9.4B Probability of Moving from State i to State i + 1

Using the transition probabilities in equations (9.12a) to (9.12c), one can now construct the states that the tree transverses, as shown in Figure 9.5.

To apply the notion of optionality, one has to first create the state tree for the period of time the queue is operational. Once that is done, one can create a payoff tree (as in the GMAB rider) to rollback to obtain the present value of the decision. While the above approach seems theoretically feasible, implementing this in practice may not be as straightforward, due to the complication introduced by the path dependency, especially when the number of servers in the queue keeps increasing. Given this backdrop, I will instead try to put bounds on the value of the exercise rather than try to implicitly value this option.

Before the advent of fast computers, queuing theory, like many other disciplines, caught the attention of operational researchers and probabilists who spent their time and energy deriving asymptotics based on queue stationarity so as to obtain analytic solutions to compute the metrics of interest. Clearly, if the queue is only operational for a finite time (in which case the arrival rate can be higher than the service rate), the formulae derived earlier FIGURE 9.5 Transition of States in a Queue FIGURE 9.6 Transition of States in a Queue (Unlinked)

may not be a great approximation to the problem at hand. As a consequence, it is important to first question the validity of the results obtained for the M/M/k queue in finite time. Once this question is answered, one needs to incorporate the notion of optionality into the managing of the operation (i.e., bringing on an additional passenger agent as and when required so as to minimize the cost and keep the expected waiting time within predefined constraints).

To answer the question of validity in finite time, it may be easier to first revisit Figure 9.5. Due to the nature of the path dependency associated with state tree in Figure 9.5, it is best (for the purposes of illustration) to unlink the branches of the tree to more clearly exhibit how the states evolve during the time the queue is operational. Figure 9.6 illustrates how the state tree above looks when unlinked.

Figure 9.6 gives a better sense of how the states (number of people in the queuing system) evolve in practice so as to be able to implicitly calculate the waiting time among other things. It is much easier to use a simulated queue (like that discussed in Chapter 4) to entertain the properties outlined in Figure 9.6 – including the consideration of having more than one passenger agent. In fact, it is even possible to simulate this queue in finite time when the service rate is slower than the arrival rate (an assumption that is NOT used for queue stationarity). Table 9.6 shows the absolute value of the relative error when approximating the expected waiting time in a queue that is only operational for 30 minutes, using equation (9.11) as compared to using the simulation algorithm in Chapter 4 to simulate this queue for a period of 30 minutes after which no arrivals are allowed (i.e., the queue is closed) for an M/M/l queue.

TABLE 9.6 Relative Error When Estimating the Expected Waiting Time for an M/M/l Queue As can be seen from Table 9.6, the higher the arrival rate relative to the service rate, the greater the relative error. Clearly, the greater the operational time of the queue the better the convergence to equation (9.11). It is also interesting to see how robust equation (9.11) is for well-behaved queue characteristics (i.e., where the service rate is higher than the arrival rate). While Table 9.6 shows the absolute value of the relative error associated with the analytical expected waiting time expression for a finite queue operating time, the results tend to be consistent across different metrics (e.g., expected number of people served).

Assume that the queue in the airport is run for a finite time, only the first 100 passengers are given a discounted price on the flight, provided they come within the hour. It can be shown that the costs for running the ticketing operation when the airline is forced to hire one, two, three, or four passenger agents at the start of the queue for a period of 60 minutes are \$103, \$82, \$89, and \$102 respectively, where I have used the following assumptions:

■ The cost associated with hiring a passenger agent is a base rate of \$20/hour.

■ Passenger agents need to be hired for an hour.

■ The airline is charged \$100/hour for the time the ticketing desk is opened.

■ The arrival rate of the passengers is 10 per minute.

■ The service rate is two per minute.

Hence, it is more cost efficient to hire two passenger agents up front. If the airline only hired one passenger agent for the entire hour and then brought on an additional agent as needed (i.e., no additional holding time) so that the queue is not jammed up and costs are managed, it can be shown that the cost associated with operating the queue when there are one, two, three, and four passenger agents now become \$103, \$70, \$60, and \$54 respectively. These results are captured in Figure 9.7.

Figure 9.7 also contains the results associated with a 10-minute holding time that were run for the purposes of comparisons. The results associated with a 60-minute holding time and 0-minute holding time do not contain any form of optionality. The reason is that in the instance of the 60-minute holding time, servers are hired at the start of the queue and kept for a duration of the entire 60 minutes, whereas in the instance of 0-minute holding time, the servers are only brought and used when necessary – in the process demonstrating the upper and lower bounds associated with the flexibility options. To obtain the results associated with a 10-minute holding time, I assumed that whenever the additional server is brought, the server is kept for a period of 10 minutes before being released (where the condition of release FIGURE 9.7 Impact of Server Holding Time on Operational Costs

is strictly predicated on if there is any passenger waiting to be served). As the astute reader realizes, it is more correct to implement the decision of deciding whether to bring a passenger agent onboard for 10 minutes based on the time remaining and the expected queue length over the remaining 10 minutes – something that can only be done with the aid of decision trees, like that illustrated in Table 9.4, which has been left as an exercise for the reader.

•  It is important to note that in obtaining the expression for P0, since the infinite series has not been collapsed to an analytic function, no assumption was made about p.
•  These are simply the values of P0 in equation (9.10) in the instance when k = 1 and 2.
•  The state transition probabilities provided in equations (9.12a) to (9.12c) are all accurate for a very small Δt.
•  The reason for this stems from that fact that if the asymptotic results are indeed accurate, in quantifying the optionality associated with bringing on the additional server, one can resort to the use of existing expressions related to expected waiting time. Found a mistake? Please highlight the word and press Shift + Enter Subjects