TY - JOUR
T1 - Semi-online scheduling revisited
AU - Albers, Susanne
AU - Hellwig, Matthias
N1 - Funding Information:
Work supported by the German Research Foundation. Corresponding author. Tel.: +49 30 20933192. E-mail addresses: [email protected] (S. Albers), [email protected] (M. Hellwig).
PY - 2012/7/20
Y1 - 2012/7/20
N2 - Makespan minimization on m identical machines is a fundamental scheduling problem. The goal is to assign a sequence of jobs, each specified by a processing time, to parallel machines so as to minimize the maximum completion time of any job. Deterministic online algorithms achieve a competitive ratio of about 1.92. Due to this relatively high competitiveness and the lack of progress in the area of randomized online strategies, recent research has investigated scenarios where the online constraint is relaxed. We study semi-online scheduling where at any time an online scheduler knows the sum of the jobs' processing times. This problem relaxation is well motivated by practical applications. The best known semi-online algorithm achieves a competitive ratio of 1.6 (Cheng, Kellerer, Kotov, 2005 [11]). The best known lower bound is equal to 1.565 (Angelelli, Nagy, Speranza, Tuza, 2004 [3]). In this paper, we present two contributions for semi-online scheduling. We develop an improved lower bound showing that no deterministic semi-online algorithm can attain a competitive ratio smaller than 1.585. This significantly reduces the gap between the previous lower bound and the upper bound of 1.6. Second, we present a new semi-online algorithm that is based on an approach different from that of previous strategies. The algorithm is 1.75-competitive and hence does not achieve the best possible competitiveness. However, our algorithm is extremely simple and, unlike previous strategies, does not resort to job classes. The algorithm is more in the spirit of online algorithms not using any extra information. Hence our upper bound highlights the additional power of a small piece of advice when provided to an online algorithm.
AB - Makespan minimization on m identical machines is a fundamental scheduling problem. The goal is to assign a sequence of jobs, each specified by a processing time, to parallel machines so as to minimize the maximum completion time of any job. Deterministic online algorithms achieve a competitive ratio of about 1.92. Due to this relatively high competitiveness and the lack of progress in the area of randomized online strategies, recent research has investigated scenarios where the online constraint is relaxed. We study semi-online scheduling where at any time an online scheduler knows the sum of the jobs' processing times. This problem relaxation is well motivated by practical applications. The best known semi-online algorithm achieves a competitive ratio of 1.6 (Cheng, Kellerer, Kotov, 2005 [11]). The best known lower bound is equal to 1.565 (Angelelli, Nagy, Speranza, Tuza, 2004 [3]). In this paper, we present two contributions for semi-online scheduling. We develop an improved lower bound showing that no deterministic semi-online algorithm can attain a competitive ratio smaller than 1.585. This significantly reduces the gap between the previous lower bound and the upper bound of 1.6. Second, we present a new semi-online algorithm that is based on an approach different from that of previous strategies. The algorithm is 1.75-competitive and hence does not achieve the best possible competitiveness. However, our algorithm is extremely simple and, unlike previous strategies, does not resort to job classes. The algorithm is more in the spirit of online algorithms not using any extra information. Hence our upper bound highlights the additional power of a small piece of advice when provided to an online algorithm.
KW - Competitive analysis
KW - Makespan minimization
KW - Online computation
UR - http://www.scopus.com/inward/record.url?scp=84861809081&partnerID=8YFLogxK
U2 - 10.1016/j.tcs.2012.03.031
DO - 10.1016/j.tcs.2012.03.031
M3 - Article
AN - SCOPUS:84861809081
SN - 0304-3975
VL - 443
SP - 1
EP - 9
JO - Theoretical Computer Science
JF - Theoretical Computer Science
ER -