EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

A coupled task scheduling approximation algorithm for minimizing the sum of completion times

József Békési, György Dósa, Gábor Galambos

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →