Unit 3: Queuing theory & network models
Operation Research notes · PTU syllabus (BCOM 602-18)
On this page
Unit summary
Waiting lines and project schedules are everyday OR problems. This unit covers types of queuing situations, the single-server queuing model with Poisson arrivals and exponential service, and network models — PERT and CPM, network construction, critical path, slack and float, and crashing a network to reduce cost.
After this unit you can
- Explain the elements and types of queuing systems
- Compute performance measures of an M/M/1 queue
- Construct project networks and find the critical path
- Calculate floats, PERT probabilities and the optimal crash schedule
PTU syllabus topics
- Types of queuing situations
- queuing models with Poisson input and exponential service
- PERT and CPM
- construction of networks
- critical path identification
- slack and float
- crashing a network for cost reduction
Topic 1
Queuing theory: elements and types
- 1Input (calling) population
Finite or infinite
- 2Arrival process
Poisson (random) arrivals at rate λ
- 3Queue discipline
FCFS, LCFS, priority, service in random order
- 4Service mechanism
Exponential service at rate μ; number of servers
- 5Output
Customers leave after service
- Types of situations: single queue–single server (ATM), single queue–multiple servers (bank tellers), multiple queues–multiple servers (supermarket counters), sequential service (hospital).
- Kendall's notation: (a/b/c) : (d/e/f) — arrival distribution / service distribution / servers : capacity / population / discipline. M/M/1 = Poisson arrivals, exponential service, one server.
- Customer behaviour: balking (does not join), reneging (leaves the queue), jockeying (switches queues).
Topic 2
M/M/1 model: performance measures
Traffic intensity (utilisation)
ρ = λ ÷ μ (must be < 1)
Probability system is idle
P0 = 1 − ρ
Average number in system
Ls = λ ÷ (μ − λ)
Average number in queue
Lq = λ² ÷ [μ (μ − λ)]
Average time in system
Ws = 1 ÷ (μ − λ)
Average time in queue
Wq = λ ÷ [μ (μ − λ)]
Probability of n in system
Pn = (1 − ρ) ρ^n
Example
Customers arrive at 8 per hour; the clerk serves 10 per hour. ρ = 0.8; P0 = 0.2; Ls = 8 ÷ 2 = 4; Lq = 64 ÷ 20 = 3.2; Ws = 1 ÷ 2 hour = 30 minutes; Wq = 8 ÷ 20 hour = 24 minutes.
Exam tip
Little's law links them: Ls = λ × Ws and Lq = λ × Wq — use it to check your answers.
Topic 3
Network models: PERT and CPM
Origin
US Navy Polaris project (1958)
DuPont and Remington Rand (1957)
Activity times
Probabilistic — three estimates
Deterministic — one estimate
Orientation
Event-oriented
Activity-oriented
Used for
R&D, new projects with uncertainty
Construction, repetitive projects
Cost
Time-focused
Time–cost trade-off (crashing)
Construction of networks
- Activity (arrow), event (node), dummy activity (dashed — shows dependency without time).
- Rules: each activity has one arrow; no loops; no dangling events; only one start and one end node; dummies to avoid two activities with the same start and end nodes.
- 1Forward pass
Earliest start (ES) and earliest finish (EF)
- 2Backward pass
Latest finish (LF) and latest start (LS)
- 3Compute floats
- 4Critical activities have zero total float
- 5Critical path = longest path = project duration
Topic 4
Slack and float; PERT probabilities
Total float
LS − ES (or LF − EF)
Free float
ES of successor − EF of the activity
Independent float
ES of successor − LF of predecessor − duration
Event slack
Latest event time − Earliest event time
PERT expected time
te = (to + 4tm + tp) ÷ 6
Activity variance
σ² = [(tp − to) ÷ 6]²
Probability of completion
Z = (Scheduled time − Expected project time) ÷ √(Sum of critical variances)
Example
Activity estimates: optimistic 4, most likely 7, pessimistic 16 days → te = (4 + 28 + 16) ÷ 6 = 8 days; σ² = (12 ÷ 6)² = 4. If the critical path expected time is 40 days with total variance 16 (σ = 4), the probability of finishing in 44 days: Z = (44 − 40) ÷ 4 = 1 → about 84%.
Topic 5
Crashing a network for cost reduction
Crashing shortens project duration by adding resources to critical activities at extra (direct) cost, while indirect costs (overheads, penalties) fall.
Cost slope
(Crash cost − Normal cost) ÷ (Normal time − Crash time)
- 1
Find the critical path and total cost at normal times
- 2
Choose the critical activity with the lowest cost slope
- 3
Crash it by one unit (or as far as possible without creating a new critical path)
- 4
Recompute paths and total cost (direct + indirect)
- 5
Repeat while total cost falls
- 6
Optimal duration = minimum total cost
Example
Activity normal 8 days ₹6,000; crash 5 days ₹9,000 → cost slope = 3,000 ÷ 3 = ₹1,000 per day. If indirect cost is ₹1,500 per day, crashing this activity saves ₹500 per day.
Key terms
- Traffic intensity
- Ratio of arrival rate to service rate
- Kendall's notation
- Shorthand describing a queuing model
- Critical path
- Longest path determining project duration
- Total float
- Time an activity can be delayed without delaying the project
- Cost slope
- Extra cost per unit time saved by crashing
Quick revision
- Queue elements: population, arrivals, discipline, service, output.
- M/M/1: ρ = λ/μ; Ls = λ/(μ − λ); Ws = 1/(μ − λ); Little's law.
- PERT probabilistic (te), CPM deterministic.
- Forward and backward passes; zero float = critical.
- Crash lowest cost slope first until total cost is minimum.
Important exam questions
Practice questions written to the PTU exam pattern for this unit's syllabus: short answers (Section A style) and long answers (Sections B and C style).
Short-answer questions
- Q1.State Kendall's notation.
- Q2.What is traffic intensity?
- Q3.Distinguish PERT and CPM.
- Q4.What is a dummy activity?
- Q5.Define total float.
- Q6.What is crashing?
Long-answer questions
- Q1.Explain the elements of a queuing system and solve an M/M/1 problem.
- Q2.Explain the construction of networks and determination of the critical path.
- Q3.Explain floats and the calculation of the probability of project completion in PERT.
- Q4.Explain the crashing of a project network with an example.
Stuck on this unit?
Message SBS on WhatsApp for help with Operation Research, or to ask about studying B.Com at Synetic.
