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 LKL 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 L) 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<∞).