集体调度中的聚合规则：公理、复杂度与高效算法

《Discrete Applied Mathematics》：Collective schedules: Axioms and algorithms

　　

集体调度：公理与算法
•对聚合规则进行理论分析，提出考虑任务长度的新性质。
•ΣD规则的复杂性结果：一般情形为NP-hard，两个选民时可在多项式时间内计算。
•带预处理的新的动态规划算法，显著快于先前基于ILP的方法。
•一个反例证明PTA-Kemeny规则不满足LRM，修正了此前的猜想。

集体调度问题由Pascual等人引入，其输入为v位选民对n个具有处理时间（processing time）p_i任务的首选调度，输出一个共识调度。该问题广泛应用于公共基础设施的阶段性建设、共享空间事件安排等场景，并推广了经典共识排序问题。现有共识排序规则（如Kemeny规则）未考虑任务时长，且只关注排序前端；已有调度规则（如ΣT规则）虽考虑了延迟，但缺乏系统的公理分析，计算复杂性也较高。此外，PTA-Kemeny规则是否满足长度减少单调性（Length Reduction Monotonicity，LRM）——即任务长度缩短后其开始时间不推迟——此前存在猜想，但未被证明或否定。为此，研究人员从公理、计算复杂性和算法设计三方面系统研究了这一问题。

研究人员定义了四个聚合规则：ΣD规则（最小化总绝对偏差）、ΣT规则（最小化总延迟）、PTA Kemeny规则（最小化加权Kendall tau距离）和EMD规则（按中位数完成时间排序）。通过理论分析，他们证明了这些规则满足或违反多个新提出的公理；通过复杂性归约，证明ΣD一般情形强NP难；设计了带预处理的动态规划算法和局部搜索启发式，并进行了大规模实验。研究意义在于：为集体调度这一交叉领域提供了系统的公理框架和高效算法，修正了PTA-Kemeny规则满足LRM的错误猜想。

在关键技术上，研究人员采用动态规划（Dynamic Programming，DP）精确求解最优化规则，通过预处理构造时间表、成本表和梯度表，将目标函数计算降为常数时间，整体复杂度为O(nv+2ⁿ·n·min(log v,n))。对于EMD规则，采用局部搜索（local search）算法，通过交换相邻任务迭代改进初始解。实验使用合成实例，偏好分别来自均匀分布和Plackett-Luce模型，任务长度在1~10间均匀随机。

在研究结果方面，本文按三个子主题总结如下。

**性质分析。** 通过理论证明与构造反例，研究人员得到：四个规则均满足PTA中性（PTA Neutrality）；ΣD规则基于距离，但任何基于距离最小化的规则都不满足PTA Condorcet一致性，且不能为ΣT提供任意常数近似；PTA Kemeny满足PTA Condorcet一致性，EMD不满足；EMD满足LRM，而ΣD和PTA Kemeny不满足，后者通过线性规划生成的反例修正了之前的猜想；PTA Kemeny满足reinforcement，EMD不满足；EMD满足unanimity，ΣD和PTA Kemeny不满足（但若短任务a被所有选民排在长任务b前，则PTA Kemeny和ΣT存在将a置于b前的优解）。

**计算复杂性。** 定理1从单机无空闲调度问题(1|no?idle|ΣD)构造多项式归约，证明ΣD问题的优化是强NP难的；当只有2个选民时，由于ΣD是距离，最优解必为其中一个选民的调度，因此多项式可解。EMD通过计算每个任务中位数完成时间并排序，复杂度为O(nv+n log n)。

**算法与实验。** 动态规划算法求解ΣD、ΣT和PTA Kemeny，对20个任务、5000选民的实例平均仅需约2秒，显著快于先前基于整数线性规划（ILP）的4.5秒。EMD加局部搜索平均总偏差比最优仅高不到1%，总延迟高约13%，且运行时间小于0.1秒。规则比较显示ΣT和PTA Kemeny给出的调度非常相似，而ΣD更贴近输入偏好。在1200个实例的LRM测试中，PTA Kemeny和ΣT均未违规，ΣD违规率为8.5%。

在讨论中，研究人员指出PTA Kemeny和ΣT适用于“越早越好”（EB）假设的场景，其中ΣT天然适合最小化延迟，PTA Kemeny因满足PTA Condorcet一致性而表现良好；ΣD按构造更适合非EB场景，且不满足unanimity等性质。EMD虽不满足reinforcement，但因其多项式时间、满足LRM以及保证所有选民偏好顺序的优先约束，仍是EB设置的优秀候选；实验显示其更接近ΣD，故也适合非EB。最后，研究人员翻译了研究结论如下：

“研究人员从公理和计算角度研究了集体调度问题的四个自然规则。该问题推广了集体排序问题，即所有任务为单位长度的特殊情形。这四个规则要么扩展了已知的集体排序规则（PTA Kemeny规则推广Kemeny规则，ΣD规则推广Spearman footrule），要么是尚未在集体排序语境中考虑过的规则（ΣT和EMD）。后者也可能对集体排序有价值。研究人员证明了性质之间的若干不相容性，表明基于距离的规则不满足PTA Condorcet一致性，且不近似最小总延迟。他们从公理、计算和实验三个角度比较了四个规则，结果支持PTA Kemeny和ΣT规则特别适合EB设置。ΣT规则设计上自然适应此类设置，PTA Kemeny规则则因满足PTA Condorcet一致性而表现良好，实验也观察到两者输出非常相似。相比之下，ΣD规则按其构造更适合非EB设置，且不满足unanimity等对EB重要的性质。EMD规则虽不满足reinforcement，但有若干优点：可多项式时间计算，且是唯一保证若所有选民偏好a先于b则将a排在b前的规则，这确保其尊重优先约束；同时EMD满足LRM，因此是EB设置的优秀候选。然而实验显示EMD更接近ΣD，故也适用于非EB。最后，研究人员猜想ΣT满足LRM，该行为在实验中被一致观察到，但公理证明仍是开放问题。未来可将集体调度扩展至额外约束（如优先约束、释放日期）或多机器环境，并研究资源投入的影响。”