Waiting Lines

There are many different waiting line situations that are described in POM and QM textbooks. We consider standard models - that is, single-phase queueing models that do not allow feedback, batch arrivals or batch service, balking or reneging. Models of this type are described by a standard notation termed Kendall's notation, although many textbooks avoid this very common notation.Some queueing models allow for the determination of the average cost of operating a queueing system where the cost is the sum of the labor costs and the waiting costs as charged against either the system time (number in system) or the waiting time (number waiting).Data

The framework for waiting lines depends on the specific model to be used. We consider nine models and each of these models can be used with or without costs. In general, the exact data required will vary as the model changes. The models are chosen at the beginning.There are nine models available. Some models are special cases of other models. In particular, all of the single- server models are special cases of the corresponding multiple-server models. The models are listed next. (The names here are the correct, official names -your book is wrong!)	1.	M/M/1 - Poisson arrivals, exponential service times, 1 server

2.	M/D/1 - Poisson arrivals, constant service times, 1 server

3.	M/G/1 - Poisson arrivals, general service times, 1 server

4.	M/ Ek /1 - Poisson arrivals, Erlang-k service times, 1 server

5.	M/M/s - Poisson arrivals, exponential service times, 1 or more servers

6.	M/M/1 with a finite queue (or finite system) size

7.	M/M/s with a finite queue (or finite system) size

8.	M/M/1 with a finite population.

9.	M/M/s with a finite population

The first parameter in the notation refers to the arrival process. The M stands for Memorylessness , which means a Poisson arrival process. The second parameter refers to the service process. The M again stands for memoryless which means that the service times follow an exponential distribution. The D stands for deterministic which is used when service times are constant (always the same). The G stands for general and the Ek stands for Erlang-k distribution. The third parameter is the number of servers (also called channels). Note that s can be set to one in the M/M/s models to solve the M/M/1 models.

Data

A sample data screen appears next.

Arrival rate (lambda). Every queueing system must have a customer arrival rate. This number is a rate, which means that a time unit (hour, day, etc.) is associated with the arrival rate. This is critical because the time unit must match the time unit of the next parameter.

Service rate (mu). The number to be entered is the rate at which individual servers process customers. Note that this is a rate. That is, it is common to know the service time. But this time must be converted to a rate and the time unit of this rate must match the time unit of the arrival rate.

Number of servers. The minimum and default value for the number of servers is one.

There are other input parameters for the other models which will be explained in the examples.

Time unit. There is a dropdown box for the time unit. This serves two purposes. One is to remind you that the arrival rate and service rate must both be based on the same time unit. Second, if you select hours then the output display will show 'minutes' and 'seconds'. If not, the output display will show '60*times answer'.

Example 1 - The M/M/1 model

Customers arrive at a rate of 26 per hour according to a Poisson arrival process. There is one server who serves customers in an average time of 2 minutes according to an exponential distribution.The output screen for this system follows. Notice that the arrival rate is entered as 26 as given in the problem statement. The service time of 2 minutes must be converted to a rate of 30 per hour.

Average server utilization. This is the percentage of time that each server is busy on average. In the example, the one server is busy 87 % of the time.Average number in the queue (line). This is the average number of customers who are in the system waiting for service. That is, they have not yet begun their service. In the example, there are 5.63 customers waiting on average.

Average number of customers in the system. This is the average number of customers who are either in line or being served. In the example, there are 6.5 customers in the system on average.

Average time in the queue (line). This is the average time that a customer spends waiting before service begins. The time unit is the same as that of the arrival and service rates. In the example it is .2167 hours.

Average time in the system. This is the average time that a customer spends waiting and being served. In the example it is .25 hoursMany times we want to convert the average waiting and system times from hours to minutes or from minutes to seconds. The average times will be multiplied by 60 or 3600 and the answers will show beside the original averages. The numbers there express the same time but with a unit of minutes, since the original times were in hours.We can list the probabilities (percentage of time) of exactly k customers in the system, the cumulative probabilities of k or fewer customers being in the system and the de cumulative probability of strictly more than k customers in the system.

The screen will appear as follows. For example, the probability that exactly three customers are in the system is .0868, while the probability that three or fewer customers are in the system is .4358. The probability that (strictly) more than three customers are in the system is .5642. Note that these probabilities are available for all models that have exponential ( memoryless ) service times.

Example 2 - the M/D/1 model.

We have left the data the same as the previous example but changed the model and solved the problem. The solution screen follows.

