Anzeige
Erschienen in:
2017 | OriginalPaper | Buchkapitel
Structured Instances of Restricted Assignment with Two Processing Times
verfasst von : Klaus Jansen, Lars Rohwedder
Erschienen in: Algorithms and Discrete Applied Mathematics
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
Abstract
For the Restricted Assignment Problem the best known polynomial algorithm is a 2-approximation by Lenstra, Shmoys and Tardos [7]. Even for the case with only two different processing times the ratio above has merely been improved by a tiny margin [2].
In some cases where the restrictions on one or both job sizes are somewhat structured, simple combinatorial algorithms are known that provide better approximation ratios than the algorithm above.
In this paper we study two classes of structured restrictions, that we refer to as the Inclusion Chain Class and the Two Partition Class. We present a 1.5-approximation for each of them.