Simulation of Queuing System
Open in the Padhaiko app4.1 Elements of queuing system
A queuing system models situations where customers (people, packets, jobs, or vehicles) arrive for service, wait if all servers are busy, receive service, and depart. Every queuing system consists of five basic elements:
- Calling Population: The source of potential customers, either finite (e.g., machines monitored by one repair technician) or infinite (e.g., callers to a national helpline, where one arrival does not alter the arrival rate).
- Arrival Process: Specifies how customers arrive over time—typically via the distribution of inter-arrival times (e.g., exponential inter-arrivals corresponding to a Poisson arrival process) and whether arrivals occur singly or in batches.
- Queue (Waiting Line): The buffer where waiting customers stay, characterized by its capacity (finite vs. infinite ).
- Queue Discipline: The rule selecting the next customer to be served:
- FIFO / FCFS: First-In, First-Out (standard default).
- LIFO / LCFS: Last-In, First-Out (stack-like buffers).
- SIRO: Service In Random Order.
- Priority (PR): Preemptive or non-preemptive priority classes (e.g., emergency patients, shortest-job-first).
- Service Mechanism: The number of parallel servers (channels) and the probability distribution of service times (mean service rate per server).
4.2 Characteristics of queuing systems
To analyze or simulate a queuing system rigorously, we track its operating characteristics and customer behaviors:
- Arrival Rate () and Service Rate (): Mean number of arrivals per unit time () and mean completions per busy server per unit time ().
- Server Utilization / Traffic Intensity (): Fraction of time each server is busy:
For an infinite-capacity queue to reach steady state (statistical equilibrium), we require the stability condition (i.e., ); otherwise the queue grows without bound.
- Transient vs. Steady-State Behavior: Early simulation output depends heavily on initial conditions (e.g., starting empty at ), known as the transient state; after sufficient time (when ), state probabilities converge to time-independent steady-state values.
- Customer Impatience Behaviors:
- Balking: An arriving customer refuses to join because the queue is already too long.
- Reneging: A queued customer leaves before receiving service after waiting too long.
- Jockeying: In multi-queue parallel systems, a customer switches from a slower/longer line to a shorter one.
4.3 Model of queuing system
The classical analytical queuing model treats the number of customers in the system as a birth–death continuous-time Markov chain:
- A birth (arrival) moves state at rate .
- A death (service completion) moves state at rate .
Steady-State Birth-Death Balance Equations
In statistical equilibrium (), the probability flux leaving state equals the probability flux entering state . Balancing flow across the cut between states and yields:
where is determined from the normalization condition .
When arrivals follow a Poisson process with rate (equivalently, i.i.d. Exponential() inter-arrival times) and service times are i.i.d. Exponential(), the memoryless property guarantees that future transitions depend only on the current count , not on elapsed times.
4.4 Types of queuing system
| Model | Key Features | Stability Condition | Typical Use |
|---|---|---|---|
| Poisson arrivals, exponential service, server, capacity | Single ATM, single CPU core, simple help desk | ||
| Poisson arrivals, exponential service, parallel servers sharing one queue | Multi-teller bank, multi-core processor, call center | ||
| Finite system capacity (arrivals when are blocked/lost) | Always stable (even if ) | Finite router packet buffer, limited parking lot | |
| Finite calling population of size (machine repairman model) | Always stable | machines serviced by technician | |
| Poisson arrivals, general service distribution (mean , variance ) | Systems with constant () or arbitrary service times |
For , the Pollaczek–Khinchin (P–K) formula gives the mean queue length:
showing that reducing service-time variance (e.g., deterministic service in ) cuts average waiting line length in half compared to !
4.5 Queuing notation (Kendall’s notation)
Kendall’s Notation: A / B / c / K / N / D
Introduced by D. G. Kendall (1953) and extended to six fields, Kendall's notation concisely specifies a queuing system as :
- : Inter-arrival time distribution ( = Markovian/Exponential, = Deterministic/Constant, = Erlang-, = General).
- : Service time distribution (, , , ).
- : Number of parallel servers ().
- : Maximum system capacity (in service + waiting; default ).
- : Calling population size (default ).
- : Queue discipline (default
FIFO/FCFS).
When the last three parameters take their defaults (), the shorthand is used (e.g., , ).
4.6 Measurement of system performance
Four core steady-state expectations measure queuing performance:
- : Average number of customers in the system (waiting + in service).
- : Average number of customers in the queue (waiting only).
- : Average time a customer spends in the system ().
- : Average waiting time in the queue.
Little’s Law
For any stationary queuing system (regardless of arrival distribution, service distribution, number of servers, or queue discipline), the long-run average count equals the effective arrival rate multiplied by the long-run average time:
(When capacity is infinite, ; in finite-capacity , blocked customers are excluded so .)
Exact Formulas for and
| Metric | () | (, ) |
|---|---|---|
| Idle Probability () | ||
| State Probability () | ||
| Mean Queue Length () | ||
| Mean System Size () | ||
| Mean Queue Wait () | ||
| Mean System Time () |
4.7 Network of queues
Real systems such as computer networks, hospitals, and multi-stage factories consist of interconnected service stations where departures from one node become arrivals to another.
Open and Closed Queuing Networks
- Open Queuing Network: Customers enter from outside the network (external Poisson rate at node ), visit one or more service centers according to routing probabilities , and eventually depart the network.
- Closed Queuing Network: A fixed population of customers circulates indefinitely among the nodes with zero external arrivals and zero departures (e.g., a multiprogrammed OS with fixed concurrency level ).
Burke’s Theorem and Jackson’s Theorem
- Burke’s Theorem: In steady state, the departure process from a stable queue with arrival rate is itself a Poisson process with rate .
- Jackson’s Theorem (Open Networks): In an open network of exponential service nodes where node has servers at rate , external Poisson arrivals , and routing probabilities :
- The effective total arrival rate at each node satisfies the linear traffic equations:
- If for every node, the joint steady-state queue-length distribution factors into the product of independent marginals:
so total mean customers and mean end-to-end sojourn time .
4.8 Applications of queuing system
Queuing theory and discrete-event queuing simulation guide capacity planning across engineering domains:
- Computer Systems and Operating Systems: Sizing CPU ready queues, multi-core thread pools, and disk I/O request buffers to bound tail latency.
- Computer Networks and Telecommunications: Dimensioning router output buffers ( packet loss probability), call-center trunk lines, and cellular channel allocation.
- Manufacturing and Logistics: Balancing assembly-line workstations, warehouse loading docks, and automated guided vehicle (AGV) dispatching.
- Service Operations: Determining the optimal number of bank tellers, supermarket checkout lanes, hospital triage nurses, and highway tollbooths to balance staffing cost against customer waiting cost.
Worked Out Examples
1
Students arrive at a campus IT help desk according to a Poisson process at an average rate of . A single technician serves them with exponentially distributed service times averaging per student. Find:
- Traffic intensity and idle probability .
- Probability that there are exactly students in the system ().
- Mean number of students in the system () and in the queue ().
- Mean time spent in the system () and waiting in the queue (), in minutes.
Identifying the rates and traffic intensity: Mean service time is , so the service rate is .
Computing , , and :
Applying Little’s Law to find and :
(Check: .)
- ,
- ()
- ,
- ,
2
A bank operates an counter with tellers sharing a single FCFS queue. Customers arrive at and each teller serves at . Calculate , , , (in minutes), and (in minutes).
Computing offered load and per-server utilization :
Finding for :
Computing , , , and :
- ()
- ,
- ,
3
In an open Jackson queuing network of a computer server, jobs arrive from outside to the CPU (Node 1, ) as a Poisson stream at rate , while external arrivals to the Disk (Node 2, ) are . After finishing at the CPU, of jobs go to the Disk and leave the system. After finishing at the Disk, return to the CPU and leave the system. Find:
- Effective arrival rates and and utilizations .
- Average total number of jobs in the system and average response time .
Solving Jackson’s traffic equations:
Substituting into the first equation:
Utilizations:
Decomposing into independent nodes:
Total average jobs and response time (using total external arrival rate ):
- (), ().
- , .
Exercises
Practice Exercises — Simulation of Queuing System
Explain Kendall’s notation in detail, stating what each symbol represents and interpreting the queues , , and .
Six Fields of Kendall’s Notation ():
- : Inter-arrival time distribution ( = Exponential/Poisson, = Deterministic, = General).
- : Service time distribution (, , , ).
- : Number of parallel servers.
- : Maximum system capacity (default ).
- : Calling population size (default ).
- : Queue discipline (default ).
Interpreting the Three Examples:
- : Poisson arrivals, exponential service times, server, infinite capacity, infinite population, FIFO discipline.
- : Poisson arrivals, constant (deterministic) service times, parallel servers, maximum capacity customers in the system, infinite population, FIFO.
- : General inter-arrival and general service distributions, server, infinite waiting room, finite population of customers, Priority queue discipline.
Kendall's notation specifies arrival distribution, service distribution, servers, capacity, population size, and discipline. Thus is a single exponential server with infinite queue; has Poisson arrivals, constant service, servers, and capacity ; has general times, server, population , and priority scheduling.
Define balking, reneging, and jockeying in queuing systems, and explain why Little’s Law () is called a distribution-free conservation law.
Customer Impatience Behaviors:
- Balking: Arriving customer sees a long queue and decides not to enter.
- Reneging: Queued customer loses patience and leaves before being served.
- Jockeying: Customer in one parallel queue moves to another queue perceived as shorter or faster.
Why Little’s Law Is Distribution-Free: holds for any stationary system with finite means—regardless of whether inter-arrival or service times are exponential, deterministic, or general, regardless of the number of servers , and regardless of queue discipline (FIFO, LIFO, or Priority).
Balking is refusing to join a queue, reneging is leaving a queue prematurely, and jockeying is switching between parallel queues. Little's Law () is distribution-free because it depends only on steady-state flow conservation, not on arrival/service distributions or service order.
Packets arrive at a single-channel network switch () at a mean rate of , and the switch transmits packets at a mean rate of . Compute:
- Channel utilization and mean number of packets waiting in the buffer ().
- Mean queuing delay () in minutes (and seconds).
- Probability that or more packets are in the switch ().
Computing utilization and mean queue length :
Computing mean queuing delay :
Computing tail probability : In an queue, :
- , .
- .
- ().
A small drive-through coffee kiosk ( with finite capacity total cars in the system) has Poisson arrivals at and exponential service at .
- Find the probability that the kiosk is empty and the blocking probability that an arriving car is turned away.
- Find the effective arrival rate of served cars.
Computing and for : Here and . Because for :
Computing effective arrival rate : Cars enter only when the system is not full (), which occurs with probability :
- , blocking probability .
- Effective arrival rate .
Compare the steady-state mean queue length of an system and an system when both have arrival rate and mean service time (). (Hint: use the Pollaczek–Khinchin formula with for exponential service and for deterministic service.)
Calculating utilization :
Computing via Pollaczek–Khinchin formula:
- For (, so ):
- For (constant service time ):
At , while —eliminating service-time variance halves the average queue length.