Fundamentals of Transportation/Queueing

Queueing

Queues are everywhere: boarding a bus or train or plane, traffic lights and ramp meters, freeway bottlenecks, shopping checkout, exiting a doorway at the end of class, waiting for a computer in the lab, a hamburger at McDonald’s, or a haircut at the barber. Explain why buses come in bunches. The same logic (with different parameters) can be applied to all these phenomena.

Cumulative Input-Output Diagram (Newell Curve)

Based on the departure rate and arrival rate pair data, the delay of every individual vehicle can be obtained. Using the I/O queueing diagram shown in Figure 1, it is possible to find the delay for every individual vehicle: the delay of the ith vehicle is time of departure - time of arrival (t2-t1). Total delay is the sum of the delays of each vehicle, which is the area in the triangle between the A(t) and D(t) curves. Rate of Arrival  0 0 0 0 0 0  Rate of Service

Distributions

Arrival Distribution - Deterministic (uniform) OR Random (e.g. Poisson) Service Distribution - Deterministic OR Random Service Method - First Come First Serve (FCFS) or First In First Out (FIFO) OR Last Come First Served (LCFS) or Last In First Out (LIFO) OR Priority (e.g. HOV bypasses at ramp meters)

Characterizing Queues

Queue Length Characteristics - Finite or Infinite Number of Channels - Number of Waiting Lines (e.g. Ramps = 2, Supermarket = 12)

We use the following notation Arrival Rate = $\lambda$ Departure Rate = $\mu$

Service time $\rho =\frac{\lambda }{\mu }$

Degree of Saturation

Oversaturated: $\lambda >\mu$

Undersaturated $\lambda <\mu$

Saturated $\lambda =\mu$

Uncapacitated Queues (M/D/1) and (M/M/1)

Comparison of M/D/1 and M/M/1 queue properties

'	M/D/1	M/M/1
Q (average queue size (#))	$Q=\frac{{\rho }^2}{2(1-\rho )}$	$Q=\frac{{\rho }^2}{1-\rho }$
w (average waiting time)	$w=\frac{\rho }{2\mu \left(1-\rho \right)}$	$w=\frac{\lambda }{\mu \left(\mu -\lambda \right)}$
t (average total delay)	$t=\frac{2-\rho }{2\mu \left(1-\rho \right)}$	$t=\frac{1}{\left(\mu -\lambda \right)}$

Notes:

• Average queue size includes customers currently being served (in number of units)
• Average wait time excludes service time
• Average delay time is (wait time + service time)

Little's Formula: $Q=\lambda w$

Example 1

At the Krusty-Burger if the arrival rate is 1 customer every minute, and the service rate is 1 customer every 45 seconds. Find the average queue size, the average waiting time, and average total delay. Assume an M/M/1 process.

Solution

Service time

$\rho =\frac{\lambda }{\mu }=\frac{60/60}{60/45}=\frac{1}{1.33}=0.75$

Average queue size (Q)

$Q=\frac{{\rho }^2}{1-\rho }=\frac{{\left(0.75\right)}^2}{1-0.75}=2.25$

$Q=\lambda w$ (within rounding error)

Average wait time

$w=\frac{\lambda }{\mu \left(\mu -\lambda \right)}=\frac{1}{1.33\left(1.33-1\right)}=2.25$

Average delay time

$t=\frac{1}{\left(\mu -\lambda \right)}=\frac{1}{\left(1.33-1\right)}=3=w+servicetime=2.25+0.75$

Comparison

We can compute the same results using the M/D/1 equations, the results are shown in the Table below.

Comparison of M/D/1 and M/M/1 queue properties

'	M/D/1	M/M/1
Q (average queue size (#))	1.125	2.25
w (average waiting time)	1.125	2.25
t (average total delay)	1.88	3

As can be seen, the delay associated with the more random case (M/M/1, which has both random arrivals and service) is greater than the less random case (M/D/1), which is to be expected.

Uncapacitated queues (M/M/1) (random arrival and random service)

Probability of n units in the system

$\begin{array}{c}P\left(n\right)={\rho }^n\left(1-\rho \right)\\ \rho =\frac{\lambda }{\mu }\end{array}$

Expected number of units in the system $E\left(n\right)=\frac{\lambda }{\mu -\lambda }$

Mean Queue Length $E\left(m\right)=\frac{{\lambda }^2}{\mu \left(\mu -\lambda \right)}$

Average waiting time of arrival, including queue and service

$E\left(v\right)=\frac{1}{\left(\mu -\lambda \right)}$

Average waiting time in queue

$E\left(w\right)=\frac{\lambda }{\mu \left(\mu -\lambda \right)}$

Probability of spending time t or less in system

$P\left(v\le t\right)=1-e^{-\left(1-\rho \right)\lambda t}$

Probability of spending time t or less in queue $P\left(w\le t\right)=1-\rho e^{-\left(1-\rho \right)\lambda t}$

Probability of more than N vehicles in queue $P\left(n>N\right)={\rho }^{N+1}$

Key Terms

• Queueing theory
• Cumulative input-output diagram (Newell diagram)
• average queue length
• average waiting time
• average total delay time in system
• arrival rate, departure rate
• undersaturated, oversaturated
• D/D/1, M/D/1, M/M/1
• Channels
• Poisson distribution,
• service rate
• finite (capacitated) queues, infinite (uncapacitated) queues

Variables

• Arrival Rate = A(t) = λ
• Departure Rate = D(t) = μ
• service time = 1/μ
• Utilization = ρ =λ/ μ
• Q - average queue size including customers currently being served (in number of units)
• w - average wait time
• t = average delay time (queue time + service time)