Queuing Theory & Line Balancing

Queuing theory and assembly-line balancing are a reliable GATE ME topic (~1–2 marks). The M/M/1 formulas, Little's law, and line-balancing metrics are the tested items.

Queuing theory (M/M/1)

A single-server queue with Poisson arrivals (rate λ) and exponential service (rate μ). Utilisation ρ = λ/μ (must be < 1 for stability).

• Number in system L_s = ρ/(1 − ρ); in queue L_q = ρ²/(1 − ρ).
• Time in system W_s = 1/(μ − λ); in queue W_q = λ/(μ(μ − λ)) = ρ/(μ − λ).
• Little's law (very general): L = λ·W (applies to system and queue separately). As ρ → 1, queues grow without bound.

Line balancing

Assign tasks to workstations on an assembly line to minimise idle time.

• Cycle time C = available time / required output (also = the bottleneck station time). Takt time = available time / customer demand.
• Minimum stations N_min = (Σ task times)/C (round up).
• Balance (line) efficiency = (Σ task times)/(N × C); balance delay = 1 − efficiency.
  Precedence constraints limit how tasks can be grouped (heuristics: largest-candidate, ranked-positional-weight).

Exam Tricks & Tips

• 🎯 M/M/1: ρ = λ/μ, L_s = ρ/(1−ρ), W_s = 1/(μ−λ) — the core set; stability needs ρ < 1.
• 🎯 Little's law L = λW links length and waiting time — use it to get one from the other instantly.
• 🎯 As utilisation ρ → 1, queue length and wait blow up — non-linear congestion, a key conceptual point.
• 🎯 Line efficiency = Σ task times/(N·C); minimum stations = Σtimes/C (round up) — the balancing essentials.
• 🎯 Cycle time = bottleneck station time = available time/output — the slowest station paces the line.
• ❌ Common mistake: mixing L_s (in system) with L_q (in queue), or W_s with W_q — "in system" includes the one being served; "in queue" excludes it (L_s = L_q + ρ).

Expected exam pattern

A 1-mark M/M/1 (ρ, L, W) or cycle-time NAT, and a 2-mark queuing (average wait/length) or line-balancing (stations, efficiency) problem. Little's law and the L_s-vs-L_q distinction are frequent points.

Quick recap

M/M/1: ρ = λ/μ (< 1), L_s = ρ/(1−ρ), L_q = ρ²/(1−ρ), W_s = 1/(μ−λ), W_q = ρ/(μ−λ); Little's law L = λW. Line balancing: cycle time C = time/output (= bottleneck), N_min = Σt/C (round up), efficiency = Σt/(N·C), balance delay = 1 − efficiency.

Cover the answer, recall, then check. 12 cards on queuing and line balancing for GATE ME.

Q1. What does M/M/1 denote?
A1. A single-server queue with Markovian (Poisson) arrivals, Markovian (exponential) service times, and one server.

Q2. Define utilisation and the stability condition.
A2. ρ = λ/μ (arrival rate/service rate). The queue is stable only if ρ < 1.

Q3. Average number in the system (M/M/1)?
A3. L_s = ρ/(1 − ρ).

Q4. Average number waiting in the queue (M/M/1)?
A4. L_q = ρ²/(1 − ρ). Note L_s = L_q + ρ.

Q5. Average time spent in the system?
A5. W_s = 1/(μ − λ).

Q6. Average waiting time in the queue?
A6. W_q = λ/(μ(μ − λ)) = ρ/(μ − λ).

Q7. State Little's law.
A7. L = λ·W — the average number in a system equals the arrival rate times the average time spent (applies to system and queue).

Q8. What happens as utilisation approaches 1?
A8. Queue length and waiting time grow without bound (non-linearly) — the system saturates.

Q9. Define cycle time in line balancing.
A9. C = available time / required output; it equals the bottleneck (slowest) station time and paces the line.

Q10. Minimum number of workstations?
A10. N_min = (Σ task times)/C, rounded up to the next integer.

Q11. Define line (balance) efficiency and balance delay.
A11. Efficiency = (Σ task times)/(N × C); balance delay = 1 − efficiency (fraction of idle time).

Q12. Difference between L_s and L_q?
A12. L_s counts everyone in the system (including the one being served); L_q counts only those waiting. L_s = L_q + ρ.

