提前预知信息的在线分批排序问题

研究工件可提前预知信息的在线分批排序问题,工件的预知信息时间依时间到达,目标为极小化最大完工时间.已知从工件的信息可预知到该工件可加工需要时间a,所有工件的最大加工时间为p_(max),多个工件可以作为一批被机器同时加工,批的加工时间为该批工件中最长加工时间.对于批容量无限的单机问题给出一个在线算法γH~∞,并证明其竞争比和问题的下界都为1+γ,其中γ=(-1+(1+(4p_(max))/(p_(max)+a)))/2,进而算法是最优的.

Online batch scheduling with known information in advance

We study a single online batch scheduling problem with known information in advance. The information arrives over time and the objective is to minimize the maximum completion time. The time between the information arrival of a job and its release time is constant $a$. The maximum of the processing times of all jobs $p_{{\rm max}}$ is known in advance too. A batch processing machine can handle up to $b$ jobs simultaneously. The processing time of a batch is given by the longest processing time of all jobs in the batch. When $b=\infty$, we provide an optimal online algorithm $\gamma H^\infty$ with a competitive ratio of $1+\gamma$, where $\gamma=\left(-1+\sqrt{1+\frac{4p_{{\rm max}}}{p_{{\rm max}}+a}}\right)/2$.