Anzeige
Erschienen in:
2015 | OriginalPaper | Buchkapitel
Approximate Deadline-Scheduling with Precedence Constraints
verfasst von : Hossein Efsandiari, MohammadTaghi Hajiaghyi, Jochen Könemann, Hamid Mahini, David Malec, Laura Sanità
Erschienen in: Algorithms - ESA 2015
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We consider the classic problem of scheduling a set of
n
jobs non-preemptively on a single machine. Each job
j
has non-negative processing time, weight, and deadline, and a feasible schedule needs to be consistent with
chain-like
precedence constraints. The goal is to compute a feasible schedule that minimizes the sum of penalties of late jobs. Lenstra and Rinnoy Kan [Annals of Disc. Math., 1977] in their seminal work introduced this problem and showed that it is strongly NP-hard, even when all processing times and weights are 1. We study the approximability of the problem and our main result is an
O
(log
k
)-approximation algorithm for instances with
k
distinct job deadlines.