What does Bottleneck Triage and Value-per-Hour Scheduling conclude, in numbers, about “Streams of Arriving Work: the c-mu Rule, the Generalised c-mu Rule and the Gittins Index”?
Answer: Read the results at three loads. At a load of 0.70, the fixed rule that always gives questions priority costs 2.560 points per task on average and the generalised rule costs 2.769, so the fixed rule is cheaper. At 0.85 the fixed rule costs 6.022 and the generalised rule 6.420, and the fixed rule still wins narrowly. Only at 0.95 does the generalised rule, at 16.998, overtake the fixed rule at 17.348. First come, first served is poor at all three loads and reaches 127.846 per task at 0.95; giving publishing tasks priority is worse still, at 444.840.
Scope of the numbers: Smith proved in 1956 that when one person faces a list, the order that minimises the weighted cost of delay sorts tasks by value divided by duration, not by value; on seven illustrative tasks the importance order pays 0.311 more than the exhaustive optimum. Frustum culling and levels of detail from computer graphics show that a fixed frame budget should not be spent on doing everything finely: doing all eight illustrative tasks finely finishes only three and reaches 0.783 of the best plan.
Data table
The numbers below are printed verbatim by the chapter's Python program and can be reproduced by running it. standard-library Python onlyprinted values that match the answer: 0.70, 0.85, 0.95, 127.846, 16.998, 17.348
| mean delay cost per job (illustrative points) | |||||
| rho | FIFO | A first | B first | gen c-mu | best static |
| 0.70 | 4.864 | 2.560 | 11.419 | 2.769 | 2.560 |
| 0.85 | 19.801 | 6.022 | 56.254 | 6.420 | 6.022 |
| 0.95 | 127.846 | 17.348 | 444.840 | 16.998 | 17.348 |
| switch point: serve A once its head has waited 0.5 hours |
Show the full program
# Chapter 2. p22: convex delay cost and the generalised c-mu rule.
# Two streams into one person, non-preemptive, exponential service:
# A questions from paying customers, mu 3 per hour, cost 2 w^2
# B publishing-queue tasks, mu 2 per hour, cost 3 w
# w = hours waited before service starts (illustrative points).
# Each stream carries half the load. Generalised c-mu (van Mieghem 1995):
# when the person frees up, serve the head job with the largest
# mu_k * C_k'(age of that head job). Fixed-seed discrete-event runs.
import collections
import math
import random
MU = {"A": 3.0, "B": 2.0}
def cost(k, w):
return 2.0 * w * w if k == "A" else 3.0 * w
def slope(k, w):
return 4.0 * w if k == "A" else 3.0
def run(policy, rho, n_jobs=60000):
rng = random.Random(37622)
lam = {k: rho / 2.0 * MU[k] for k in MU}
tot = math.fsum(lam.values())
t_arr, free_at = 0.0, 0.0
q = {"A": collections.deque(), "B": collections.deque()}
costs, served = [], 0
arrivals = []
for _ in range(n_jobs):
t_arr += rng.expovariate(tot)
k = "A" if rng.random() < lam["A"] / tot else "B"
arrivals.append((t_arr, k))
i = 0
while served < n_jobs:
while i < n_jobs and arrivals[i][0] <= free_at:
q[arrivals[i][1]].append(arrivals[i][0])
i += 1
if not q["A"] and not q["B"]:
free_at = arrivals[i][0]
continue
heads = [k for k in "AB" if q[k]]
if policy == "FIFO":
k = min(heads, key=lambda h: q[h][0])
elif policy in ("A first", "B first"):
k = policy[0] if q[policy[0]] else heads[0]
else:
k = max(heads, key=lambda h: MU[h] * slope(h, free_at - q[h][0]))
t0 = q[k].popleft()
costs.append(cost(k, free_at - t0))
free_at += rng.expovariate(MU[k])
served += 1
return math.fsum(costs) / n_jobs
print("mean delay cost per job (illustrative points)")
print("rho FIFO A first B first gen c-mu best static")
for rho in (0.70, 0.85, 0.95):
r = {p: run(p, rho) for p in ("FIFO", "A first", "B first", "gcmu")}
st = min(r["A first"], r["B first"])
print("%.2f %6.3f %7.3f %7.3f %8.3f %10.3f" % (
rho, r["FIFO"], r["A first"], r["B first"], r["gcmu"], st))
print("switch point: serve A once its head has waited 0.5 hours")Single source and citation
Fan, Y. (2026). Stage-Bottleneck Triage, Weighted Shortest-Processing-Time Scheduling and Level-of-Detail Execution Velocity (Version 1.0.0), Chapter 2: Streams of Arriving Work: the c-mu Rule, the Generalised c-mu Rule and the Gittins Index. 5D Library. DOI pending
DOI pending · monograph page goes live after publication · 5DL-B-376 · v1.0.0 · CC-BY-NC-ND-4.0
BibTeX
@book{fan2026376,
author = {Fan, Yafu},
title = {Stage-Bottleneck Triage, Weighted Shortest-Processing-Time Scheduling and Level-of-Detail Execution Velocity},
year = {2026},
publisher = {5D Library},
edition = {1.0.0},
note = {DOI pending}
}Other chapter answers in this book
- Chapter 1 · Why "Most Important First" Is Wrong: Value per Hour and the Adjacent Interchange
- Chapter 3 · The Single Bottleneck of a Phase: a Five-Stage Funnel, Little's Law and the Moving Constraint
- Chapter 4 · Frustum Culling: Tasks with No Causal Path to Cash
- Chapter 5 · Levels of Detail: a Multiple-Choice Knapsack inside a Fixed Focus Budget
- Chapter 6 · No Stalls: Log-Normal Tails, Pooled Buffers and a Focus Budget That Includes Rest
- Chapter 7 · The Classical Sources: Sunzi on Emptiness and Fullness, Mencius on Declining, Seneca's Second Letter and the Law of the Minimum
- Chapter 8 · Field Tools and Checker Specifications: the Daily Scheduling Ledger, the Scheduler and a Pre-registered Test