2026-07-25T05:49:17Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15842 2024-03-06T10:56:19Z ddc:004 open_access

Online Scheduling on Identical Machines with a Metric State Space Goko, Hiromichi Kawamura, Akitoshi Kawase, Yasushi Makino, Kazuhisa Sumita, Hanna Online scheduling Competitive analysis Online dial-a-ride 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Hiromichi Goko and Akitoshi Kawamura and Yasushi Kawase and Kazuhisa Makino and Hanna Sumita 2022 Is Part Of LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2022.32 urn:nbn:de:0030-drops-158421 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.32 eng https://creativecommons.org/licenses/by/4.0/legalcode