Chapter 2

The Basics—Single-Channel, Single-Phase Model

A single line of people waiting for some service is arguably the most common business model on our planet (see Figure 2.1 for a diagram of this configuration). The variations on this simple theme are nearly infinite when you consider the forms that the service can take and the nature of the customers desiring that service.

We will use a coffee shop where customers from different walks of life enter the shop; wait in line; and, when they reach the service window, order anything from a simple cup of coffee to a more complex mixture of coffee and other ingredients to larger orders of multiple combinations of these. To analyze the basic behavior of this model, we must make some assumptions where the full Kendall notation for the model is M/M/1/∞/∞/FCFS:

• The arrival rate distribution is described by a Poisson distribution using an average rate λ, which means that the interarrival times can be characterized by an exponential distribution with an average interarrival time of 1/λ. Interarrival times are independent of the number of customers in the system.
• The service time distribution is defined by an exponential distribution with an average service time of 1/µ, where µ represents the average service rate. Service times are independent of the number of customers in the system.
• The number of channels (servers) is one, and the number of phases in the service is one. We assume here that a single server does everything for the customer in the coffee shop: taking the order, preparing the coffee, and collecting the payment. Obviously, in many coffee shops with a higher volume of customers, more than one person likely performs these activities. We will discuss these complexities in chapter 4.
• The arrival or calling population is infinite in size. This avoids complications introduced by the possibility of having served all available customers.
• The length of the waiting line can be infinite. Although not really possible in real-world situations, this avoids analysis complications introduced by the rare possibility that some customers are blocked from entering the line. We will discuss the effects of limited line lengths in later chapters.
• The priority rule is first come, first served (FCFS).
• Balking or reneging by customers is not considered in the analysis.
• The average arrival rate is less than the average service rate (λ < µ). That is, the utilization factor ρ = λ/µ is less than 1.

This last assumption should be intuitively obvious because the average line length will increase significantly when the arrival rate approaches the service rate, as shown in Figure 2.2.

One thing that is often confusing when reviewing the equations presented by different authors for a given waiting line model is that at first glance they do not always appear to be the same. However, with closer inspection, we can see that one version is equivalent to another version because some author(s) substituted ρ for some combinations of λ and µ or have applied Little’s Law. The different versions are provided here for your reference with what I consider to be the most useful version listed first. The various performance measures for the basic M/M/1 model are listed in the same order in which they will be presented for other waiting line models later in the book.

• Utilization factor: ρ = λ/µ; for a basic M/M/1 model, ρ must be less than 1.
• Probability of 0 customers in the system (this is also the probability that a customer will experience no waiting for service): P₀ = 1 − ρ.
• Probability of exactly n customers in the system: P_n = (1 − ρ)ρⁿ = P₀ρⁿ.
• Probability that the number of customers in the system is greater than k:

  P_n>k = ρ^k+1.

• Probability that the server is busy: P_n>0 = 1 − P₀ = ρ.
• Average number of customers in the system:

  L = λ/(µ − λ) = ρ/(1 − ρ) = λW.

• Average total time customers spend in the system: W = 1/(µ − λ) = L/λ.
• Average number of customers waiting in the queue (not yet being served):

  L_q = ρL = ρλ/(µ − λ) = λ²/[µ(µ − λ)] = ρ²/(1 − ρ) = L − ρ = λW_q.

• Average time customers wait in the queue before being served:

  W_q = ρW = W − (1/µ) = ρ/(µ − λ) = λ/[µ(µ − λ)] = L_q/λ.

The term system applies to not only the number of customers waiting in line but also any customer(s) being served. Also useful to remember is that the sum of all possible probabilities for a parameter must equal 1. This allows you to determine a probability that may be difficult to calculate directly. In such a case, you add together all the other possible probabilities excluding the one you want to determine and subtract that sum from 1. An example of this was shown previously for the probability that a server is busy.

If you observe the formulas for line lengths and waiting time carefully, you can see that the ratio of the average number of people in the system to the average waiting time in that system is equal to the average arrival rate when the system is in a steady-state condition. Expressed in the form L = λW, this ratio is referred to as Little’s Law.¹ This ratio also applies when just considering the number of people waiting in line and the time spent waiting in that line before being served. As we will see in subsequent chapters, Little’s Law applies across a wide range of waiting line models regardless of the probability distributions chosen to represent the arrival and the service rates. Hence, Little’s Law is especially useful for manufacturing applications of queuing analysis where such probability distributions are often unknown.

Another significant observation can be drawn by looking at the formulas for L, L_q, and P₀ that are expressed using only the utilization factor ρ = λ/µ. This means that these values vary only with ρ; that is, as long as the arrival and service rates increase in direct proportion to each other (ρ remains constant), the values for L, L_q, and P₀ will remain unchanged. However, W and W_q will decrease with increasing values of λ and µ. Figure 2.2 shows the value for L versus ρ, and you can see that the line length is essentially flat for ρ < 0.4. In chapter 3, you will see that this characteristic holds true for multiple-channel lines.

You may observe what appears to be an inconsistency in the expressions for L_q, where it is shown as being equal to both ρL and L − ρ. Is this possible? Most textbooks avoid this question by presenting only one version for L_q; however, I include both versions in my class lectures as a check on whether students are reading the material. To answer the question: If both equations are true, then ρL must equal L − ρ. Moving all the L terms to one side of the equation gives the result that L(1 − ρ) = ρ. Dividing both sides by (1 − ρ) gives L = ρ/(1 − ρ), which is the equation for L.

Figure 2.3 shows typical individual waiting times and service (brewing) times along with the number of customers already in the shop when each customer arrives. These values were obtained using a simple Excel simulation program. This set of sample data does not show any values for L that are greater than 5, which could lead a person to assume that the line lengths for the business are not too long. However, subsequent simulation runs using the same interarrival and service time distributions and the same number of customers have demonstrated possible line lengths as great as 14, brewing times as long as 16 minutes, and waiting times up to 20 minutes. To obtain more information regarding the variability of the performance measures, multiple simulation runs are required. These will be explored in detail in chapter 7. You should note in Figure 2.3 that the average for each performance measure depicted rarely occurs, if at all, for any customer. This leads to a very important observation that the average performance values derived from the queuing equations are primarily for the longer-term business perspective and are a very poor indicator of what a typical customer encounters.

As mentioned in chapter 1, an exponential distribution is not the most accurate distribution to represent the service time for this type of business because the minimum service time required for even a simple cup of house coffee is likely to be greater than 30 seconds when the time for payment is included. Yet the simulated data in Figure 2.3 show several occasions when the brewing time is less than 30 seconds (0.5 minute). The longer brewing times shown can be expected when one considers a customer ordering several coffees for a group of people. Perhaps an Erlang distribution with an appropriate k factor would be a better representation for this type of service, as discussed in chapter 4.

Finally, market surveys can provide estimates of how long a line can be before customers looking into the shop are likely to decide to not even enter (balking). For example, let us say that a line longer than 5 people, including the person being served, is a definite turnoff for a potential coffee shop customer. So, given the data for this example, what is the probability of this occurring? Referring to the data in Example 2.1 and using the formula P_n>k = ρ^k+1, where k = 5, we obtain 0.8⁶ = 0.2621 or 26.21%.

Thus, Ken’s Caffeine Fix coffee shop in Example 2.1 is likely to lose at least one fourth of its possible customers. Conversely, the probability that the average number of customers in the shop is 5 or less is 1 − 0.2621 = 0.7379 or 73.79%.