Online Batch Scheduling of Incompatible Job Families with Variable Lookahead Interval

We consider online parallel-batch scheduling of f incompatible unit-length job families with variable lookahead interval to minimize the maximum completion time, where f is the number of job families which is known in advance. Incompatible job family means that a batch only contains the jobs from the same job family. At any time t, an online algorithm can foresee the information of the jobs arriving in the time interval (t,t + Δ(t)], where Δ(t) = (λ − 1)t + β is variable. When the batch capacity b = ∞ and f ≥ 1, we provide a best possible online algorithm with competitive ratio 1 + αf for 0 ≤ β < 1 and 1 ≤ λ ≤ 1 + β, where αf is a positive root of λfαf2 + (λf + β + 1 − f)α f + β − f = 0. When the batch capacity (f <) b < ∞ and f ≥ 2, we give an online algorithm with competitive ratio 1 +max{ f fαf+f, f λfαf+β+1} for 0 ≤ β < 1 and λ ≥ 1, and prove that it is the best possible for λ = 1 and 0 ≤ β ≤ f+1−f2 +1 2.