EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Single Machine Scheduling with Few Deadlines

Klaus Heeger, Danny Hermelin, Dvir Shabtay

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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