单机上带有可变前瞻区间的分批在线排序问题

本文研究单台无界平行批处理机上带有可变前瞻区间的在线排序问题。工件按时在线到达，目标是最小化时间表长。在时刻$t$，在线算法能够预见到$（t，t+\Delta（t）]$内到达工件的信息，这里前瞻区间的长度$\Delta（t）=\beta p_{\max}（t）$并非定长，其中$p_{\max}（t）$表示在$t$时刻及之前到达工件的最大加工时长，$\beta\in（0，1）$是常数。本文对于工件加工时长的一般情形，给出了当 0<β≤1/6 时最好可能的在线算法；对于工件加工时长被限制在一个区间的情形，给出了当 0<β<1 时最好可能的在线算法。

Online scheduling on single batch machine with variable lookahead interval

This paper investigates the online scheduling on an unbounded parallel-batch machine with variable lookahead interval to minimize makespan. Online means that jobs arrive over time. At any time $t$, an online algorithm can foresee the information of the jobs arriving in $(t, t+\Delta(t)]$, where $\Delta(t)=\beta p_{\max}(t)$ is the length of the lookahead interval which is not invariable, $p_{\max}(t)$ is the maximum processing time of the jobs arriving at or before $t$ and $\beta\in(0, 1)$ is a constant. On the general case of processing time, we give an online algorithm which is the best possible for 0<β≤1/6. When the processing times of all jobs are restricted in an interval, we give the best possible online algorithm for 0<β<1.