Online Busy Time Scheduling with Untrusted Prediction

Rick van de Bovenkamp; Alison Hsiang Hsuan Liu

doi:10.1007/978-3-031-82697-9_24

Online Busy Time Scheduling with Untrusted Prediction

Rick van de Bovenkamp, Alison Hsiang Hsuan Liu^*

^*Corresponding author for this work

Sub Algorithms and Complexity

Utrecht University

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

Abstract

In this work, we study the online busy time scheduling problem with infinite processors, where each job j has a release time r_j, a processing time p_j, and a deadline d_j. Busy time scheduling aims to use multiple processors to schedule jobs concurrently to minimize the time a machine has to process jobs. We consider the case proposed by Koehler and Khuller [20], where a single machine has unlimited processors. Moreover, we consider the case where the online algorithm can access prediction, which might be imperfect, on when the machine should be active. We present an algorithm, Multiplier, that dynamically adjusts its strategy for reserving time windows for potential future jobs according to the prediction it receives and how much it trusts the prediction. We show that Multiplier is (1+41+λ)-consistent and (1+41-λ)-robust with a trust parameter λ∈[0,1).

Original language	English
Title of host publication	SOFSEM 2025
Subtitle of host publication	Theory and Practice of Computer Science - 50th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2025, Proceedings
Editors	Rastislav Královič, Věra Kůrková
Publisher	Springer
Pages	324-336
Number of pages	13
ISBN (Electronic)	978-3-031-82697-9
ISBN (Print)	978-3-031-82696-2
DOIs	https://doi.org/10.1007/978-3-031-82697-9_24
Publication status	Published - 16 Feb 2025
Event	50th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2025 - Bratislava, Slovakia Duration: 20 Jan 2025 → 23 Jan 2025

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	15539 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	50th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2025
Country/Territory	Slovakia
City	Bratislava
Period	20/01/25 → 23/01/25

Bibliographical note

Publisher Copyright:
© The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.

Keywords

adaptive strategy
consistency
online busy time scheduling
robustness
untrusted prediction

Access to Document

10.1007/978-3-031-82697-9_24

Cite this

van de Bovenkamp, R., & Liu, A. H. H. (2025). Online Busy Time Scheduling with Untrusted Prediction. In R. Královič, & V. Kůrková (Eds.), SOFSEM 2025: Theory and Practice of Computer Science - 50th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2025, Proceedings (pp. 324-336). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 15539 LNCS). Springer. https://doi.org/10.1007/978-3-031-82697-9_24

van de Bovenkamp, Rick ; Liu, Alison Hsiang Hsuan. / Online Busy Time Scheduling with Untrusted Prediction. SOFSEM 2025: Theory and Practice of Computer Science - 50th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2025, Proceedings. editor / Rastislav Královič ; Věra Kůrková. Springer, 2025. pp. 324-336 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{f5a3bd2ab7184527ab04eff0e4dddafb,

title = "Online Busy Time Scheduling with Untrusted Prediction",

abstract = "In this work, we study the online busy time scheduling problem with infinite processors, where each job j has a release time rj, a processing time pj, and a deadline dj. Busy time scheduling aims to use multiple processors to schedule jobs concurrently to minimize the time a machine has to process jobs. We consider the case proposed by Koehler and Khuller [20], where a single machine has unlimited processors. Moreover, we consider the case where the online algorithm can access prediction, which might be imperfect, on when the machine should be active. We present an algorithm, Multiplier, that dynamically adjusts its strategy for reserving time windows for potential future jobs according to the prediction it receives and how much it trusts the prediction. We show that Multiplier is (1+41+λ)-consistent and (1+41-λ)-robust with a trust parameter λ∈[0,1).",

keywords = "adaptive strategy, consistency, online busy time scheduling, robustness, untrusted prediction",

author = "\{van de Bovenkamp\}, Rick and Liu, \{Alison Hsiang Hsuan\}",

note = "Publisher Copyright: {\textcopyright} The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.; 50th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2025 ; Conference date: 20-01-2025 Through 23-01-2025",

year = "2025",

month = feb,

day = "16",

doi = "10.1007/978-3-031-82697-9\_24",

language = "English",

isbn = "978-3-031-82696-2",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "324--336",

editor = "Rastislav Kr{\'a}lovi{\v c} and V{\v e}ra Kůrkov{\'a}",

booktitle = "SOFSEM 2025",

}

