我们研究了在对抗模型下的单机和相同并行机器上的调度与测试，以最小化总加权完成时间。在此设置中，每个作业都配备有权重、处理时间上限和测试时间。算法可以选择直接执行作业，也可以先进行测试，以揭示可能较低的处理时间。我们首次建立了针对该问题的常数竞争算法，考虑了作业依赖的权重，反映了每个作业的相对重要性。
对于单机调度，我们提出了一种确定性算法，其竞争比为 2.3166，随机变体的竞争比为 2.1523。这些保证与无权重情况下的最佳已知上界相匹配。将这些算法与列表调度相结合，针对相同并行机器调度的竞争比分别为 2.7763 和 2.5110，改进了之前在无权重情况下的最佳已知界限。
博主点评： 本文通过对抗模型提出了调度算法的新思路，尤其是在作业权重和处理时间方面的考虑，使得算法在竞争比上表现突出，具有重要的理论意义与实际应用潜力。