OPTIMAL SEMI-ONLINE ALGORITHM for SCHEDULING on A BATCH PROCESSING MACHINE

We consider two semi-online scheduling problems on a single batch (processing) machine with jobs' nondecreasing processing times and jobs' nonincreasing processing times, respectively. Our objective is to minimize the makespan. A batch processing machine can handle up to B jobs simultaneously. We study an unbounded model where B = ∞. The jobs that are processed together construct a batch, and all jobs in a batch start and complete at the same time. The processing time of a batch is given by the longest processing time of any job in the batch. Jobs arrive over time. Let p_j denote the processing time of job J_j. Given job J_j and its following job J_j + 1, we assume that p_j + 1 ≥ α p_j, where α ≥ 1 is a constant number, for the first problem with jobs' nondecreasing processing times. For the second problem, we assume that p_j + 1 ≤ α p_j, where 0 < α < 1 is a constant number. We propose an optimal algorithm for both problems with a competitive ratio α2+4}-α2+1 for the first problem and 4α+1+12 for the second problem.