具有线性恶化效应的在线分批排序问题

本文研究一类具有线性恶化效应的单机在线分批排序问题,工件$J_j$的加工时间为$p_j=b_j+\alpha t$, 其中$b_j$为基本加工时间, $\alpha>0$为恶化率, $t$是开工时间. 工件的到达时间是未知的, 工件的基本加工时间只有在工件到达之后才能知道.多个工件可以作为一批被机器同时加工, 批的加工时间为该批中工件最大加工时间.本文对于目标为极小化makespan的批容量无限的单机问题给出一个在线算法$\beta H^\infty$,并证明其竞争比和问题的下界相同, 进而算法是最优的.

Online Batch Scheduling with Linear Deterioration Effect

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.