Anzeige
Erschienen in:
2012 | OriginalPaper | Buchkapitel
Online Minimum Makespan Scheduling with a Buffer
verfasst von : Yan Lan, Xin Chen, Ning Ding, György Dósa, Xin Han
Erschienen in: Frontiers in Algorithmics and Algorithmic Aspects in Information and Management
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 this paper we study an online minimum makespan scheduling problem with a reordering buffer. We obtain the following results, which improve on work from FOCS 2008: i) for
m
identical machines, we give a 1.5-competitive online algorithm with a buffer of size 1.5
m
, which is better than the previous best result : 1.5-competitive algorithm with a buffer of size 1.6197
m
; ii) for three identical machines, to give an optimal online algorithm we reduce the size of the buffer from nine to six; iii) for
m
uniform machines, using a buffer of size
m
, we improve the competitive ratio from 2 +
ε
to 2 − 1/
m
+
ε
, where
ε
> 0 is sufficiently small.