关键词: 分批排序, 恶化效应, 竞争比, 在线算法

Abstract: An online batch scheduling with linear deterioration effect on single machine is considered. Jobs arrive over time. A batch processing machine can handle up to $B$ jobs simultaneously. The actual processing time $p_j$ of Job $J_j$ is assumed to be a linear function of its starting time $t$, i.e., $p_j=b_j+\alpha t$, where $\alpha >0$ is the deterioration ratio, $b_j$ is the basic processing time, which is unknown until it arrives. The processing time of a batch is given by the longest processing time of any job in the batch. For single machine with unbounded capacity to minimize makespan problem, we give an optimal online algorithm, which competitive ratio matches the lower bound of the problem.

Key words:  batch scheduling, deterioration effect, competitive, online algorithm