Near-Linear Time Scheduling for Drone-Based Parcel Delivery from a Warehouse

We consider the problem where a warehouse has multiple drones and wants to deliver parcels to several customers. Each drone picks a parcel from the warehouse, delivers it and returns to the warehouse. The speeds and battery lives of the drones could be different and due to the limited battery life, each drone has a bounded range in which it can deliver parcels. The goal is to assign parcels to the drones so that the time taken to deliver all the parcels is minimized. This turns out to be an NP-hard problem, and hence, the focus of this article is to design a fast approximation algorithm. We do this by adapting the Longest Processing Time First (LPT) heuristic, which is a classical heuristic for the fundamental problem of uniform machine scheduling to the Drones Warehouse Problem (DWP) , which is a natural generalization of the uniform machine scheduling problem. We prove that the natural approach of solving this problem via the LPT heuristic has an approximation factor of ϕ, where ϕ ≈ 1.62 is the golden ratio. LPT heuristic was first considered by Gonzalez et al. (SIAM J. Comput. 6(1):155–166, 1977) . Since then, extensive work has been done to improve the approximation factor of the LPT heuristic. However, all known implementations of the LPT heuristic take O(mn) time, where m is the number of machines and n is the number of jobs. In this work, we come up with the first near-linear time implementation for LPT both for DWP and Uniform Scheduling. Specifically, the running time is O((n+m) (log 2 m +log n )). Somewhat surprisingly, the result is obtained by mapping the problem to dynamic maintenance of lower envelope lines, which has been well-studied in the computational geometry community.