The output format is the same. Because the model has changed, some of the results have changed. In particular, the number of customers in line is 2.8167 rather than the 5.63 from the M/M/1 system. (The number in line and the time in line in a M/D/1 system are always half of those in an M/M/1 system). Probabilities are not available since the service times are not exponential.

Example 3 - the M/G/1 model

In this model, service times may have any distribution. The input to the routine is not only the mean service rate but also the standard deviation of the service time. The following screen contains all of the information for this example. Notice that there is one extra row for the input. The output is the same. In the example, the mean rate is still 30 customers per hour as before, but the service time standard deviation is .05 hours or 3 minutes.

All service distributions are a special case of the general distribution. A standard deviation of 1/rate yields the exponential distribution. For example, since the service rate is 30, if the service time standard deviation is 1/30 = .03333, the model has an exponential service time distribution.

This is shown in the preceding screen. Notice that the answers are identical to those in example 1 except for roundoff (since we used .0333 rather than 1 /30th exactly).A standard deviation of 0 will yield the constant service time (M/D/1) model. This is displayed next. Compare the results with example 2 which displayed the M/D/1 model.

Example 4 - the M/ Ek /1 model.

Another available service time distribution is the Erlang-k distribution. The screen below exhibits the M/ Ek /1 model and solution. The only difference in the input is that the value for k must be given (rather than no value or a standard deviation).

When k is one, as in the following screen, then we have an exponential distribution. Compare the results with our first example.

Example 5 - The M/M/s Queue

The most basic question in queueing is what will happen if the number of servers is increased. In the screen below we show the output for the original situation except with two servers. Waiting time is now .0077 hours rather than the .217 hours in the original description. To double check the original example, you can use the M/M/s model and enter 1 server.

Example 6 - The M/M/1 system with a finite queue

In this system the number of waiting spaces is finite. The typical example is a telephone system. The extra line of input to this model is the maximum allowable system size. Notice that we said system not waiting. In the following example we have indicated that at most two customers can be in the system. This means that no more than one can be waiting with the second being served. (This is a single-line phone with call waiting.) If there were two servers it would mean that no one can be waiting. Be careful when considering the system size versus the waiting area size.

NOTE: The model is termed a finite queue but it is the system size which is entered into the program. It is NOT the queue size.

Because the system size is limited, it is possible that customers will arrive at the system but be blocked from entering. Therefore, we define the effective arrival rate as the actual number of customers who enter the store rather than arrive at the store. Furthermore, the output displays the percentage of time (probability) that the system is full.

In the example, only 71% of the customers who show up enter the system since customers show up at a rate of 26 per hour but the effective arrival rate is 18.539 per hour. When we display the probabilities as follows we see that 28.69% of the time the system is full (k=2). That is, 28.69% of the time when a phone call is made it receives a busy signal.

Example 7 - The M/M/1 system with a finite population

Typically we assume that the population is infinite. In the following screen we are exhibiting a population of 13 potential customers each arriving at a rate of two times per hour (for a net potential arrival rate of 26, as in the previous examples). This is the arrival rate when they are not in the system. However, from the output it can be seen that each customer averages .088 hours each time he or she arrives. The effective arrival rate is the one arrival per hour times the average number of the 13 who are not in the system. In this example, the effective arrival rate is only 22.1 customers per hour (rather than the potential of 26 arrivals per hour). If service were better, then these customers could arrive more frequently. The screen includes the probability that a customer waits. (This is not the probability that all servers are busy, since arrival rates vary depending on the number in the system.)

NOTE: In this model, the arrival rate to be entered to the program is the arrival rate FOR AN INDIVIDUAL CUSTOMER. In many textbooks, for this model the time between arrivals is given. This time must be converted to an arrival rate. For example, it might be that each of five customers shows up on average every 30 minutes. This must be converted to a rate of 60/30 = 2 per hour (per customer). The program will automatically adjust for the number of customers. Notice that we enter the number 2 as the arrival rate. It is tempting to enter 2*5 =10 but this is incorrect!

Example 8 - M/M/s with costs

The next screen contains an example with costs. Customer costs can be charged against either the time a customer spends in the system or charged against only the time waiting. We charge $2 for each hour the customer waits. This yields a total cost of $2*6.5 customers in the system plus the $4/ hour labor cost for a total system cost of $17 per hour (bottom line in table). Alternatively, we might charge against the time a customer waits. In this case we have 5.633 customers waiting on average multiplied by $2 for a subtotal of $11.26 to which we add the $4 server charge yielding $15.27 as displayed in the second line from the bottom.