IFSM 300 – Class 24

April 24, 2002

Preliminaries

  • Assignment 24: read chapter 15.
  • Homework 6 due Monday, May 6. Problems to be announced.
  • Class Web site reminder: http://www.gl.umbc.edu/~rrobinso/

The Queueing System

  • Complete notes below. Summary here.
  • Introduction
  • Table for the basic single-server model.
  • Probability of waiting.
  • Probability of idle service facility.
  • Mass function for number of customers in the system.
  • Mean number of customers in the system.
  • Mean time a customer spends in the system.
  • Little’s Law.
  • Mean time in the queue.
  • Mean number of customers in the queue.
  • Little’s Law again.
  • Example – the Ultimate Burger Restaurant.

Comparative Analysis

  • Complete notes below. Summary here.
  • See the procedure summary, page 772.
  • Refer to Increasing the Service Level, situation 15.3, page 770.
  • In this example, we compare the original system with two possible revised systems. The measures of effectiveness we compare are displayed in two tables:
  • Performance measures (probabilities and means) – table 15.8, page 770.
  • Costs – table 15.9, page 772.

Millionaire Q1

The performance measures for a queueing system apply when the system reaches steady state. In a simple (M/M/1) system, steady state will be achievable only when:

  1. The Poisson process describes arrivals and service.
  2.  = .
  3.  < . (!!)
  4.  > .

Millionaire Q2

In an M/M/1 model, when  and  change so as to come closer together in value, the average length of the line in the system:

  1. Stabilizes.
  2. Becomes longer. (!!)
  3. Becomes shorter.
  4. Is not defined.

Millionaire Q3

A basic result for the M/M/1 model is Pn = (/ )nP0 . This probability mass function tells us:

  1. The probability that n customers will arrive in the next hour.
  2. The probability that n customers will be served in the next hour.
  3. The probability that n customers are in the line, not including the customer being served.
  4. The probability that n customers are in the line, including the customer being served. (!!)

Millionaire Q4

The average (mean) number of customers in an M/M/1 system, found from the probability mass function Pn , is the same as:

  1. Lq .
  2. L . (!!)
  3. Wq .
  4. W .

Millionaire Q5

Little’s law, a fundamental relationship that applies to various kinds of queueing models, is:

  1. L =  - W.
  2. L = /W.
  3. L = W. (!!)
  4. L =  + W.

Millionaire Q6

In an M/M/1 system, the fraction of time more than 3 customers are in line (including the customer being served) is:

  1. P0 + P1 +P2 +P3 .
  2. (P0 + P1 +P2 +P3) – 1 .
  3. 1 + (P0 + P1 +P2 +P3) .
  4. 1 - (P0 + P1 +P2 +P3) . (!!)

Notes: The Queueing System

Introduction. With the descriptions of arrivals and service stipulated as covered previously, we are now able to derive much information about this M/M/1 (“basic, single-server”) queueing system.

The information we derive applies to steady state – that is, to equilibrium, not to transients such as occur when you start the system or close it. To achieve a steady state, the mean service rate must be strictly greater than the mean arrival rate; we’ll return to this subject later.

Table for the Basic Single-Server Model. The specific queueing-system information on which we shall focus is summarized in Table 15.7, page 769, shown below (at the top of the next page).

We’ll go through the formulas in the table, deriving each and giving a brief numerical example of each. To avoid mathematical complications, we’ll review derivations most of which are motivating or “heuristic” rather than mathematically rigorous. Along the way, we’ll include an important topic not in the table: Little’s Law. And we’ll come back to the subject of the mean service rate having to be strictly greater than the mean arrival rate. After all of that, we’ll go through a full sample problem: the Ultimate Burger Restaurant. Finally, we’ll view an example of using the basic model to compare improvement alternatives.

Probability of Waiting for Service. In our notation, let’s shorten Pr for probability to simply P. And let’s attach a subscript to indicate the event to which the probability applies.

For instance, to get started, define

PW – Pr {arriving customer must wait before receiving service}

= Pr {server is busy when customer arrives}

= Pr {system already contains at least one customer}.

We want a formula for PW based upon things we know. At this stage, what we may assume we know are the mean (average) arrival rate  and the mean service rate  .

