日本フィジカルAI新聞

世界のフィジカルAIを、日本語で。

スケジューリングarXiv:2407.16323

LPTに関する2つの結果:準線形時間アルゴリズムとドローンによる荷物配送

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

シェア:XThreadsFacebookLINEはてブBluesky

LPTヒューリスティックを準線形時間で実装するアルゴリズムを提案し、ドローン配送問題への適用を分析した。

著者: L. Sunil Chandran, Rishikesh Gajjala, Shravan Mehra, Saladi Rahul

分類: cs.DS, cs.CG, cs.RO

原文アブストラクト

The focus of this paper is to increase our understanding of the Longest Processing Time First (LPT) heuristic. LPT is a classical heuristic for the fundamental problem of uniform machine scheduling. For different machine speeds, LPT was first considered by Gonzalez et al (SIAM J. Computing, 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. 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 of lines, which has been well studied in the computational geometry community. Our second contribution is to analyze the performance of LPT for the Drones Warehouse Problem (DWP), which is a natural generalization of the uniform machine scheduling problem motivated by drone-based parcel delivery from a warehouse. In this problem, 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 (where it can also get charged). 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. We prove that the natural approach of solving this problem via the LPT heuristic has an approximation factor of $\phi$, where $\phi \approx 1.62$ is the golden ratio.

関連論文

  1. 1Boston Dynamics、車輪付きAtlasの研究試作機を紹介研究・技術
  2. 2GXOとApptronik、Apolloの物流現場試験を拡大 最大1,000台の展開を構想量産・展開
  3. 3newmoとKDDIが資本業務提携 2028年に堺市で自動運転タクシー商用化目指す提携・買収
  4. 4NVIDIA、CoRLでGR00T 2とIsaac Lab 3.0を発表新製品・発表
  5. 5UC BerkeleyとNVIDIAの研究者、AIエージェントでロボット制御コードを仮想環境で改善研究・技術

PR・アフィリエイト広告

FRONTIER(GPU搭載BTOパソコン)

FRONTIER(GPU搭載BTOパソコン)の公式広告バナーFRONTIERでGPU搭載PCを見る ↗
PR本紙発行元 EmplifAI