4.1 派活的艺术：任务分配与调度

4.1 派活的艺术：任务分配与调度

摘要：任务分配回答"哪个镇民在什么时候干哪件活"。本节给出分配问题的形式化框架，过中心化指派、贪心分配、市场化竞价、组合拍卖四类机制，比较最优性与通信开销，并用代码实验对照最优指派与贪心的差距、展示负载敏感市场机制的自我纠偏。

收割季节的清晨，合作社门口站着一排等着派活的镇民，墙上贴着一列农活：东边割麦、西边浇水、谷仓晾晒。谁去哪儿，看似人事小事，实则是多智能体系统里被研究得最透的工程问题——任务分配。上一章镇民学会了谈判与守规，这一章开市政厅，第一件事就是建立派活制度。本节是第 4 章的起点：先把问题说清楚，再看四类机制各自的解法与代价。

问题的形式化骨架

任务分配的标准建模：镇民集（各有能力与当前负载）、任务集（各有技能要求、时长、截止时间）、代价或收益矩阵（镇民干某活的成本与产出），目标是在约束（技能匹配、时序、容量）下最小化总成本或最大化总收益。它跟运筹学的指派问题是近亲——镇民数与任务数相等、代价给定、无时序耦合时，匈牙利算法多项式时间求最优；但真实 MAS 的麻烦在于三处松动：代价矩阵是私有的（镇民知道自己的成本，调度者不知道）、任务是流式到达的、镇民负载动态变化。这三处松动，恰好把后面的机制串成一部演化史。

中心化指派：调度者收齐所有人的成本自报，跑指派算法，下令分工。最优、一次成型；但要求成本可信（谎报怎么办）、调度者是单点、不适应流式任务。适合封闭车间。

贪心分配：任务按序处理，每次派给"当前最便宜的空闲镇民"。零协调、可流式；最坏情况离最优很远——两个便宜活全派给同一个镇民，贵的活留给后面的人手不足。适合任务廉价、错了能重来的场景。

市场化竞价：第 3 章合同网的直接应用——每个任务招标，镇民按自身边际成本投标，价低者得。成本私有没关系（报价已经含了私货），负载动态没关系（投标价随负载上涨）。代价是每单生意的通信与协商开销，以及贪婪授标不保证全局最优。

组合拍卖：任务之间有协同（谷仓晾晒与运麦同地，打包给一人省一趟路），逐个招标会拆散协同。让镇民对"任务包"竞价，调度者选总报价最低的任务包组合。协同红利兑现，但求解（组合选择）本身是 NP 难，通信量也暴涨。

图 4-1 四类分配机制的能力画像

实验一：最优指派对贪心分配

先把"贪心有多差"量化。四个镇民五件活，代价矩阵给定：小规模用穷举求全局最优，贪心则逐活挑当前最便宜的人。

from itertools import permutations

COST = {                     # 代价矩阵：镇民 -> {任务: 成本}
    "anna":  {"mow": 4, "water": 6, "haul": 9, "sort": 5},
    "bela":  {"mow": 8, "water": 5, "haul": 6, "sort": 7},
    "chen":  {"mow": 7, "water": 9, "haul": 5, "sort": 8},
    "dora":  {"mow": 6, "water": 4, "haul": 7, "sort": 6},
}
TASKS = ["mow", "water", "haul", "sort"]

def brute_force():
    """穷举所有一对一分配，求总成本最小。"""
    best, best_plan = None, None
    for perm in permutations(COST.keys(), len(TASKS)):
        total = sum(COST[p][t] for p, t in zip(perm, TASKS))
        if best is None or total < best:
            best, best_plan = total, dict(zip(TASKS, perm))
    return best, best_plan

def greedy():
    """逐活派给当前最便宜的空闲镇民（贪心从不回头）。"""
    plan, used, total = {}, set(), 0
    for t in TASKS:
        c, a = min((COST[a][t], a) for a in COST if a not in used)
        plan[t], used, total = a, used | {a}, total + c
    return total, plan

opt, opt_plan = brute_force()
gre, gre_plan = greedy()
print(f"最优: {opt} {opt_plan}")
print(f"贪心: {gre} {gre_plan}  偏离 {(gre-opt)/opt:.0%}")
​

