License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2022.32
URN: urn:nbn:de:0030-drops-158421
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/15842/
Goko, Hiromichi ;
Kawamura, Akitoshi ;
Kawase, Yasushi ;
Makino, Kazuhisa ;
Sumita, Hanna
Online Scheduling on Identical Machines with a Metric State Space
Abstract
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.
BibTeX - Entry
@InProceedings{goko_et_al:LIPIcs.STACS.2022.32,
author = {Goko, Hiromichi and Kawamura, Akitoshi and Kawase, Yasushi and Makino, Kazuhisa and Sumita, Hanna},
title = {{Online Scheduling on Identical Machines with a Metric State Space}},
booktitle = {39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
pages = {32:1--32:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-222-8},
ISSN = {1868-8969},
year = {2022},
volume = {219},
editor = {Berenbrink, Petra and Monmege, Benjamin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/15842},
URN = {urn:nbn:de:0030-drops-158421},
doi = {10.4230/LIPIcs.STACS.2022.32},
annote = {Keywords: Online scheduling, Competitive analysis, Online dial-a-ride}
}
|
Keywords: |
|
Online scheduling, Competitive analysis, Online dial-a-ride |
|
Collection: |
|
39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
09.03.2022 |