van de Bovenkamp, R & Liu, AHH 2025, Online Busy Time Scheduling with Untrusted Prediction. in R Královič & V Kůrková (eds), SOFSEM 2025: Theory and Practice of Computer Science - 50th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2025, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 15539 LNCS, Springer, pp. 324-336, 50th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2025, Bratislava, Slovakia, 20/01/25. https://doi.org/10.1007/978-3-031-82697-9_24

Online Busy Time Scheduling with Untrusted Prediction. / van de Bovenkamp, Rick; Liu, Alison Hsiang Hsuan.
SOFSEM 2025: Theory and Practice of Computer Science - 50th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2025, Proceedings. ed. / Rastislav Královič; Věra Kůrková. Springer, 2025. p. 324-336 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 15539 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Online Busy Time Scheduling with Untrusted Prediction

AU - van de Bovenkamp, Rick

AU - Liu, Alison Hsiang Hsuan

N1 - Publisher Copyright: © The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.

PY - 2025/2/16

Y1 - 2025/2/16

N2 - In this work, we study the online busy time scheduling problem with infinite processors, where each job j has a release time rj, a processing time pj, and a deadline dj. Busy time scheduling aims to use multiple processors to schedule jobs concurrently to minimize the time a machine has to process jobs. We consider the case proposed by Koehler and Khuller [20], where a single machine has unlimited processors. Moreover, we consider the case where the online algorithm can access prediction, which might be imperfect, on when the machine should be active. We present an algorithm, Multiplier, that dynamically adjusts its strategy for reserving time windows for potential future jobs according to the prediction it receives and how much it trusts the prediction. We show that Multiplier is (1+41+λ)-consistent and (1+41-λ)-robust with a trust parameter λ∈[0,1).

AB - In this work, we study the online busy time scheduling problem with infinite processors, where each job j has a release time rj, a processing time pj, and a deadline dj. Busy time scheduling aims to use multiple processors to schedule jobs concurrently to minimize the time a machine has to process jobs. We consider the case proposed by Koehler and Khuller [20], where a single machine has unlimited processors. Moreover, we consider the case where the online algorithm can access prediction, which might be imperfect, on when the machine should be active. We present an algorithm, Multiplier, that dynamically adjusts its strategy for reserving time windows for potential future jobs according to the prediction it receives and how much it trusts the prediction. We show that Multiplier is (1+41+λ)-consistent and (1+41-λ)-robust with a trust parameter λ∈[0,1).

KW - adaptive strategy

KW - consistency

KW - online busy time scheduling

KW - robustness

KW - untrusted prediction

UR - http://www.scopus.com/inward/record.url?scp=86000474570&partnerID=8YFLogxK

U2 - 10.1007/978-3-031-82697-9_24

DO - 10.1007/978-3-031-82697-9_24

M3 - Conference contribution

AN - SCOPUS:86000474570

SN - 978-3-031-82696-2

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 324

EP - 336

BT - SOFSEM 2025

A2 - Královič, Rastislav

A2 - Kůrková, Věra

PB - Springer

T2 - 50th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2025

Y2 - 20 January 2025 through 23 January 2025

ER -

van de Bovenkamp R, Liu AHH. Online Busy Time Scheduling with Untrusted Prediction. In Královič R, Kůrková V, editors, SOFSEM 2025: Theory and Practice of Computer Science - 50th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2025, Proceedings. Springer. 2025. p. 324-336. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-82697-9_24