What does Bottleneck Triage and Value-per-Hour Scheduling conclude, in numbers, about “Levels of Detail: a Multiple-Choice Knapsack inside a Fixed Focus Budget”?

Answer: Doing everything finely is the most revealing case. Only three of the eight tasks get done, for a total value of 101, which is 0.783 of the optimal plan. Doing everything coarsely finishes all eight tasks but reaches a total of only 58, which is 0.450 of the optimum. Doing everything at medium finishes seven tasks for a total of 114, 0.884 of the optimum: not bad, but still short. The optimal plan reaches 129.

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. printed values that match the answer: 0.450, 0.783, 0.884, 101, 114, 129

rule value tasks done
all coarse58 8 of 8 (0.450 of optimum)
all medium114 7 of 8 (0.884 of optimum)
all fine101 3 of 8 (0.783 of optimum)
LOD optimum129
chosen levels:
K1 checkout copy fine100 min
K2 consult reply fine70 min
P1 chapter edit medium80 min
P2 cover brief medium40 min
V1 video script coarse30 min
V2 thumbnail coarse10 min
S1 restock sheet coarse20 min
S2 ledger notes coarse10 min
minutes used 360 of 360
Show the full program
# Chapter 5. p51: level of detail as a multiple-choice knapsack.
# A focus budget of 360 minutes (breaks are budgeted separately, see
# chapter 6). Eight tasks, each done at one level: skip, coarse, medium
# or fine, with (minutes, value). Values are concave in minutes; the two
# checkout-node tasks (K1, K2) lose most of their value when done
# coarsely. Exact dynamic programme over 10-minute units versus three
# uniform rules: all coarse, all medium, all fine (uniform rules take
# tasks in w/p order of that level until the budget runs out).
# All minutes and values are illustrative.
TASKS = [  # name, [(min, val) coarse, medium, fine]
    ("K1 checkout copy", [(30, 8), (60, 30), (100, 44)]),
    ("K2 consult reply", [(20, 6), (40, 22), (70, 30)]),
    ("P1 chapter edit", [(40, 14), (80, 22), (160, 27)]),
    ("P2 cover brief", [(20, 6), (40, 9), (90, 11)]),
    ("V1 video script", [(30, 10), (60, 15), (120, 18)]),
    ("V2 thumbnail", [(10, 4), (20, 6), (50, 7)]),
    ("S1 restock sheet", [(20, 7), (40, 10), (80, 11)]),
    ("S2 ledger notes", [(10, 3), (30, 5), (60, 6)]),
]
BUDGET = 360
LEVELS = ["skip", "coarse", "medium", "fine"]


def dp():
    n, cap = len(TASKS), BUDGET // 10
    best = [[-1.0] * (cap + 1) for _ in range(n + 1)]
    pick = [[0] * (cap + 1) for _ in range(n + 1)]
    best[0] = [0.0] * (cap + 1)
    for i, (_, opts) in enumerate(TASKS):
        choices = [(0, 0)] + opts
        for b in range(cap + 1):
            for lv, (m, v) in enumerate(choices):
                u = m // 10
                if u <= b and best[i][b - u] + v > best[i + 1][b]:
                    best[i + 1][b] = best[i][b - u] + v
                    pick[i + 1][b] = lv
    lv, b = [], cap
    for i in range(n, 0, -1):
        lv.append(pick[i][b])
        b -= ([(0, 0)] + TASKS[i - 1][1])[pick[i][b]][0] // 10
    return best[n][cap], lv[::-1]


def uniform(level):
    def ratio(i):
        m, v = TASKS[i][1][level]
        return -v / m
    order = sorted(range(len(TASKS)), key=ratio)
    left, val, used = BUDGET, 0, 0
    for i in order:
        m, v = TASKS[i][1][level]
        if m <= left:
            left -= m
            val += v
            used += 1
    return val, used


opt, lv = dp()
print("rule          value  tasks done")
for k, name in ((0, "all coarse"), (1, "all medium"), (2, "all fine")):
    v, u = uniform(k)
    print("%-12s  %5d  %d of 8   (%.3f of optimum)" % (name, v, u, v / opt))
print("LOD optimum   %5d" % opt)
print("chosen levels:")
mins = 0
for (name, opts), l in zip(TASKS, lv):
    m = ([(0, 0)] + opts)[l][0]
    mins += m
    print("  %-18s %-6s %3d min" % (name, LEVELS[l], m))
print("minutes used %d of %d" % (mins, BUDGET))

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 5: Levels of Detail: a Multiple-Choice Knapsack inside a Fixed Focus Budget. 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