Utilization, Queue Length, and WIP Limit

Chris, a fresh college graduate with a double major in Mathematics and Statistics, is planning to open a rent-a-car for business in the neighborhood. He lives in a small town with no local rent-a-car shop for business. He estimated that 30 local companies might take advantage of his rent-a-car. He estimated that there is a 0.1 probability that business needs to rent a car service. Based on this information, the binomial Distribution is a suitable model because that only shows two states, whether companies use rent-a-car services.?

Binomial Distribution

If there are N possible outcomes and p is the probability of an event occurring, then the chance of k events will be calculated by Binomial Distribution.?

Let's call this equation (A). Suppose there are 30 total customers, and there is 0.1 probability that a customer will come to the shop. What is the likelihood that four customers will enter the shop?

In other words, there is a chance of 17.7% that four customers use his rent-a-car service.?

Poission Distribution

Soon he realized that the problem was that it was not mentioned how long it would take to get four customers based on the previous model. In addition, he doesn't know how many customers he may have in advance. It can be a huge number, for example, business from the neighboring town or even individual tourists, and he doesn't know the probability for the customer. The only information he has is the rate for the customer. In other words, how many customers arrive at some time; for example, he may have 15 customers per week. It means that he potentially has more than 30 clients and potentially tends to infinity. We know that the probability of getting a customer is?

Here "n" is the total number of customers, "k" is the number of customers who uses Chris's services, and "p" is the probability that the customer uses Chris's services. If the number of customers increases, the probability goes down, and if Chris has infinite customers, the probability goes to zero.

It means n (number of customers) tends to infinity, then p (probability) tends to zero.?

When n tends to infinity and p tends to zero. Let's put these limits on the Binomial Distribution formula, our equation (A), and let's call it equation (B)

Put

in equation (B),?where lambda is the expected number of customers.?

The formula above is a probability density function for Poisson Distribution. Let's call it equation (C)

Exponential Distribution

Now he started looking at the problem from another dimension. What is the first customer's arrival time if they follow the Poisson Distribution? It is used to predict the amount of time until the next event. Because time is continuous, this is a continuous distribution. Like any other continuous distribution, the probability of any point is zero because for any function.

Therefore, it needs to be calculated on the interval.

If the first event happens after "k" time, it means?

Because there is no event happening until time "k" it means

For nothing to happen till time k, it would be

This is a Cumulative Density Function (CDF). To get the Probability Density Function (PDF), take a derivative of this.

The formula above is a probability density function for Exponential Distribution. Let's call this equation (D)

Queue Length

For the past few weeks, Chris's business has grown a lot, and as a result, there is always a queue in front of his counter. He is trying to find out why and how he can improve the situation. His initial thoughts are if the rate of serving the existing customer is faster than the rate of arriving customers, then there shouldn't be any queue. He is very sure that he is serving customers faster than they come, but still, there is a queue, and he is trying to investigate the issue more by wearing his Mathematical cap.

Single Server Exponential Queue

Chris is the only one serving the client; in other words, there is only a single server, and arrivals of customers are using a Poisson Process of rate lambda. The arrivals of customers are independent of each other, and the time between them is an exponential random variable with a mean of 1/lambda. It is also written as M/M/1 in Kendall's notation, named after British Mathematician David Kendall (Kendall, 1953). Here the first M, Markovian or memoryless, is the arrival process. The second M, Markovian or memoryless, is service time distribution, and 1 represents the total number of servers. Arrival is a Poisson Process, and service time distribution is exponential service time.?

Here a(t) is the arrival rate of the customers, and b(t) is the service rate. Traffic intensity is the arrival rate over the service rate.

Suppose 0 is the first item, and P0 is the proportion of time in state 0. There can't be any item left from state 0 because there is no item in the queue. P1 is the proportion of time the system has exactly one customer. Here is the relationship between these

For any other state other than 0, it would be

It is a flow-balance equation; in other words, "in a steady state, the rate of transition out of a given state must equal the rate of transition into that state" (Shortle et al., 2018)

Let's rewrite the flow-balance equation.

Now let's try to find out the value of the second term

In general, it would be?

Let's call this equation (E). The sum of all probabilities must be equal to 1. It means that

It is a geometric series, and if the ratio of arrival to departure is less than 1, its sum would be

Put this in equation (E).?

Let's write it in the form of utilization (traffic intensity/capacity)

Let's calculate the length of the queue.?

It is again a geometric series with a ratio is less than one. Its sum would be

This equation explains the relationship between Utilization and Queue Length. Here is a graphical representation of this.?

He learned an important lesson: As long as the arrival rate of customers to the departure rate of customers is less than 85%, the customer queue is manageable. However, if it is higher, the queue length becomes larger. This relationship is also described as principle Q3, "The Principle of Queuing Capacity Utilization: Capacity Utilization increases queue exponentially" by Donald G. Reinertsen (Reinertsen, 2009).

Interestingly, the relationship is also valid in the reverse direction. It means that we can not only calculate the queue length by utilization, in other words, the capacity of the queue, but we can calculate the queue utilization by the queue length.?

The following graph can show this relationship

What can Chris do with this information? If he wants to make his utilization manageable, he can control the queue length. Chris can handle the queue length by putting Work In Progress Limit (or WIP Limit) to manage the utilization of the queue. Therefore it is necessary to put the WIP limit to work in smaller batches to avoid full utilization of the server, in other words, reaching its capacity.

Another critical question is why we even want to do this. It is because if queue utilization is greater than or equal to one, the queue becomes unstable. In other words, the queue length and wait time both become infinity. In simple words, if serving the customer rate is slower than the customer arrival rate, the queue will become longer and longer, and the customer waiting in the queue will keep waiting for longer.?

References

Kendall, D. G. (1953). Stochastic Processes Occurring in the Theory of Queues and their Analysis by the Method of the Imbedded Markov Chain. The Annals of Mathematical Statistics, 24(3), 338–354. https://doi.org/10.1214/aoms/1177728975

Reinertsen, D. G. (2009). The Principles of Product Development Flow: Second Generation Lean Product Development (1st ed.). Celeritas Pub.

Shortle, J. F., Thompson, J. M., Gross, D., & Harris, C. M. (2018). Fundamentals of Queueing Theory (Wiley Series in Probability and Statistics) (5th ed.). Wiley.