“多人多任务”下如何分工

一个任务给一个人，一个人干一个任务，很多经典的分配算法处理的也正是这种情况。现实里很多场景并不这样安排。一个项目里的测试任务，可能要两三个人一起做；一个能力强的人，也可能同时负责好几个不同的小任务。问题一旦变成这样，原来那些经典漂亮的分配算法就不够用了。

这篇论文讨论的是Many to Many assignment，也就是“多对多分配”问题。要解决的是：一个任务可以交给多个不同的人，一个人也可以承担多个不同任务，怎样安排才能把整体效果做到最好？

这篇论文把一个长期悬着的开放问题，拉回到了一个能真正算、而且还能算得动的层面。作者选的切入口是一个老牌算法Kuhn-Munkres，也就是很多人熟悉的匈牙利算法。这个算法擅长的是“一对一分配”，也就是一个人对一个任务。作者的工作就是想办法在可计算的前提下，把它改造成能处理“多对多”场景。

原来的匈牙利算法像是在给一张“单选题”答卷排答案，每个人只能选一个任务，每个任务也只给一个人；而这篇论文要处理的是“多选题”版本，既允许一个人打多勾，也允许一个任务被多个人共同勾选，但还不能重复乱选。这样一来，整个问题结构都变了。

图 1可以看出：多对多分配里，“什么叫一个可行分配”。论文给的例子里，左边表现矩阵 Q 和右边分配矩阵 T。Q 里每个数字表示某个人做某个任务的效果评分； T 表示最后有没有把这个人分到这个任务上。分配矩阵里，约束L=[1,2,4,2] 和 La=[1,2,3,2,2,2]，总评分是 6.57。说明这篇论文处理问题是有明确规则的：有些任务必须配够几个人，有些人最多只能接几项活。

这篇论文难点在于经典匈牙利算法没法直接拿来用。作者的改进办法是在Kuhn-Munkres 过程中加入“回溯”机制，新算法叫 KMB。核心机制为：如果当前做出的某个配对会让整体分配卡死，不要硬往下走，退回来换一条路继续找。

算法层面，作者证明了KMB 算法是对的，只要找到满足条件的完美匹配，这个结果就是最优的。第二，最坏时间复杂度仍然保持在一个立方量级：O((∑La[i])^3)。说明作者不是通过“暴力穷举”硬撑出结果，而是在尽量把新问题压到和经典可用算法同一个复杂度层级里。

论文专门讨论了什么时候这个问题没有解。你可以理解成：不是所有“多对多分工”要求都能被满足。比如有的任务要求的人手太多，但每个人最多能接的任务数又太低，最后一定会卡死。作者为此专门给出了一个“可判定条件”，正式运行 KMB 之前先检查这个分工要求是不是有可能实现。

图 4 、图 5和表 4可以看出这个方法跑起来到底快不快。作者做了两类实验。第一类，拿 KMB 和穷举算法直接对比，看结果对不对、速度差多少。表 4 里有组数字特别有冲击力：当 m=10 时，KMB 的平均时间还在 0.329 毫秒和 0.571 毫秒这个量级，可穷举法已经飙到了 317028 毫秒和 929525.8 毫秒，最大时间为几百万毫秒。对使用者来说，一个眨眼出结果，一个等到怀疑人生。

第二类实验，观察规模变大时，KMB 能不能撑住。图 5 给出了肯定的结论：随着人数和任务数增加，时间上涨后依旧在可接受的范围里，证明对中等规模的问题是可行的。

局限性在于：第一，虽然 KMB 已经把问题压到了立方复杂度，但回溯本身仍然会让特定情况下跑的较慢。第二，这篇工作讨论的是一种干净的多对多分配约束，暂未把更多现实限制塞进去，比如更复杂的偏好、优先级、动态变化等。

这篇文章告诉我们，传统匈牙利算法那套“找最大权匹配”的思路，并不只困在教科书里，只要肯加回溯、加判定条件，也能解决更真实的团队与任务配置问题。

作者简介：朱海滨，加拿大尼皮辛大学计算机科学教授，IEEE Fellow、AAIA Fellow，E-CARGO模型与Role-Based Collaboration（RBC，基于角色的协作）方法的重要创立学者，现任IEEE Systems, Man, and Cybernetics Society系统科学与工程副主席。主要研究方向包括软件工程、编程技术、协作技术与系统、基于角色的协作、自适应协作，聚焦多智能体系统、群体绩效优化、群体角色分配及E-CARGO模型应用等问题。

ORCID：0000-0003-1922-1631

DOI: 10.1016/j.tcs.2016.01.002

已收藏 0

点赞 0