Consider this “heuristic” (nonrigorous) way of analyzing the action. We work with the averages, to see what would happen if arrivals and service completions took place in the average amounts of time. To parallel the numerical examples in the book, let  = 4 customers per hour arriving and  = 5 customers per hour being served when the server is busy (continued on the next page, after table 15.7):


Arrivals

Number of customers arriving per hour / Time between one arrival and the next
Numerical: 4 customers per hour / Numerical: ¼ hour (15 minutes)
Symbolic:  / Symbolic: 1 / 
Service
Number of customers served per hour / Time between one service and the next (time to serve one customer)
Numerical: 5 customers per hour / Numerical: 1/5 hour (12 minutes)
Symbolic:  / Symbolic: 1 / 
Continuing with our description of average action, and referring to the summaries of arrivals and service (above), because service rate  is larger than arrival rate , and therefore the time to serve a customer 1 /  (12 minutes) is less than the time between arrivals 1 /  (15 minutes), no waiting line develops. An arriving customer is served immediately. For the server, the time between arrivals consists of:

Server’s Timeline

New customer arrives /
Server busy
serving customer /
Server finished
and thus idle / Next customer arrives
time 0 / 12 minutes
(1/5 hour) / 3 minutes
(1/4 hour – 1/5 hour) / 15 minutes after time 0
( ¼ hour)
1 /  (hours) / 1 /  - 1 /  (hours) / 1 /  (hours)
From this, we see that the fraction of time the server is busy is

(time serving) / (time between arrivals) = 12 minutes/15 minutes = 0.80;

in other words, (0.80)(100) = 80 percent of the time.

If we express this in symbols, the fraction of the time the server is busy is

(time serving) / (time between arrivals) = (1/) / (1/) =  / .

The fraction of the time the server is busy corresponds to the probability the server will be busy when an arrival occurs. Thus, if this conclusion can be confirmed by a rigorous derivation (it can), we have found that

PW =  / .

In the book, the ratio  /  is called the “utilization factor.”

Probability That Service is Idle. Once we know PW, the next probability we want may be derived easily, and rigorously in this case. Define

P0 – Pr {server is idle when customer arrives}

= Pr {arriving customer is served immediately}

= Pr {system contains no customers}.

We label this “P sub zero” because it is the probability that zero other customers will be in the system at the time the new customer arrives.

With only two possibilities – having to wait and not having to wait – we know that
Pr {customer does not wait} = 1 – Pr {customer must wait} = 1 – ( / ).

Therefore,

P0 = 1 – ( / ).

In our ongoing numerical example,

P0 = 1 – (4/5) = 1/5 = 0.20 (or, 20 percent of the time).

Probability Mass Function for Number of Customers in the System. The third line of table 15.7 shows the most important result so far: a probability mass function of the number of customers “in the system,” meaning in the queue (waiting line) plus being served.

Here is the whole-queueing-system counterpart of the Poisson mass functions that assign probabilities to the number of customers arriving in time T and being served by a busy server in time T. As we shall see, however, this mass function is different. Its mathematical form is one we have not yet seen. And it does not include a selected time T.

To derive the mass function, we’ll follow short-cut reasoning known as stochastic balance. The idea is similar to the “out = in” treatment of intermediate, pass-through nodes in an LP network-flow model. I’ll just sketch the idea, nonrigorously.

Let’s ask: at what rate do customers arrive at an empty system? We find the answer by adjusting the rate at which customers arrive in general so as to reflect the percentage of time the system is empty. Specifically,

(mean rate of arriving at an empty system)

= (mean arrival rate)(fraction of time system is empty)

=  P0 .

Now let’s ask: at what rate do customers leave a system that contains only one customer? We adjust the rate at which customers leave in general so as to reflect the percentage of time the system contains one customer:

(mean rate of leaving a system that contains one customer)

= (mean rate of leaving)(fraction of time system contains one customer)

=  P1 .

Since the system is in steady state and therefore, on average, not gaining or losing customers, it should be true that

(mean rate of increasing from 0 to 1 customers in the system)

= (mean rate of decreasing from 1 to 0 customers in the system).

As shown above, this implies  P0 =  P1 , which can be written

P1 = ( / ) P0 .

Similarly, it should be true that

(mean rate of increasing from 1 to 2 customers in the system)

= (mean rate of decreasing from 2 to 1 customers in the system).

