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)
rhoFIFOA firstB firstgen c-mubest static
0.704.8642.56011.4192.7692.560
0.8519.8016.02256.2546.4206.022
0.95127.84617.348444.84016.99817.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