Single Machine Scheduling with Few Deadlines
Algorithmica · 2027-02 · 89 (1)
DOI: 10.1007/s00453-026-01414-3 ↗Kurz gefasst
Fachartikel in der Zeitschrift Algorithmica, online erschienen am 06.11.2026. Verfasst von Klaus Heeger und 2 weiteren Autor:innen. Die Arbeit nennt 33 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Israel Science Foundation, Bundesministerium für Umwelt, Naturschutz, nukleare Sicherheit und Verbraucherschutz.
Abstract (Originalsprache)
We study single-machine scheduling problems with few deadlines. We focus on three classical objectives, namely minimizing the weighted number of tardy jobs, the total weighted completion time, and the total weighted late work. For each of the three problems, we give a pseudo-polynomial-time algorithm for a constant number of different deadlines. These algorithms are complemented with ETH-based, almost tight lower bounds. Furthermore, we study the case in which the number of jobs with nontrivial deadline (i.e. jobs with deadline smaller than the total processing time of all jobs) is taken as a parameter. For this case, the complexities of our three problems differ: Minimizing the weighted number of tardy jobs and minimizing the total weighted late work becomes fixed-parameter tractable, while minimizing the total weighted completion time is W[1]-hard.
Förderung
- Israel Science Foundation
- Bundesministerium für Umwelt, Naturschutz, nukleare Sicherheit und Verbraucherschutz
Zitieren
APA
Heeger, K., Hermelin, D., & Shabtay, D. (2027). Single Machine Scheduling with Few Deadlines. Algorithmica, 89(1). https://doi.org/10.1007/s00453-026-01414-3
Vancouver
Heeger K, Hermelin D, Shabtay D. Single Machine Scheduling with Few Deadlines. Algorithmica. 2027;89(1). doi:10.1007/s00453-026-01414-3
BibTeX
@article{Heeger2027,
author = {Heeger, Klaus and Hermelin, Danny and Shabtay, Dvir},
title = {Single Machine Scheduling with Few Deadlines},
journal = {Algorithmica},
year = {2027},
volume = {89},
number = {1},
doi = {10.1007/s00453-026-01414-3}
}
EUVIMED