This produces  P1 =  P2 , which we combine with P1 from above to obtain

P2 = ( / ) P1 = ( / )[( / ) P0]

= ( / )2 P0 .

Since the same idea applies to rates up and down between any two adjacent levels of

(n – 1) customers and n customers, we conclude that

Pn = ( / )n P0 , n = 0, 1, 2, …

This probability mass function assigns probability to the total number of customers in the system, waiting and being served. Its form is not Poisson. It is instead “Geometric,” which is the discrete-variable equivalent of the exponential density function of a continuous variable. Like the exponential density, it is memoryless.

Numerical examples of Pn versus n, for  = 4 and  = 5, are shown in table 15.6 of the book, page 768. The following illustrate the computations with three values of n (remember that P0 = 1 - /):

P0 = ( / )0 P0 = (1)(1 – 4/5) = 1/5 = 0.20

P1 = ( / )1 P0 = (4/5)(1/5) = 4/25 = 0.16

P2 = ( / )2 P0 = (4/5)2(1/5) = 16/125 = 0.128

The moments of this Geometric probability mass function of the number of customers in the system turn out to be:

_

mean n =  / ( - ) = 4/(5 – 4) = 4/1 = 4 customers in the system

variance 2 =   / ( - )2 = (5)(4) / (5 – 4)2 = 20/1 = 20 (customers)2

standard deviation  =  2 =  20 = 4.47 customers.

Mean Number of Customers in the System. Moving to the fourth line of table 15.7, define:

L – mean number of customers in the system (waiting and being served).

_

This is exactly the same as n, the mean n from the probability mass function Pn. We are just changing the notation to the symbol L, a standard notation in the queueing community. Thus

L =  / ( - ) ,

and in our continuing numerical example

L = 4/(5 – 4) = 4 customers in the system.

Note that while the actual number of customers in the system at any particular time always would be an integer, the mean (average) number need not be, and, unlike this example, probably won’t be, an integer.

Why No Steady State When  = ? The test to check that our system will achieve steady state, rather than contain a queue that grows indefinitely, is  >  . We might well ask why, since  =  falls on the boundary, we can’t also have steady state when  =  .

Conceptual explanations are obscure. But a technical explanation is quite clear. Consider the formula L =  / ( - ) . When  >  the denominator is positive and therefore L is positive. Imagine the service rate  slowing down to draw closer to the arrival rate . As this happens, the denominator becomes smaller and smaller, and thus L, the average number in line, grows larger and larger. In mathematical jargon, as the service rate moves extremely close to the arrival rate, L “blows up” giving us an average line length that goes out the door and around the world. Moreover, if we should reach the point where the service rate is precisely the same as the arrival rate, then  -  = 0 and L is no longer “defined” because division by zero is not a defined operation.

Why Isn’t the Average Line Length Zero? Another question we might ask is why the average line length L is positive, instead of zero, when we have the required steady-state condition  >  . In the heuristic reasoning that enabled us to derive PW, we saw that on average the server is busy only part of the time (an interval of duration 1/) and is idle the rest of the time (an interval of duration 1/ - 1/) . This suggests that the line length, on average, will be zero because, on average, each arriving customer is finished being served before the next customer arrives.

The answer illustrates the point that you must be cautious using heuristic logic. The “average behavior” concept that works for PW does not work here. The reason is that departures from average are the underlying cause of a positive L. That is, a line builds up when the current arrival rate moves higher than the current service rate, as it will from time to time. Remember that the current arrival and service rates fluctuate. In our system model, the time between one customer and the next, and the time to service a customer, are random variables to which probabilities are assigned by exponential density functions.

Roughly speaking, the average line length is what you would compute by observing the line length periodically (say every five minutes) over a long period, then adding up the observed lengths and dividing by the number of observations. Since the line lengths observed likely will be often positive, sometimes zero, and never negative, we would obtain a positive average unless we had the rare case (like the Maytag repair man) of very few arrivals. We see the same general effect in the formula for L. The ratio  / ( - ) approaches zero only when the arrival rate  becomes extremely small relative to the service rate  .

Mean Time A Customer Spends in the System. Line 5 of table 15.7 addresses the question: How much time does a customer spend in the system (time in the queue, and then time being served, added together)? Again we go through a short-cut heuristic derivation, one that gives us the right answer.

