An EPTAS for minimizing the total weighted completion time of jobs with release dates on uniformly related machines
Information and Computation · 2026-06 · 311 · 105454
DOI: 10.1016/j.ic.2026.105454 ↗Kurz gefasst
Fachartikel in der Zeitschrift Information and Computation, 2026-06. Verfasst von Leah Epstein und 1 weiteren Autor:innen. Die Arbeit nennt 31 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY-NC-ND 4.0). Gefördert von: Israel Science Foundation.
Abstract (Originalsprache)
Scheduling of independent jobs with release dates so as to minimize the total weighted completion time is a well-known scheduling problem. Here, we study it for the classic machine environment of uniformly related machines. An efficient polynomial time approximation scheme (an EPTAS) is a family of (1 + ε )-approximation algorithms where the running time is bounded by a polynomial in the input size times a function of ε > 0. For problems that are NP-hard in the strong sense, as it is the case for the problem studied here, an EPTAS is the best possible approximation scheme. We design an EPTAS for the problem by employing known techniques and introducing a large collection of new methods
Förderung
- Israel Science Foundation
Zitieren
APA
Epstein, L., & Levin, A. (2026). An EPTAS for minimizing the total weighted completion time of jobs with release dates on uniformly related machines. Information and Computation, 311, 105454. https://doi.org/10.1016/j.ic.2026.105454
Vancouver
Epstein L, Levin A. An EPTAS for minimizing the total weighted completion time of jobs with release dates on uniformly related machines. Information and Computation. 2026;311:105454. doi:10.1016/j.ic.2026.105454
BibTeX
@article{Epstein2026,
author = {Epstein, Leah and Levin, Asaf},
title = {An EPTAS for minimizing the total weighted completion time of jobs with release dates on uniformly related machines},
journal = {Information and Computation},
year = {2026},
volume = {311},
pages = {105454},
doi = {10.1016/j.ic.2026.105454}
}
EUVIMED