Queueing Theory, PERT and CPM

Queueing theory predicts waiting lines; CPM and PERT plan projects made of many activities. Both appear every year in GATE ME as short numerical questions.

The M/M/1 queue

Poisson arrivals at rate λ, exponential service at rate μ, one server, with ρ = λ/μ < 1:

Little's law: L = λW and L_q = λW_q (valid for almost any queue).

Project networks (CPM)

Draw activities as arrows (AOA) or nodes (AON) in order of precedence. For each activity:

• Earliest start (ES) and earliest finish EF = ES + duration (forward pass, take the maximum at merges).
• Latest finish (LF) and latest start LS = LF − duration (backward pass, take the minimum at bursts).
• Total float = LS − ES = LF − EF. Free float = ES of the next activity − EF.

The critical path is the longest path through the network; its activities have zero total float, and its length is the project duration. Delaying a critical activity delays the whole project.

Crashing: shorten critical activities with the lowest cost per unit time first, until another path becomes critical.

PERT

For uncertain activity times with optimistic a, most likely m and pessimistic b:

• Expected time t_e = (a + 4m + b)/6.
• Variance σ² = ((b − a)/6)².
• Project variance = sum of the variances on the critical path. The probability of finishing by time T uses z = (T − T_e)/σ_project with the normal table.

Worked example

Customers arrive at 6 per hour; the server handles 10 per hour.

• ρ = 0.6. L = 6/(10 − 6) = 1.5 customers. W = 1/4 h = 15 minutes.
• L_q = 0.6 × 1.5 = 0.9; W_q = 0.9/6 h = 9 minutes.

Practice