Anzeige
Erschienen in:
2009 | OriginalPaper | Buchkapitel
Approximating Scheduling Machines with Capacity Constraints
verfasst von : Chi Zhang, Gang Wang, Xiaoguang Liu, Jing Liu
Erschienen in: Frontiers in Algorithmics
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
In the Scheduling Machines with Capacity Constraints problem, we are given
k
identical machines, each of which can process at most
m
i
jobs.
$M \leq \sum_{i = 1}^{k}{m_i}$
jobs are also given, job
j
has a non-negative processing time length
t
j
≥ 0. The task is to find a schedule such that the makespan is minimized and the capacity constraints are met. In this paper, we present a 3-approximation algorithm using an extension of
Iterative Rounding Method
introduced by Jain [4]. To the best of the authors’ knowledge, this is the first attempt to apply
Iterative Rounding Method
to scheduling problem with capacity constraints.