Online scheduling of unit length jobs on a batching machine to maximize the number of early jobs with lookahead

摘要

This paper studies online scheduling of unit length jobs on a parallel batching machine with the help of lookahead. The objective is to maximize the number of early jobs. Denote by b the size of each batch with b = ∞ in the unbounded batching and b < ∞ in the bounded batching. In the LK_L lookahead model, at a time instant t, an online algorithm can foresee all jobs that will arrive in the time segment (t, t + L). When 0 ≤ L < 1, we show that a simple greedy online algorithm (independent of the value of I) has a best possible competitive ratio of 1/min{n, b+1}, where n is the number of jobs. This means that lookahead is useless when 0 ≤ L < 1. When 1 ≤ L < 2, we establish the upper bounds 0.39 (for b = ∞) and 2/3 (for b < ∞) of competitive ratios, and provide an online algorithm of competitive ratios 1/4 (for b = ∞)and 1/5 (for b < ∞).