The Central Idea
A basic queue has three ingredients:
- an arrival process;
- a service process;
- a rule describing how waiting customers are selected for service.
If customers arrive faster than the system can process them for long enough, a queue forms. The central operational question is: how do arrival intensity and service capacity interact to determine congestion and delay?
Arrival Rate
Let
\[ \lambda \]denote the average arrival rate. If customers arrive at an average rate of \(\lambda=12\) per hour, then the expected number of arrivals during \(t\) hours is \(\lambda t\).
Service Rate
Let
\[ \mu \]denote the average service rate of one server. The corresponding mean service time is
\[ \boxed{\frac{1}{\mu}}. \]Mean Service Time
If \(\mu=12\) customers per hour, then
\[ \frac{1}{\mu}=\frac{1}{12}\text{ hour}=5\text{ minutes}. \]The Number in the System
Let \(N(t)\) denote the number of customers in the system at time \(t\). This count includes both customers waiting in line and customers currently receiving service.
The process \(\{N(t):t\ge0\}\) is often the main state process in a queueing model.
Queue Length Versus System Size
Queueing notation often distinguishes \(L\), the long-run mean number in the entire system, from \(L_q\), the long-run mean number waiting in the queue.
A customer currently in service is counted in \(L\) but not in \(L_q\).
Waiting Time Versus System Time
The quantity \(W\) denotes the mean time a customer spends in the entire system, while \(W_q\) denotes the mean time spent waiting before service.
\[ \boxed{ W=W_q+\text{mean service time} }. \]Queue Discipline
A queue discipline specifies which waiting customer is served next.
- first-come, first-served;
- last-come, first-served;
- priority service;
- random selection;
- processor sharing.
First-Come, First-Served
The most common introductory rule is first-come, first-served, abbreviated FCFS or FIFO. Customers are served in the same order in which they arrive.
One Server Versus Several Servers
A queue may have one server or several parallel servers. Examples include one cashier, several checkout lanes, one processor, or a pool of service agents.
The number of servers is a major structural feature of the model.
Kendall's Queueing Notation
A common notation summarizes arrival and service assumptions. For example,
\[ M/M/1 \]denotes:
- Markovian, or Poisson, arrivals;
- Markovian, or exponential, service times;
- one server.
The \(M/M/1\) Queue
The basic \(M/M/1\) model assumes:
- Poisson arrivals with rate \(\lambda\);
- independent exponential service times with rate \(\mu\);
- one server;
- unlimited waiting capacity;
- no abandonment;
- independent arrival and service processes.
Utilization
The traffic intensity or utilization is
\[ \boxed{ \rho=\frac{\lambda}{\mu} }. \]In a stable \(M/M/1\) system, \(\rho\) is also the long-run fraction of time the server is busy.
Interpreting Utilization
If \(\lambda=8\) customers per hour and \(\mu=10\) customers per hour, then
\[ \rho=\frac{8}{10}=0.8. \]The server is busy about \(80\%\) of the time in long-run equilibrium.
The Stability Condition
For a standard \(M/M/1\) queue to have a steady-state distribution,
\[ \boxed{\lambda<\mu} \]or equivalently
\[ \boxed{\rho<1}. \]The server must be able to process work faster on average than work arrives.
Why \(\lambda<\mu\) Matters
If \(\lambda\ge\mu\), arrivals occur at least as quickly as the server can process them on average. In the unlimited-capacity \(M/M/1\) model, the queue does not settle into a finite long-run equilibrium distribution.
Birth-Death Structure
The \(M/M/1\) queue can be viewed as a continuous-time birth-death process. When there are \(n\ge1\) customers:
\[ n\to n+1 \]occurs at rate \(\lambda\), while
\[ n\to n-1 \]occurs at rate \(\mu\).
What Happens at State Zero
When \(N(t)=0\), no customer is present to complete service. The only next transition is \(0\to1\) when the next arrival occurs.
Steady-State Probabilities
For a stable \(M/M/1\) queue,
\[ \boxed{ \pi_n=(1-\rho)\rho^n, \qquad n=0,1,2,\ldots }. \]The long-run number in the system therefore has a geometric distribution on the nonnegative integers.
Probability the System Is Empty
\[ \boxed{ \pi_0=1-\rho }. \]Therefore, the long-run probability that the system is empty is \(1-\rho\).
Probability the Server Is Busy
The server is busy whenever at least one customer is present:
\[ P(N\ge1)=1-\pi_0=\rho. \]Thus,
\[ \boxed{P(\text{server busy})=\rho}. \]Probability of at Least \(k\) Customers
For the steady-state \(M/M/1\) distribution,
\[ \boxed{ P(N\ge k)=\rho^k }. \]Congestion probabilities rise sharply as \(\rho\) approaches \(1\).
Mean Number in the System
For a stable \(M/M/1\) queue,
\[ \boxed{ L=\frac{\rho}{1-\rho} = \frac{\lambda}{\mu-\lambda} }. \]Mean Number Waiting in Queue
\[ \boxed{ L_q=\frac{\rho^2}{1-\rho} = \frac{\lambda^2}{\mu(\mu-\lambda)} }. \]Mean Time in the System
\[ \boxed{ W=\frac{1}{\mu-\lambda} }. \]This includes both waiting time and service time.
Mean Waiting Time in Queue
\[ \boxed{ W_q=\frac{\lambda}{\mu(\mu-\lambda)} }. \]Since the mean service time is \(1/\mu\),
\[ W=W_q+\frac{1}{\mu}. \]Little's Law
A fundamental relationship in queueing and flow systems is
\[ \boxed{ L=\lambda W }. \]In words: average number in the system = arrival rate × average time in the system.
Little's Law for the Waiting Line
Applied only to the queue,
\[ \boxed{ L_q=\lambda W_q }. \]Little's Law is far more general than the \(M/M/1\) formulas and applies to many stable flow systems.
Checking the \(M/M/1\) Formulas with Little's Law
Since
\[ W=\frac{1}{\mu-\lambda}, \]Little's Law gives
\[ L=\lambda W=\frac{\lambda}{\mu-\lambda}, \]matching the direct \(M/M/1\) formula.
Example: Basic \(M/M/1\) System
Suppose \(\lambda=6\) customers per hour and \(\mu=10\) customers per hour. Then
\[ \rho=\frac{6}{10}=0.6. \]The queue is stable because \(\rho<1\).
Example: Mean Number in the System
\[ L=\frac{0.6}{1-0.6} = \boxed{1.5}. \]Example: Mean Time in the System
\[ W=\frac{1}{10-6} = \frac14\text{ hour} = \boxed{15\text{ minutes}}. \]Example: Mean Waiting Time
The mean service time is
\[ \frac{1}{10}\text{ hour}=6\text{ minutes}. \]Therefore,
\[ W_q=15-6=\boxed{9\text{ minutes}}. \]Example: Mean Number Waiting
Little's Law for the queue gives
\[ L_q=\lambda W_q. \]Since \(W_q=0.15\) hour,
\[ L_q=6(0.15)=\boxed{0.9}. \]Congestion Increases Nonlinearly
As
\[ \rho\to1^-, \]the quantities \(L,L_q,W,W_q\) grow without bound in the \(M/M/1\) model. Operating very close to full utilization can therefore create disproportionately large delays.
Why High Utilization Can Be Expensive
A stochastic service system needs slack to absorb random variation. When utilization becomes too high, even small fluctuations in arrivals and service times can create long queues.
Queueing theory therefore exposes a tradeoff between utilization and responsiveness.
Arrival Variability Matters
Two systems can have the same mean arrival rate but different waiting behavior if their arrival patterns have different variability.
Bursty, scheduled, correlated, or seasonal arrivals can require models other than a Poisson process.
Service Variability Matters
Two systems can have the same mean service time but different queueing performance if service-time variability differs.
Exponential service is only one model; deterministic or low-variance service can produce shorter waits under the same mean capacity.
The \(M/G/1\) Idea
The notation
\[ M/G/1 \]describes Poisson arrivals, a general service-time distribution, and one server.
The \(M/M/c\) Idea
The notation
\[ M/M/c \]describes Poisson arrivals, exponential service times, and \(c\) parallel servers. Multi-server systems require formulas different from the \(M/M/1\) case.
Capacity-Limited Queues
Some systems allow only a finite number of customers. If the system is full, new arrivals may be blocked or lost.
Such models change both the state space and the effective arrival rate.
Customer Abandonment
In many real queues, customers may leave before receiving service. This is called abandonment or reneging.
Balking
A customer may decide not to enter after observing congestion. This is called balking.
Balking makes the effective arrival behavior depend on the current system state.
Priority Queues
Some systems serve high-priority customers ahead of lower-priority customers. Priorities may be preemptive or nonpreemptive and can change waiting-time distributions substantially.
Networks of Queues
In many systems, customers move from one service station to another. Manufacturing lines, computer networks, hospital departments, and logistics systems can all be modeled as networks of interacting queues.
Queueing as a Flow System
\[ \text{arrivals} \longrightarrow \text{waiting} \longrightarrow \text{service} \longrightarrow \text{departures}. \]Long-run conservation of flow is one reason Little's Law is so broadly applicable.
Throughput
The throughput is the long-run departure rate. In a stable, lossless single-class queue,
\[ \boxed{\text{throughput}=\lambda}. \]If customers are blocked, lost, or abandon, effective throughput may be lower.
Queue Length Is Random
Even in steady state, the number of customers changes randomly. The quantity \(L\) is an expectation, not a constant queue length.
Waiting Time Is Random
Likewise, \(W\) is a mean. Some customers receive immediate service while others wait much longer.
Operational decisions often require probabilities and quantiles in addition to averages.
Service Levels
A service-level metric might ask for
\[ P(W_q\le5\text{ minutes}). \]Such probabilities can be more operationally useful than mean waiting time alone.
Steady State Versus Transient Behavior
Standard \(M/M/1\) formulas describe long-run equilibrium. A system that has just opened, begins with a backlog, or has just experienced a surge can behave differently during a transient period.
Queueing Simulation
- Generate the next arrival time.
- Generate service times.
- Track whether the server is busy or idle.
- Place arriving customers in line when necessary.
- Process arrivals and departures in chronological order.
- Record waiting times, queue lengths, and utilization.
Discrete-Event Simulation
Queueing simulation is a major example of discrete-event simulation. The simulated clock jumps from one event time to the next rather than advancing through every instant.
What Simulation Can Estimate
- mean queue length;
- mean waiting time;
- waiting-time quantiles;
- server utilization;
- probability of delay;
- probability of overflow;
- service-level performance;
- effects of staffing or capacity changes.
Warm-Up Periods in Simulation
A simulation started from an empty system may initially understate steady-state congestion. Analysts often discard an initial warm-up period before estimating long-run performance.
Model Assumption: Poisson Arrivals
The \(M/M/1\) model assumes Poisson arrivals. Scheduled appointments, clustered demand, and daily cycles can violate this assumption.
Model Assumption: Exponential Service
The \(M/M/1\) model assumes independent exponential service times. Highly standardized or heavy-tailed service systems may behave differently.
Model Assumption: Independent Arrivals and Service
Basic queueing models assume arrival behavior does not directly alter service times and vice versa. Real congestion can violate this assumption.
Model Assumption: Infinite Waiting Capacity
The standard \(M/M/1\) model assumes arbitrarily many customers can wait. Physical spaces and computer buffers often have finite capacity.
Common Error: Confusing \(\lambda\) and \(\mu\)
\(\lambda\) measures incoming demand, while \(\mu\) measures service capacity. Reversing them changes the utilization calculation.
Common Error: Comparing Incompatible Units
If arrivals are measured per hour and service times are given in minutes, convert them before computing
\[ \rho=\frac{\lambda}{\mu}. \]Common Error: Treating \(\rho=1\) as Stable
In the standard \(M/M/1\) model, \(\rho=1\) is not a stable steady-state operating point. Stability requires
\[ \boxed{\rho<1}. \]Common Error: Confusing \(L\) and \(L_q\)
\(L\) includes the customer in service. \(L_q\) counts only customers waiting.
Common Error: Confusing \(W\) and \(W_q\)
\(W\) includes waiting and service time. \(W_q\) measures only the time before service begins.
Common Error: Applying \(M/M/1\) Formulas to Every Queue
The formulas
\[ L=\frac{\lambda}{\mu-\lambda} \]and
\[ W=\frac{1}{\mu-\lambda} \]depend on the \(M/M/1\) assumptions. They do not automatically apply to multi-server, finite-capacity, priority, or general-service systems.
Common Error: Assuming High Utilization Is Always Efficient
In stochastic systems, operating very close to \(100\%\) utilization can cause severe waiting. Efficiency must be considered together with delay and service quality.
A Reliable Procedure for \(M/M/1\) Problems
- Identify the arrival rate \(\lambda\).
- Identify the service rate \(\mu\).
- Convert both rates to the same time units.
- Compute \(\rho=\lambda/\mu\).
- Check the stability condition \(\rho<1\).
- Use the appropriate formula for \(L\), \(L_q\), \(W\), or \(W_q\).
- Use Little's Law as a consistency check.
- Interpret the result as a long-run average.
A Reliable Procedure for Little's Law
- Identify the relevant flow system.
- Determine the long-run effective arrival or throughput rate.
- Match system-wide \(L\) with \(W\), or queue-only \(L_q\) with \(W_q\).
- Use \(L=\lambda W\) or \(L_q=\lambda W_q\).
- Check units: rate times time should produce an average count.
Example: Full \(M/M/1\) Workflow
Customers arrive at rate \(\lambda=9\) per hour, and one server completes service at rate \(\mu=12\) per hour.
\[ \rho=\frac{9}{12}=0.75. \]The system is stable.
\[ L=\frac{0.75}{1-0.75}=3. \] \[ W=\frac{1}{12-9}=\frac13\text{ hour}=20\text{ minutes}. \]The mean service time is
\[ \frac1{12}\text{ hour}=5\text{ minutes}. \]Therefore,
\[ W_q=20-5=15\text{ minutes}. \]Finally,
\[ L_q=\lambda W_q=9\left(\frac14\right)=2.25. \]Thus,
\[ \boxed{ \rho=0.75,\quad L=3,\quad L_q=2.25,\quad W=20\text{ min},\quad W_q=15\text{ min} }. \]Practice 1: Utilization
An \(M/M/1\) queue has \(\lambda=8\) per hour and \(\mu=10\) per hour. Find \(\rho\).
Practice 2: Stability
Is an \(M/M/1\) queue with \(\lambda=12\) and \(\mu=10\) stable?
Practice 3: Mean Number in the System
For \(\lambda=6\) and \(\mu=9\), find \(L\).
Practice 4: Mean Time in the System
Using \(\lambda=6\) and \(\mu=9\), find \(W\) in hours and minutes.
Practice 5: Mean Waiting Time
Using the same queue, find \(W_q\).
Practice 6: Mean Number Waiting
Using the same queue, find \(L_q\).
Practice 7: Empty-System Probability
An \(M/M/1\) queue has \(\rho=0.7\). Find the steady-state probability that the system is empty.
Practice 8: Tail Probability
For \(\rho=0.7\), find
\[ P(N\ge3). \]Practice 9: Little's Law
A stable service system has throughput \(20\) customers per hour and average time in system \(0.25\) hour. Find the average number in the system.
Practice 10: Identify the Error
A student says: “A server with \(100\%\) utilization is ideal because no service capacity is wasted and the queue is still stable.”
Explain the error for the standard \(M/M/1\) model.
Practice Answers
Practice 1
\[ \rho=\frac{8}{10}=\boxed{0.8}. \]Practice 2
No. Since \(\lambda=12>\mu=10\), \(\rho=1.2>1\). The standard unlimited \(M/M/1\) queue has no finite steady-state distribution.
Practice 3
\[ L=\frac{\lambda}{\mu-\lambda} = \frac{6}{9-6} = \boxed{2}. \]Practice 4
\[ W=\frac{1}{9-6} = \frac13\text{ hour} = \boxed{20\text{ minutes}}. \]Practice 5
\[ W_q = \frac{6}{9(3)} = \frac29\text{ hour} = \boxed{13.\overline{3}\text{ minutes}}. \]Practice 6
\[ L_q = \lambda W_q = 6\left(\frac29\right) = \boxed{\frac43}. \]Practice 7
\[ P(N=0)=1-\rho=\boxed{0.3}. \]Practice 8
\[ P(N\ge3)=\rho^3=(0.7)^3=\boxed{0.343}. \]Practice 9
\[ L=\lambda W=20(0.25)=\boxed{5}. \]Practice 10
In the standard \(M/M/1\) model, \(\rho=1\) is not stable. Random variation causes the queue to grow without settling into a finite steady-state distribution. Stability requires
\[ \boxed{\rho<1}. \]What to Remember
- \(\lambda\) is the arrival rate.
- \(\mu\) is the service rate of one server.
- The mean service time is \(1/\mu\).
- \(L\) is the mean number in the system.
- \(L_q\) is the mean number waiting.
- \(W\) is the mean total time in the system.
- \(W_q\) is the mean waiting time before service.
- An \(M/M/1\) queue has Poisson arrivals, exponential service times, and one server.
- Utilization is \(\rho=\lambda/\mu\).
- The \(M/M/1\) stability condition is \(\rho<1\).
- In steady state, \(\pi_n=(1-\rho)\rho^n\).
- The server is busy with probability \(\rho\).
- \(L=\lambda/(\mu-\lambda)\).
- \(W=1/(\mu-\lambda)\).
- Little's Law gives \(L=\lambda W\).
- The queue-only form is \(L_q=\lambda W_q\).
- High stochastic utilization can produce rapidly increasing delay.
- Multi-server, finite-capacity, priority, abandonment, and general-service systems require modified models.
The central operational principle is: random variability creates waiting whenever demand approaches service capacity too closely.
Where We Go Next
Queueing models track congestion caused by random arrivals and service. Another major stochastic-process application tracks how systems move among functioning, degraded, failed, and repaired conditions over time.
The next lesson, Reliability Processes, develops failure and repair models, survival probabilities, hazard rates, system states, availability, and stochastic reliability over time.