Online Scheduling on a Parallel‐Batch Machine With Pulse Interruptions

ABSTRACT We consider an online scheduling problem on a parallel‐batch machine with pulse interruptions, which have negligible time lengths, to minimize the makespan. Jobs arrive over time, and the related information of a job becomes known at its arrival time. A parallel‐batch machine can process at most a given number of jobs simultaneously, with the processing time of a batch being equal to the longest processing time of the jobs in the batch. No batch can be processed during a pulse interruption, and preemption is not allowed. For the problem with periodic pulse interruptions, we show that there is no online algorithm with a competitive ratio of less than 2 and develop an online algorithm with a competitive ratio of at most 3. For the special case with a known pulse interruption, we demonstrate that the competitive ratio of the online algorithm is 2.5 and further prove that the online algorithm is the best possible when the batch capacity is 2 or unbounded. Finally, we perform numerical experiments to illustrate the performance of the online algorithm in practice.