Document Open Access Logo

Online Scheduling on Identical Machines with a Metric State Space

Authors Hiromichi Goko, Akitoshi Kawamura, Yasushi Kawase, Kazuhisa Makino, Hanna Sumita

PDF

File

Thumbnail PDF
PDF
LIPIcs.STACS.2022.32.pdf
  • Filesize: 0.71 MB
  • 21 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Theory of computation → Online algorithms
Keywords
  • Online scheduling
  • Competitive analysis
  • Online dial-a-ride

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

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.

Cite As Get BibTex

Hiromichi Goko, Akitoshi Kawamura, Yasushi Kawase, Kazuhisa Makino, and Hanna Sumita. Online Scheduling on Identical Machines with a Metric State Space. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 32:1-32:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.STACS.2022.32

Author Details

Hiromichi Goko
  • Toyota Motor Corporation, Aichi, Japan
Akitoshi Kawamura
  • Kyoto University, Japan
Yasushi Kawase
  • University of Tokyo, Japan
Kazuhisa Makino
  • Kyoto University, Japan
Hanna Sumita
  • Tokyo Institute of Technology, Japan

Funding

This work was partially supported by the joint project of Kyoto University and Toyota Motor Corporation, titled "Advanced Mathematical Science for Mobility Society", JST PRESTO Grant Number JPMJPR2122, and JSPS KAKENHI Grant Numbers JP17K12646, JP19K22841, JP20H05967, JP20K19739, JP21K17708, and JP21H03397.

References

  1. Norbert Ascheuer, Sven O. Krumke, and Jörg Rambau. Online Dial-a-Ride Problems: Minimizing the Completion Time. In Proceedings of STACS, volume 1770, pages 639-650, 2000. Google Scholar
  2. G. Ausiello, E. Feuerstein, S. Leonardi, L. Stougie, and M. Talamo. Algorithms for the On-Line Travelling Salesman. Algorithmica, 29(4):560-581, 2001. Google Scholar
  3. Giorgio Ausiello, Esteban Feuerstein, Stefano Leonardi, Leen Stougie, and Maurizio Talamo. Competitive algorithms for the on-line traveling salesman. In Proceedings of the 4th Workshop on Algorithms and Data Structures, pages 206-217, 1995. Google Scholar
  4. Alexander Birx. Competitive analysis of the online dial-a-ride problem. PhD thesis, Technische Universität Darmstadt, 2020. Google Scholar
  5. Alexander Birx and Yann Disser. Tight analysis of the smartstart algorithm for online dial-a-ride on the line. SIAM Journal on Discrete Mathematics, 34(2):1409-1443, 2020. Google Scholar
  6. Alexander Birx, Yann Disser, and Kevin Schewior. Improved bounds for open online dial-a-ride on the line. In Proceedings of Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM), volume 145, 2019. Google Scholar
  7. Antje Bjelde, Jan Hackfeld, Yann Disser, Christoph Hansknecht, Maarten Lipmann, Julie Meißner, Miriam Schlöter, Kevin Schewior, and Leen Stougie. Tight Bounds for Online TSP on the Line. ACM Transactions on Algorithms, 17(1):1-58, 2021. Google Scholar
  8. Michiel Blom, Sven O Krumke, Willem E de Paepe, and Leen Stougie. The online tsp against fair adversaries. INFORMS Journal on Computing, 13(2):138-148, 2001. Google Scholar
  9. Vincenzo Bonifaci, Maarten Lipmann, and Leen Stougie. Online multi-server dial-a-ride problems. SPOR-Report : reports in statistics, probability and operations research. Technische Universiteit Eindhoven, 2006. Google Scholar
  10. Esteban Feuerstein and Leen Stougie. On-line single-server dial-a-ride problems. Theoretical Computer Science, 268(1):91-105, 2001. Google Scholar
  11. Greg N. Frederickson, Matthew S. Hecht, and Chul E. Kim. Approximation Algorithms for Some Routing Problems. SIAM Journal on Computing, 7(2):178-193, 1978. Google Scholar
  12. Giorgio Gambosi and Gaia Nicosia. On-line scheduling with setup costs. Information Processing Letters, 73(1-2):61-68, 2000. Google Scholar
  13. R. L. Graham. Bounds for Certain Multiprocessing Anomalies. Bell System Technical Journal, 45(9):1563-1581, 1966. Google Scholar
  14. Dan Gusfield. Bounds for naive multiple machine scheduling with release times and deadlines. Journal of Algorithms, 5(1):1-6, 1984. Google Scholar
  15. Leslie A. Hall and David B. Shmoys. Approximation schemes for constrained scheduling problems. In Proceedings of Annual Symposium on Foundations of Computer Science, pages 134-139, 1989. Google Scholar
  16. Hongtao Hu, K. K.H. Ng, and Yichen Qin. Robust Parallel Machine Scheduling Problem with Uncertainties and Sequence-Dependent Setup Time. Scientific Programming, 2016, 2016. Google Scholar
  17. Patrick Jaillet and Michael R. Wagner. Generalized online routing: New competitive ratios, resource augmentation, and asymptotic analyses. Operations Research, 56(3):745-757, 2008. Google Scholar
  18. Sven O. Krumke. Online optimization: Competitive analysis and beyond. PhD thesis, Technische Universität Berlin, 2001. Google Scholar
  19. Maarten Lipmann, Xiwen Lu, Willem E. de Paepe, Rene A. Sitters, and Leen Stougie. On-Line Dial-a-Ride Problems Under a Restricted Information Model. Algorithmica, 40(4):319-329, 2004. Google Scholar
  20. David M Miller, Hui-Chuan Chen, Jessica Matson, and Qiang Liu. A hybrid genetic algorithm for the single machine scheduling problem. Journal of Heuristics, 5(4):437-454, 1999. Google Scholar
  21. David B. Shmoys, Joel Wein, and David P. Williamson. Scheduling parallel machines on-line. SIAM Journal on Computing, 24(6):1313-1331, 1995. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact