What does Zero-Courier Dispatch conclude, in numbers, about “Multi-Agent Claiming: Contract-Net Bidding, Graham's List Scheduling and Timing Anomalies”?

Answer: Chapter 3 covers contract-net claiming and Graham's list scheduling and reproduces a timing anomaly: three executors finish in 12, four need 15.

Scope of the numbers: Its parameters are illustrative and all calculations are generated by its programs. It names no server, account, key or deployment command, and it is general business analysis, not personalised advice.

中文版

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: 12

case agents makespan
baseline3 12.0
one more agent4 15.0
every task 1 h shorter3 13.0
two precedence edges removed3 16.0
Graham bound 1 + (m - 1) / m' for m 34: 1.5000
observed ratio 4 agents / 3 agents1.2500
total work 34 h; lower bound on 3 agents 11.33 h
longest chain T1 -> T912 h
Show the full program
# Chapter 3. p32: Graham's timing anomalies under greedy list dispatch.
# Model: greedy list scheduling - whenever an agent is idle it takes
# the first ready task in the priority list. Instance: nine tasks of
# the classic textbook example used to illustrate Graham (1966, 1969):
# times 3,2,2,2,4,4,4,4,9; T1 precedes T9; T4 precedes T5 to T8. We
# then add an agent, shorten every task by one hour, and drop two
# precedence edges; each "improvement" lengthens the schedule.
import heapq

TIMES = [3, 2, 2, 2, 4, 4, 4, 4, 9]
EDGES = [(1, 9), (4, 5), (4, 6), (4, 7), (4, 8)]


def list_schedule(times, edges, m, order=None):
    n = len(times)
    order = order or list(range(1, n + 1))
    pred = {i: set() for i in range(1, n + 1)}
    for u, v in edges:
        pred[v].add(u)
    done, started = {}, set()
    free = [0.0] * m
    events = []
    t = 0.0
    while len(done) < n:
        idle = [k for k in range(m) if free[k] <= t]
        for k in idle:
            for task in order:
                if task in started:
                    continue
                if all(p in done and done[p] <= t for p in pred[task]):
                    started.add(task)
                    free[k] = t + times[task - 1]
                    heapq.heappush(events, (free[k], task))
                    break
        if not events:
            break
        t, task = heapq.heappop(events)
        done[task] = t
        while events and events[0][0] == t:
            t2, task2 = heapq.heappop(events)
            done[task2] = t2
    return max(done.values())


if __name__ == "__main__":
    base = list_schedule(TIMES, EDGES, 3)
    more = list_schedule(TIMES, EDGES, 4)
    short = list_schedule([x - 1 for x in TIMES], EDGES, 3)
    loose = list_schedule(TIMES, EDGES[:1] + EDGES[3:], 3)
    print("case                              agents  makespan")
    print("baseline                               3  {:>8}".format(base))
    print("one more agent                         4  {:>8}".format(more))
    print("every task 1 h shorter                 3  {:>8}".format(short))
    print("two precedence edges removed           3  {:>8}".format(loose))
    print("Graham bound 1 + (m - 1) / m' for m 3 -> 4: {:.4f}".format(
        1 + (3 - 1) / 4))
    print("observed ratio 4 agents / 3 agents: {:.4f}".format(more / base))
    total = 0
    for x in TIMES:
        total += x
    print("total work {} h; lower bound on 3 agents {:.2f} h".format(
        total, total / 3))
    print("longest chain T1 -> T9 = {} h".format(TIMES[0] + TIMES[8]))

Single source and citation

Fan, Y. (2026). Commander Intent Compilation, Automated DAG Task Decomposition and Zero-Courier Multi-Agent Dispatch (Version 1.0.0), Chapter 3: Multi-Agent Claiming: Contract-Net Bidding, Graham's List Scheduling and Timing Anomalies. 5D Library. DOI pending

DOI pending · monograph page goes live after publication · 5DL-B-407 · v1.0.0 · CC-BY-NC-ND-4.0

BibTeX
@book{fan2026407,
  author    = {Fan, Yafu},
  title     = {Commander Intent Compilation, Automated DAG Task Decomposition and Zero-Courier Multi-Agent Dispatch},
  year      = {2026},
  publisher = {5D Library},
  edition   = {1.0.0},
  note      = {DOI pending}
}

Other chapter answers in this book