Anzeige
Erschienen in:
2010 | OriginalPaper | Buchkapitel
Online Splitting Interval Scheduling on m Identical Machines
verfasst von : Feifeng Zheng, Bo Liu, Yinfeng Xu, E. Zhang
Erschienen in: 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
This paper investigates online scheduling on
m
identical machines with
splitting intervals
, i.e., intervals can be split into pieces arbitrarily and processed simultaneously on different machines. The objective is to maximize the throughput, i.e., the total length of satisfied intervals. Intervals arrive over time and the knowledge of them becomes known upon their arrivals. The decision on splitting and assignment for each interval is made irrecoverably upon its arrival. We first show that any non-split online algorithms cannot have bounded competitive ratios if the ratio of longest to shortest interval length is unbounded. Our main result is giving an online algorithm
ES
(for Equivalent Split) which has competitive ratio of 2 and
$\frac{2m-1}{m-1}$
for
m
= 2 and
m
≥ 3, respectively. We further present a lower bound of
$\frac{m}{m-1}$
, implying that
ES
is optimal as
m
= 2.