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
Activity times
Three estimates (optimistic, likely, pessimistic)
One fixed estimate
Nature
Probabilistic
Deterministic
Focus
Time
Time and cost (crashing)
Used for
Research, new projects
Construction, repeat projects
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.