在并行任务调度（PTS）问题中，我们需要调度 $n$ 个作业，每个作业都有固定的处理时间和机器需求，以最小化最后一个作业的完成时间。Jansen 和 Rau（2019）提出了一种 PTS 算法，其近似比为 $(3/2)\mathrm{OPT} + p_{\max}$。他们还提出了一个开放性问题，即是否可能实现近似比为 $(4/3)\mathrm{OPT} + p_{\max}$。在本研究中，我们展示了一种这样的算法，运行时间为 $O(n\log n)$。
多集群调度（MCS）是 PTS 的自然扩展，其中我们有 $N$ 个集群，每个集群有 $m$ 台机器来调度作业。Jansen 和 Rau（2019）将他们的 PTS 算法适应于 MCS，取得了以下结果：（1）2 的近似，和（2）如果 $N$ 能被 3 整除，则近似比为接近线性的 $9/4$。我们改进了他们的 2-近似的运行时间，并将 $9/4$ 的近似推广到一般情况。MCS 的 2-近似是紧的，因为除非 P=NP，否则无法期望获得比 2 更好的近似比 [Zhuk, 2006]。除了我们的理论结果，我们还实现了我们的算法，并展示了它的实际适用性。
博主点评： 本文提出的算法在理论与实践上都具有重要意义，尤其是对于并行任务调度和多集群调度问题的高效解决方案，展示了优化算法在处理复杂调度问题中的潜力。