A coupled task scheduling approximation algorithm for minimizing the sum of completion times
Annals of Operations Research · 2026-07 · 362 (1-3) · 1-26
DOI: 10.1007/s10479-026-07261-3 ↗Kurz gefasst
Fachartikel in der Zeitschrift Annals of Operations Research, online erschienen am 21.05.2026. Verfasst von József Békési und 2 weiteren Autor:innen. Die Arbeit nennt 23 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: University of Szeged.
Abstract (Originalsprache)
In the considered coupled task problem (CTP) we have to schedule n jobs on a single machine, each consisting of two tasks with exact time delay between them, while the objective is to minimize the total completion time of the jobs. We analyze a greedy type algorithm – called SDF (Shortest Delay First) – from worst case point of view, and we give bounds for the asymptotic behavior of SDF for the special case where each task has equal length processing time p . For this case, the best-known upper bound on the asymptotic performance ratio of algorithm SDF is $$\frac{5}{3}\approx 1.666\ldots .$$ 5 3 ≈ 1.666 … . We improve this bound to a general upper bound $$\frac{21p-\sqrt{3(43p^2-28p+4)}-6}{6p}$$ 21 p - 3 ( 43 p 2 - 28 p + 4 ) - 6 6 p that holds for all $$p\ge 2.$$ p ≥ 2 . Using constructions to compute lower bounds, we give narrow intervals for the asymptotic behavior of algorithm SDF as a function of the parameter p .
Förderung
- University of Szeged
Zitieren
APA
Békési, J., Dósa, G., & Galambos, G. (2026). A coupled task scheduling approximation algorithm for minimizing the sum of completion times. Annals of Operations Research, 362(1-3), 1-26. https://doi.org/10.1007/s10479-026-07261-3
Vancouver
Békési J, Dósa G, Galambos G. A coupled task scheduling approximation algorithm for minimizing the sum of completion times. Annals of Operations Research. 2026;362(1-3):1-26. doi:10.1007/s10479-026-07261-3
BibTeX
@article{Bksi2026,
author = {Békési, József and Dósa, György and Galambos, Gábor},
title = {A coupled task scheduling approximation algorithm for minimizing the sum of completion times},
journal = {Annals of Operations Research},
year = {2026},
volume = {362},
number = {1-3},
pages = {1--26},
doi = {10.1007/s10479-026-07261-3}
}
EUVIMED