跑出来的差距可能不大（四乘四的小算例贪心未必翻车），但把矩阵里的数字挪一挪——比如让"割草最便宜的人同时也是别的活的关键好手"——贪心立刻露馅：它对"每活最便宜"的局部迷恋，会把关键的多面手早早占用，让后面的活只剩贵手可用。贪心解连稳定都谈不上（换任务顺序结果就变），这正是市场化机制要治的病。

实验二：市场机制的负载自纠偏

市场化竞价的杀手锏是自适应。下面的实验让任务流式到达，镇民投标价随自身负载上浮；对比"贪心不看负载"与"市场看负载"两种派法，观察完工时间。

import random

class Worker:
    def __init__(self, name, base, speed):
        self.name, self.base, self.speed = name, base, speed
        self.queue = []                     # 已接任务

    def quote(self, task):
        """投标价 = 基础成本 × (1 + 排队深度)。越忙报价越贵。"""
        load = len(self.queue)
        return self.base * (1 + 0.8 * load) + task["size"] / self.speed

    def finish_time(self):
        return sum(t["size"] / self.speed for t in self.queue)

def dispatch_stream(tasks, workers, market=True):
    makespan_hist = []
    for t in tasks:
        if market:                          # 市场化：负载进报价
            w = min(workers, key=lambda w: w.quote(t))
        else:                               # 贪心：只看基础成本
            w = min(workers, key=lambda w: w.base)
        w.queue.append(t)
        makespan_hist.append(max(x.finish_time() for x in workers))
    return max(w.finish_time() for w in workers), makespan_hist[-1]

random.seed(21)
workers = [Worker("w1", base=5, speed=2), Worker("w2", base=6, speed=3),
           Worker("w3", base=7, speed=4)]
tasks = [{"name": f"job{i}", "size": random.uniform(4, 10)}
         for i in range(15)]

span_greedy, _ = dispatch_stream(tasks, [Worker(w.name, w.base, w.speed)
                                         for w in workers], market=False)
span_market, _ = dispatch_stream(tasks, [Worker(w.name, w.base, w.speed)
                                         for w in workers], market=True)
print(f"贪心派活 总完工 {span_greedy:.1f}")
print(f"市场派活 总完工 {span_market:.1f}")
​

贪心派活反复把任务塞给"基础成本最低"的快手，快手过载、慢手吃灰；市场机制让快手的报价随队列上涨，任务自动流向"综合最划算"的人，总完工时间显著缩短。价格是负载的信号灯——这是市场化派活的核心直觉，也是它不需要全局信息的底气。

⚠️ 常见坑：把调度目标偷换成"单任务成本最小"。派活要盯的是全局指标（总完工、最晚完工、截止违约率），单任务的便宜常常是全局的贵——快递员都爱送近件，远件就永远没人送。

调度的时序维度：截止时间进场

分配之上还有调度：不只谁干，还有先后。经典工具箱里，EDD（最早截止优先）最小化最大延迟，SPT（最短优先）最小化平均完工；分布式版本里每个镇民本地排序，再靠拍卖微调跨镇民的先后。这些启发式在单机调度教材里有完整谱系，MAS 的贡献是把它们改造成"没有全局视野也能跑"的版本：比如每个镇民用 EDD 排本地队列，跨镇民的资源冲突（两人在同一时段抢同一台烘干机）交给下一节的协调机制或 DCOP 处理。

💡 关键直觉：分配与调度的所有花样，本质都在回答同一个问题——私有信息怎么汇集、动态变化怎么跟上。中心化用"上报"汇集、用"重算"跟上；市场用"报价"汇集、用"价格"跟上。理解了这一点，看到新机制就能迅速归类。

沙盘推演小结

合作社的派活板换了两代：先是指派表（最优但僵化），后来改成招标板（自适应但话多）。收割结束，账本显示市场化派活的总完工最短，代价是邮局的邮票消耗翻了倍。下一节追问一个更根本的问题：派完活之后，怎么保证一群镇民在执行中不分道扬镳——有人遇阻该通知谁、有人退出谁兜底、共同的承诺靠什么维系。