Queueing Models
- Customers arrive in some random manner to a service station
- Upon arrival they may have to wait in a queue
- When it is their turn, they are served, which takes some random amount of time
- Once they are done, the leave the system
Example questions:
- How many customers are in the system on average?
- How many customers are in the queue on average?
- How much time does a customer spend in the system (again, on average)?
- …
Some Fundamental Quantities
- \(L\): the average number of customers in the system
- \(L_Q\): the average number of customers in the queue
- \(L_S\): the average number of customers being served
- \(W\): the average amount of time a customer spends in the system
- \(W_Q\): the average amount of time a customer spends in the queue
- \(W_S\): the average amount of time a customer spends being served
- \(N(t) = {}\) the number of customers that arrived by the time \(t\)
- \(\displaystyle\lambda_a = \lim_{t\to\infty} \frac{N(t)}{t} = {}\) the customer arrival rate
- \(D(t) = {}\) the number of customers that departed by the time \(t\)
- \(\displaystyle\lambda_d = \lim_{t\to\infty} \frac{D(t)}{t} = {}\) the customer departure rate
Cost Identities
Suppose customers pay to the system according to some rule.
Define:
- \(E(t) = {}\) the total earning of the system by time \(t\)
- \(\displaystyle E_r = \lim_{t\to\infty} \frac{E(t)}{t} = {}\) the average rate at which the system earns.
- \(S = {}\) the average amount an entering customer spends
Basic cost identity:
\[E_r = \lambda_a \times S\]
Different Payment Rules
- Customer pays $1 for each time unit spent in the system:
- Customer pays $1 for each time unit spent in the queue:
- Customer pays $1 for each time unit spent being served:
Steady-State Probabilities
Let \(X(t) = {}\) the number of customers in the system at time \(t\).
For \(n \ge 0\), define the limiting (or long run, or steady state) probability of exactly \(n\) customers in the system as
\[P_n = \lim_{t\to\infty} \operatorname{P}(X(t) = n)\]
Define
- \(a_n = {}\) the proportion of customers that find exactly \(n\) other customers in the system when they arrive.
- \(d_n = {}\) the proportion of customers that depart when there are exactly \(n\) other customers in the system.
Steady-State Probabilities (cont.)
Define
- \(A_n(t) = {}\) the number of customers that found exactly \(n\) customers in the system upon arrival.
- \(D_n(t) = {}\) the number of customers that departed when exactly \(n\) customers were in the system.
- \(\displaystyle \lambda_{a,n} = \lim_{t\to\infty} \frac{A_n(t)}{t} = {}\) the rate at which customers arrive to find \(n\) customers in the system.
- \(\displaystyle \lambda_{d,n} = \lim_{t\to\infty} \frac{D_n(t)}{t} = {}\) the rate at which customers depart while leaving \(n\) customers in the system.
\[a_n = \frac{\lambda_{a,n}}{\lambda_a}\]
\[d_n = \frac{\lambda_{d,n}}{\lambda_d}\]
One at a time arrivals and departures
Suppose customers arrive one at a time and depart one at a time.
Then \(\lambda_{a,n} = \lambda_{d,n}\) and \(a_n = d_n\) for each \(n\).
Poisson Arrivals
If the arrivals of the customers form a Poisson process, then \(a_n = P_n\).
Single Server Exponential System (M/M/1)
- Arrivals are according to a Poisson process with rate \(\lambda_a\).
- Service times are independent exponential variables with rate \(\lambda_s\).
- There is one server with one queue.
This is a process with states \(n = 0, 1, \ldots\), where \(n\) is the number of customers in the system.
Define
- \(E_n(t) = {}\) the number of times the system entered state \(n\) by the time \(t\),
- \(L_n(t) = {}\) the number of time the system left state \(n\) by the time \(t\).
Define \(\displaystyle e_n = \lim_{t\to\infty} E_n(t)/t\) and \(\displaystyle l_n = \lim_{t\to\infty} L_n(t)/t\)
Balance Equations
For each \(n\), \(l_n = e_n\).
Remember \(\displaystyle P_n = \lim_{t\to\infty} \operatorname{P}(X(t) = n)\) is the proportion of time the system is in state \(n\).
\[\lambda_a P_0 = \lambda_s P_1\]
\[(\lambda_a + \lambda_s) P_n = \lambda_a P_{n-1} + \lambda_s P_{n+1}\]
\[P_n = \left(\frac{\lambda_a}{\lambda_s}\right)^n\left(1 -
\frac{\lambda_a}{\lambda_s}\right) \text{ for } n = 0, 1, \ldots\]