TY - GEN
T1 - Online splitting interval scheduling on m identical machines
AU - Zhen, Feifeng
AU - Liu, Bo
AU - Xu, Yinfeng
AU - Zhang, E.
PY - 2010
Y1 - 2010
N2 - 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 2m-1/m-1 for m = 2 and m ≥ 3, respectively. We further present a lower bound of m/m-1, implying that ES is optimal as m = 2.
AB - 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 2m-1/m-1 for m = 2 and m ≥ 3, respectively. We further present a lower bound of m/m-1, implying that ES is optimal as m = 2.
UR - https://www.scopus.com/pages/publications/79956329441
U2 - 10.1007/978-3-642-14355-7_31
DO - 10.1007/978-3-642-14355-7_31
M3 - 会议稿件
AN - SCOPUS:79956329441
SN - 3642143547
SN - 9783642143540
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 304
EP - 313
BT - Algorithmic Aspects in Information and Management - 6th International Conference, AAIM 2010, Proceedings
T2 - 6th International Conference on Algorithmic Aspects in Information and Management, AAIM 2010
Y2 - 19 July 2010 through 21 July 2010
ER -