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.