Online algorithms for scheduling unit length jobs on parallel-batch machines with lookahead

摘要

We consider online scheduling of unit length jobs on m parallel-batch machines with lookahead to minimize makespan. A parallel-batch machine can handle up to b jobs simultaneously as a batch with processing time equal to the maximum processing time of the jobs included in the batch. In the lookahead model, at a time instant t, an online algorithm can foresee all the jobs that will arrive in the time segment (t, t +β]. In this paper, we deal with two variants: the unbounded model with b - ∞ and the bounded model with b < ∞. For the unbounded model, we present an optimal online algorithm for β≥ 1 /m, and provide a best possible online algorithm of competitive ratio 1 + α_m for 0≤β< 1/m, where α_m is the positive root of (1 + α)~((m+1)) = α + 2 - β ∑_(i=1)~m(1+α)~i,For the bounded model, we establish a lower bound with a form of piecewise function, and provide an online algorithm with competitive ratios 1 + α~* for α ≤β≤1/6 and 3/2 for β> 1/6, respectively, where α~* is the positive root of α~2 + (β + 1)α + β - 1 = 0. The online algorithm is the best possible when 0≤ β≤1/6.