Two Results on LPT: A Near-Linear Time Algorithm and Parcel Delivery using Drones

本文的重点是增加我们对最长处理时间优先（LPT）启发式算法的理解。LPT是一种用于均匀机器调度基本问题的经典启发式算法。对于不同的机器速度，Gonzalez等人（SIAM J. Computing，1977）首次考虑了LPT。自那时以来，已经进行了大量工作来改进LPT启发式算法的近似因子。然而，所有已知的LPT启发式算法实现都需要$O(mn)$时间，其中$m$是机器数量，$n$是作业数量。在这项工作中，我们提出了第一个近似线性时间的LPT实现。具体而言，运行时间为$O((n+m)(\log^2{m}+\log{n}))$。有些令人惊讶的是，这个结果是通过将问题映射到线的下凸壳的动态维护来获得的，这在计算几何学界已经得到了广泛研究。 我们的第二个贡献是分析LPT在无人机仓库问题（DWP）中的性能，该问题是均匀机器调度问题的自然推广，其动机是基于从仓库进行基于无人机的包裹递送。在这个问题中，一个仓库有多个无人机，想要将包裹送到几个客户那里。每个无人机从仓库取出一个包裹，递送它，然后返回仓库（在那里它也可以充电）。无人机的速度和电池寿命可能不同，由于电池寿命有限，每个无人机在其可以递送包裹的有界范围内。目标是将包裹分配给无人机，以使递送所有包裹所需的时间最小化。我们证明了通过LPT启发式算法解决这个问题的自然方法具有近似因子$\phi$，其中$\phi \approx 1.62$是黄金比例。

研究Longest Processing Time First (LPT)启发式算法在机器调度和无人机仓库问题中的应用

将LPT问题映射到线的下凸壳的动态维护中，实现了第一个近线性时间复杂度的LPT算法实现。同时，分析了LPT在无人机仓库问题中的性能表现，证明了LPT的近似比为黄金分割数。

论文提出了第一个近线性时间复杂度的LPT算法实现，并分析了LPT在无人机仓库问题中的性能表现。

与本文相关的研究包括Gonzalez等人的研究以及LPT启发式算法的改进研究。