Online Scheduling Of Unit Length Jobs On A Batching Machine To Maximize The Number Of Early Jobs

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.Parallel batching means that several jobs can form a batch and be processed together with the processing time of a batch being equal to the maximum processing time of the jobs in the batch.Denote by b the capacity of the batches 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).The main results of this paper are as follows.(1) When 0≤L＜1,we show that a simple greedy online algorithm(independent to 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.(2) When 1≤L＜2,we establish the upper bounds 0.39(for b =∞) and 2/3(for b＜∞) of competitive ratios.Then we provide an online algorithm of competitive ratios 1/4(for b =∞) and 1/5(for b＜∞).