Waiting lines — at machines, service counters, on assembly lines — cost time and money. Queuing theory predicts waiting; line balancing distributes work evenly across stations. GATE tests the M/M/1 queue formulas and assembly-line balancing metrics.

Core concept: queuing models relate arrival and service rates to waiting time and queue length; line balancing assigns tasks to workstations to minimise idle time given a required output rate.

Deep explanation

Beginner — the M/M/1 queue

The basic model: Poisson arrivals (rate λ), exponential service (rate μ), single server, infinite queue (FCFS). Define utilisation ρ = λ/μ (must be < 1 for stability). Then:

• Average number in system L = ρ/(1 − ρ) = λ/(μ − λ).
• Average number in queue L_q = ρ²/(1 − ρ).
• Average time in system W = 1/(μ − λ).
• Average time in queue W_q = ρ/(μ − λ) = λ/(μ(μ − λ)).
  Little's law ties them: L = λW and L_q = λW_q (universal, any queue).

Intermediate — extensions

• M/M/c (multiple servers), M/M/1/N (finite capacity), M/G/1 (general service) extend the basic model. As ρ → 1, waiting time explodes (nonlinearly) — the reason systems avoid running near full capacity.
• Probability of n in system (M/M/1): P_n = (1 − ρ)ρⁿ; probability system empty P₀ = 1 − ρ.

Advanced — assembly line balancing

Distribute tasks (with precedence) among stations to meet a required output:

• Cycle time C = available time/required output (the time allowed per station).
• Minimum number of stations N_min = (Σ task times)/C (round up).
• Balance efficiency = (Σ task times)/(N × C); balance delay (idle %) = 1 − efficiency.
  Heuristics: largest-candidate rule, ranked positional weight. The bottleneck station (longest station time) limits the line's output rate.

Worked example

Customers arrive at a single machine at λ = 6 per hour (Poisson); service rate μ = 10 per hour (exponential). Find the average number in the system and the average time in the system.
Utilisation ρ = λ/μ = 6/10 = 0.6 (< 1, stable).
L = λ/(μ − λ) = 6/(10 − 6) = 6/4 = 1.5 customers.
W = 1/(μ − λ) = 1/(10 − 6) = 1/4 hour = 15 minutes. (Check Little's law: L = λW = 6 × 0.25 = 1.5 ✓.)

GATE relevance

M/M/1 queue metrics (L, L_q, W, W_q), utilisation, Little's law, and assembly-line balancing (cycle time, minimum stations, balance efficiency) are recurring Industrial Engineering questions. The M/M/1 formulas and Little's law are must-memorise.

Exam tricks & shortcuts

• M/M/1: L = λ/(μ−λ), W = 1/(μ−λ); utilisation ρ = λ/μ must be < 1.
• Little's law L = λW is universal — use it to get any quantity from another.
• Line balancing: cycle time = available time/output; min stations = Σtask/C (round up).
• Mnemonic: "L equals lambda-W (Little's law), always."

Key formulas (M/M/1 queue)

• Traffic intensity: ρ = λ/μ (λ = arrival rate, μ = service rate); stable if ρ < 1.
• Avg number in system: L_s = ρ/(1 − ρ); in queue L_q = ρ²/(1 − ρ).
• Avg time in system: W_s = 1/(μ − λ); in queue W_q = ρ/(μ − λ).
• Little's law: L = λW.
• Line balancing: cycle time C = available time/demand; min stations N = Σt_i/C; efficiency η = Σt_i/(N·C).

M/M/1 formulas give queue lengths and waiting times; line balancing minimises workstations for a target cycle time.

Worked Example

Problem: Customers arrive at a single-server counter (M/M/1) at an average rate of 6 per hour, and the server processes them at an average rate of 10 per hour. Find the server utilization, the average number of customers in the system, and the average time a customer spends in the system.

Solution:
For an M/M/1 queue with arrival rate λ = 6/hr and service rate µ = 10/hr:

Server utilization (traffic intensity):
ρ = λ/µ = 6/10 = 0.6 (the server is busy 60% of the time).

Average number of customers in the system:
L_s = ρ/(1 − ρ) = 0.6/(1 − 0.6) = 0.6/0.4 = 1.5 customers.

Average time a customer spends in the system:
W_s = 1/(µ − λ) = 1/(10 − 6) = 0.25 hr = 15 minutes.

Answer: Utilization ρ = 0.6, average number in system L_s = 1.5, average time in system W_s = 15 minutes.