Question

Consider two \(\mathrm{M} / \mathrm{M} / 1\) queues with respective parameters \(\lambda_{i}, \mu_{i}, i=1,2 .\) Suppose they share a common waiting room that can hold at most three customers. That is, whenever an arrival finds her server busy and three customers in the waiting room, she goes away. Find the limiting probability that there will be \(n\) queue 1 customers and \(m\) queue 2 customers in the system. Hint: Use the results of Exercise 28 together with the concept of truncation.

Short answer

The limiting probability that there will be \(n\) queue 1 customers and \(m\) queue 2 customers in the system is given by the formula: \(P_{n,m} = \frac{(\lambda_1 \lambda_2)^{n+m}}{n! \cdot m! \cdot (n\mu_1 + m\mu_2)^{n+m+1}}\) We calculate the probabilities for all possible combinations of n and m, considering that only a maximum of 3 customers can be in the waiting room at a time. After finding probabilities for each combination, we normalize them by dividing each one by the sum of all probabilities, resulting in the limiting probabilities \(P_{n,m}\).

Step-by-step solution

Define Variables and Parameters

Let's represent the limiting probability of having \(n\) customers from queue 1 and \(m\) customers from queue 2 with \(P_{n,m}\). Given that there are two separate queues with their respective parameters: \(\lambda_{i}, \mu_{i}, i=1,2\), our goal is to find \(P_{n,m}\) for each possible combination of n and m.

Main Equation

Based on the results of Exercise 28 and using the concept of truncation, we can use the following equation: \(P_{n,m} = \frac{(\lambda_1 \lambda_2)^{n+m}}{n! \cdot m! \cdot (n\mu_1 + m\mu_2)^{n+m+1}}\)

Determine All Possible Combinations of n and m

Since the waiting room has a maximum capacity of 3 customers, the possible combinations of n and m are (n, m): (0, 0), (1, 0), (2, 0), (3, 0) (0, 1), (1, 1), (2, 1) (0, 2), (1, 2) (0, 3)

Calculate Limiting Probabilities for Each Combination

We need to find \(P_{n,m}\) for each possible combination of values of n and m. We can do this by plugging in the values into the equation for each combination: \(P_{0,0} = \frac{1}{(\mu_1 + \mu_2)^1}\) \(P_{1,0} = \frac{(\lambda_1)^1}{1! \cdot (\mu_1)^2}\) \(P_{2,0} = \frac{(\lambda_1)^2}{2! \cdot (\mu_1)^3}\) \(P_{3,0} = \frac{(\lambda_1)^3}{3! \cdot (\mu_1)^4}\) \(P_{0,1} = \frac{(\lambda_2)^1}{1! \cdot (.\mu_2)^2}\) \(P_{1,1} = \frac{(\lambda_1 \lambda_2)^2}{1! \cdot 1! \cdot (\mu_1 + \mu_2)^3}\) \(P_{2,1} = \frac{(\lambda_1 \lambda_2)^3}{2! \cdot 1! \cdot (\mu_1 + 2.\mu_2)^3}\) \(P_{0,2} = \frac{(\lambda_2)^2}{2! \cdot (2.\mu_2)^3}\) \(P_{1,2} = \frac{(\lambda_1 \lambda_2)^3}{1! \cdot 2! \cdot (\mu_1 + 2.\mu_2)^3}\) \(P_{0,3} = \frac{(\lambda_2)^3}{3! \cdot (3.\mu_2)^4}\) Note that we do not need to calculate probabilities for combinations where total customers are more than 3 since there can be no more than 3 customers in the waiting room.

Normalize Probabilities

Since probabilities must sum up to 1, we need to find the normalization constant C. \(C = P_{0,0} + P_{1,0} + P_{2,0} + P_{3,0} + P_{0,1} + P_{1,1} + P_{2,1} + P_{0,2} + P_{1,2} + P_{0,3}\) Then, multiply each limiting probability we found in Step 4 by the normalization constant C to normalize the probabilities: \(P_{n,m} = CP_{n,m}\)

Key concepts

Queueing Theory

Queueing theory is a mathematical study of waiting lines or queues. This discipline is a critical aspect of operations management, computer science, telecommunications, and many other fields that deal with complex systems and processes. The core objective of queueing theory is to predict queue lengths and waiting times, which are of great importance in resource allocation and service capacity planning. A common model used in queueing theory is the M/M/1 queue, which represents a single-server queue with exponential service times and a Poisson arrival process. The 'M' stands for 'memoryless', indicating that the arrival times and service times are exponentially distributed, and each event in the queue (arrival or departure) does not depend on previous events. This simplification allows for the derivation of many useful results regarding system characteristics such as average queue length, average waiting time, and the distribution of the number of customers in the system. The exercise provided involves a modification to the standard M/M/1 queue, where two such queues share a limited waiting space, a real-world constraint that many service systems could face.

An understanding of M/M/1 queues is essential as it provides the building blocks for analyzing more complex queueing systems, which can have multiple servers, various types of arrival and service processes, and different queue disciplines (e.g., first-come-first-served, priority). These systems are often analyzed using state probability distributions to understand the behavior of the queue over time and to calculate performance metrics such as utilization and throughput.

Limiting Distribution

The concept of a limiting distribution in queueing theory refers to the stable state probabilities as time approaches infinity. In other words, the limiting distribution describes the long-term behavior of a queueing system, assuming it reaches a steady-state where the arrival and service rates remain constant over time. This is crucial for analyzing systems where we assume the queue has been running for a sufficient duration and will continue running for an indefinite period.

The exercise showcases the application of the limiting distribution by exploring the probabilities of different numbers of customers being present in a shared waiting room for two queues. When these probabilities stop changing over time, they have reached their limiting values, which are used to make predictions about future system states. For M/M/1 queues, the limiting distribution can often be represented by an exponential or geometric series due to the memoryless property of the underlying processes. Calculating the limiting distribution provides insights into the probability of finding the system in any given state at a random time and is fundamental in assessing system performance and identifying bottleneck potentials.

Truncation

Truncation in queueing theory refers to a situation where the state space of a queue is limited. In a practical scenario, queue sizes can't grow indefinitely due to physical or resource limitations. For example, a waiting room might have a limited number of seats, or a computer server may only be able to handle a finite number of concurrent tasks. In these cases, when the maximum capacity is reached, new arrivals are either turned away or lost, a concept commonly referred to as 'blocking'.

In our exercise, this concept is illustrated by a waiting room that can hold at most three customers. By applying truncation to the M/M/1 queue model, we can forecast the probabilities for every feasible combination of customers in the two queues without considering more customers than the waiting room can handle. This leads to a truncated state space, requiring adjustments to the standard M/M/1 model, which assumes an infinite capacity. The truncation forces us to re-evaluate the probabilities and normalize them to ensure they sum up to one, reflecting a complete probability distribution across all possible states. This practice is common in systems with finite buffers and is critical for accurately modeling and predicting the performance of such systems.