Online Scheduling on Identical Machines with a Metric State Space
Online Scheduling on Identical Machines with a Metric State Space
复制标题
DOI：
10.4230/lipics.stacs.2022.32
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Hiromichi Goko;A. Kawamura;Yasushi Kawase;K. Makino;Hanna Sumita
中科院分区：
文献类型：
--
作者：
Hiromichi Goko;A. Kawamura;Yasushi Kawase;K. Makino;Hanna Sumita
本文在与公制状态空间的同一机器上介绍了一个在线调度问题，该机器通常在相同的机器上使用经典的在线调度问题，在线旅行推销员问题和在线拨号拨号问题。源状态，目标状态，处理时间和释放时间。 （在与距离相对应的时间内），在作业过程之后，机器的状态成为目的地状态，而相关的研究则涉及仅发布时间的模型，本文侧重于一般性目的地状态和处理时间的模型也未知。问题的难度。在时间0。然后，关注未知的目的地状态和处理时间，我们为基本情况构建了O（log M/ log log M） - 竞争算法。
This paper introduces an online scheduling problem on m identical machines with a metric state space, which generalizes the classical online scheduling problem on identical machines, the online traveling salesman problem, and the online dial-a-ride problem. Each job is associated with a source state, a destination state, a processing time, and a release time. Each machine can process a job on and after its release time. Before processing a job, a machine needs to change its state to the source state (in a time corresponding to the distance), and after the process of the job, the machine’s state becomes the destination state. While related research deals with a model in which only release times are unknown to the algorithm, this paper focuses on a general model in which destination states and processing times are also unknown. The main result of this paper is to propose a O (log m/ log log m )-competitive online algorithm for the problem, which is best possible. A key approach is to divide the difficulty of the problem. To cope with unknown release times, we provide frameworks to produce a min { 2 ρ +1 / 2 , ρ +2 } -competitive algorithm using a ρ -competitive algorithm for a basic case where all jobs are released at time 0. Then, focusing on unknown destination states and processing times, we construct an O (log m/ log log m )-competitive algorithm for the basic case. We also provide improved algorithms for some special cases.