Allocation Problem in Remote Teleoperation: Online Matching with Offline Reusable Resources and Delayed Assignments
Allocation Problem in Remote Teleoperation: Online Matching with Offline Reusable Resources and Delayed Assignments
复制标题
DOI：
10.5555/3545946.3598678
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Osnat Ackerman Viden;Yohai Trabelsi;Pan Xu;Karthik Abinav Sankararaman;Oleg Maksimov;Sarit Kraus
中科院分区：
文献类型：
--
作者：
Osnat Ackerman Viden;Yohai Trabelsi;Pan Xu;Karthik Abinav Sankararaman;Oleg Maksimov;Sarit Kraus
许多应用程序中的任务应该分配给代理可以建模为二分图中的匹配。在本文中，我们考虑的应用程序，任务到达动态和拒绝的任务可能会有显着的不利影响的请求者，因此执行任务的一些延迟是首选完全拒绝。任务的执行时间取决于任务、代理和分配，并且只有其分布是预先知道的。实际时间只有在执行任务后座席可用于新分配时才知道。我们认为这种应用程序是两种到达类型之一。对于第一种类型，到达分布是预先已知的，而对于第二种类型，没有关于到达时间和顺序的假设。对于第一种类型，我们提出了一个基于LP的在线算法，竞争比为0。5.对于第二种类型，我们没有一个恒定的竞争比的在线算法。我们运行了大量的实验，以评估我们的算法在现实世界的数据集，展示了LP方法的优势。
Many applications where tasks should be assigned to agents can be modeled as matching in bipartite graphs. In this paper, we consider applications where tasks arrive dynamically and rejection of a task may have significant adverse effects on the requester, therefore performing the task with some delay is preferred over complete rejection. The performance time of a task depends on the task, the agent, and the assignment, and only its distribution is known in advance. The actual time is known only after the task performance when the agent is available for a new assignment. We consider such applications to be one of two arrival types. With the first type, the arrival distribution is known in advance, while there is no assumption about the arrival times and order with the second type. For the first type, we present an LP-based online algorithm with a competitive ratio of 0 . 5. For the second type, we show no online algorithm with a constant competitive ratio. We run extensive experiments to evaluate our algorithm in a real-world dataset, demonstrating the advantages of the LP approach.