Let’s defineW – mean time a customer spends in the system.

It seems logical that in steady state, on average,

(mean time a newly arrived customer spends in the system until leaving)

= (mean number in line and being served) / (mean number leaving per unit time).

For example, suppose there were 10 in the system and they were leaving at an average rate of 20 per hour. Considering average action, the departures would be 10 the first half hour and 10 more the second half hour, totaling 20. So for a customer at the end of the line of 10 (a line containing that customer plus 9 others), the wait is for the whole group of 10 to leave, with our end-of-line customer being the last to leave. In other words, our end-of-line customer waits a time given by (10 in the system) / (20 leaving per hour) = 0.5 hours.

In this calculation, the numerator is L. It seems at first that the denominator should be . Indeed, we used  for the rate of leaving in our derivation of Pn. Further reflection reveals, however, that our situation here is different. In the derivation of Pn, the departures were from systems containing at least one customer – in other words, systems in which service was busy. That’s not necessarily true now; the server probably will not always be busy.

The departure rate, taking into account the fact that sometimes the server isn’t busy, may be found easily, however, from stochastic-balance reasoning. In steady state, out = in. That is, (mean number leaving per unit time) = ( mean number arriving per unit time).

Thus,

W = L / 

= [ / ( - )] /  = 1 / ( - ) .

So

W = 1 / ( - ) .

In our continuing numerical example, W = 1 / (5 – 4) = 1 hour waiting in the system.

Little’s Law.In the preceding derivation, we saw that W = L /  . When rewritten as

L =  W ,

we have a relationship known as Little’s Law. This relationship offers a quick way to go back and forth between L and W. It turns out to be broadly applicable in various different queueing models, if you define  appropriately (namely, as the mean rate at which customers enter the system).

Mean Time a Customer Waits to Be Served. On the sixth line of table 15.7 we turn attention to the waiting line or queue in the system, not including the customer being served. Define

WQ – mean time a customer spends in the queue, waiting to get served.

Because

( time in the system) = ( time in the queue) + (time being served),

and because the mean of a sum of random variables is equal to the sum of the means, we have

(mean time in the system) = (mean time in the queue) + (mean time being served),

W = WQ + (1 / ) .

Therefore

WQ = W – (1 / ) = [1 / ( - )] - (1 / )

= [ - ( - )] / [( - ) ] ,

which simplifies to WQ =  /  ( - ) .

Example: WQ = 4 / 5 (5 – 4) = 4 / 5 = 0.80 hours in the queue.

Little’s Law For the Queue. We may adapt Little’s Law to the queue by recognizing that the mean rate at which customers enter the queue is the same as the mean rate at which they enter the system:  . So,

LQ =  WQ ,

where we define

LQ – mean number of customers in the queue.

Mean Number of Customers in the Queue. To obtain the formula on the last line of table 15.7, we simply apply Little’s Law:

LQ =  WQ =  [ /  ( - )],

LQ = 2 /  ( - ) .

Example: LQ = 42 / 5(5 – 4) = 16 / 5 = 3.2 customers in the queue.

The Ultimate Burger Restaurant. To gain some experience using table 15.7, let’s work out the following problem:

The Ultimate Burger Restaurant has a single drive-through window. An average of 40 cars per hour arrive at the window. It takes an average of 1 minute to serve a car. Assume that interarrival and service times are exponentially distributed. And assume no restrictions on number of customers or line length.

(a) What type of queuing model applies to this problem? In which table, on what page in our book, do you find a summary of associated formulas?

The last two sentences indicate that the Poisson-process assumptions apply and we may use the unrestricted basic, single-server model: table 15.7, page 769.

(b) Prepare a list of data using standard symbols. If a rate is given, also calculate the corresponding time. If a time is given, also calculate the corresponding rate. Show times in both hours and minutes. Check that the system will reach steady state.

We are given:

Mean arrival rate = 40 cars per hour (this is ).

Mean service time = 1 minute (this is 1 / ).

We calculate:

Mean interarrival time = 1 /  = 1/40 hour, or (1/40)(60) = 1.5 minutes.

Mean service time in hours = 1/60 hour (this is1 /  in hours, needed to obtain ).

Mean service rate =  = 60 cars per hour.

Checking for steady state:

In this case  >  (60 > 40) so the system will achieve steady state.