Operations Research & Queueing Theory
Cobham Non-Preemptive Priority Queue Waiting Formula
Calculate urgent W_q1 = R_0/(1 - rho_1) and routine W_q2 = R_0/((1 - rho_1)*(1 - rho_1 - rho_2)) M/G/1 waits via Alan Cobham’s (1954) priority formula.
Slash urgent triage wait times without adding servers — and verify Kleinrock conservation!
In hospital emergency triage, fab hot-lots, and QoS packet routing, Urgent Class 1 jobs (arrival rate lambda_1, mean service tau_1, squared CV C_s1^2, utilization rho_1 = lambda_1 * tau_1) jump ahead of Routine Class 2 jobs (lambda_2, tau_2, C_s2^2, rho_2 = lambda_2 * tau_2) in queue WITHOUT interrupting an ongoing service (non-preemptive head-of-line priority). Alan Cobham (1954) proved that with combined residual service time R_0 = 0.5 * (lambda_1 * tau_1^2 * (1 + C_s1^2) + lambda_2 * tau_2^2 * (1 + C_s2^2)) and total utilization rho_tot = rho_1 + rho_2 < 1, urgent wait drops to W_q1 = R_0 / (1 - rho_1) while routine wait becomes W_q2 = R_0 / ((1 - rho_1) * (1 - rho_tot))!
Verify on lambda_1 = 1.0/hr (B2), tau_1 = 0.20 hr (B3 -> rho_1 = 0.20), C_s1^2 = 1.0 (B4), lambda_2 = 2.0/hr (B5), tau_2 = 0.30 hr (B6 -> rho_2 = 0.60, rho_tot = 0.80), and C_s2^2 = 1.0 (B7): residual service R_0 = 0.5 * (0.08 + 0.36) = 0.2200 hr, unprioritized FIFO wait is 0.22 / 0.20 = 1.1000 hr (66 min), Class 1 priority slashes urgent wait 75% to 0.22 / 0.80 = 0.2750 hr (16.5 min!), and Class 2 wait rises modestly to 0.22 / (0.80 * 0.20) = 1.3750 hr (82.5 min) — preserving Kleinrock’s Conservation Law 0.20*0.275 + 0.60*1.375 = 0.8800 = 0.80 * 1.1000!
| Priority Queue Metric (rho_1=0.20, rho_2=0.60, R_0=0.22 hr) | Formula | Verified Output |
|---|---|---|
| Unprioritized FIFO Wait (W_FIFO) | R_0 / (1 - rho_1 - rho_2) | 1.1000 hr (66.0 min) |
| Urgent Priority Class 1 Wait (W_q1) | R_0 / (1 - rho_1) | 0.2750 hr (16.5 min, -75%!) |
| Routine Class 2 Wait (W_q2) | R_0 / ((1 - rho_1) * (1 - rho_1 - rho_2)) | 1.3750 hr (82.5 min) |
| Kleinrock Work Conservation | rho_1 * W_q1 + rho_2 * W_q2 | 0.8800 (= rho_tot * W_FIFO) |
Cobham Urgent Class 1 Expected Queue Wait W_q1 Formula
Validate positive arrival/service rates, C_s^2 >= 0, and system stability rho_1 + rho_2 < 1.
=LET(l_1, B2, t_1, B3, cv_1, B4, l_2, B5, t_2, B6, cv_2, B7, r_1, l_1 * t_1, r_2, l_2 * t_2, IF(OR(l_1 < 0, t_1 <= 0, cv_1 < 0, l_2 < 0, t_2 <= 0, cv_2 < 0, r_1 + r_2 >= 1), "Unstable Queue (Require rho_1 + rho_2 < 1)", LET(r_0, 0.5 * (l_1 * (t_1^2) * (1 + cv_1) + l_2 * (t_2^2) * (1 + cv_2)), ROUND(r_0 / (1 - r_1), 4))))Cobham Routine Class 2 Expected Queue Wait W_q2 Formula
Class 2 waits both for residual service R_0, for existing Class 1 + Class 2 backlog (1 - rho_1 - rho_2), AND for newly arriving Class 1 jobs (1 - rho_1)!
=LET(l_1, B2, t_1, B3, cv_1, B4, l_2, B5, t_2, B6, cv_2, B7, r_1, l_1 * t_1, r_2, l_2 * t_2, IF(OR(l_1 < 0, t_1 <= 0, cv_1 < 0, l_2 < 0, t_2 <= 0, cv_2 < 0, r_1 + r_2 >= 1), "Unstable Queue (Require rho_1 + rho_2 < 1)", LET(r_0, 0.5 * (l_1 * (t_1^2) * (1 + cv_1) + l_2 * (t_2^2) * (1 + cv_2)), ROUND(r_0 / ((1 - r_1) * (1 - r_1 - r_2)), 4))))Try the example
Use the original values or change them to test your understanding.