具有前瞻性的在线排序是一类非常重要的排序模型, 其特点是在任意时刻可以预知未来将要到达的部分工件信息。预知的信息可以是工件的个数, 也可以是未来某个区间内到达的所有工件的信息, 其中一类前瞻模型是$LK_{\beta}$模型, 该模型可以预知的时间区间是固定长度$\beta$, 其中$\beta\geq0$。本文研究单处理机上具有线性前瞻区间的在线分批排序问题, 其特点是在任何时刻$t$, 可以提前预知时间区间$(t, \lambda t+\beta]$内将要到达的工件信息, 其中$\lambda\geq1, \beta\geq0$。随着时间的增长, 可以预测的时间区间长度是变化的, 呈现稳定增长趋势。当$\lambda=1$时, 即为$LK_\beta$前瞻模型。本文讨论的优化目标为最小化时间表长。当批容量无界且工件加工长度按照不减的顺序到达时, 针对$\lambda, \beta$的不同取值范围, 分别给出了最优算法和最好可能的在线算法。

The online scheduling with lookahead is a very important scheduling model, which has the character that at any time, it can foresee the information of some jobs that will coming in the near feature. The information can be the number of jobs that can foresee, or the jobs that will come in some time intervals. The $LK_\beta$ is one of the models, in which the length of the time interval that can foresee is fixed with value $\beta, \beta\geq0$. This paper considers the online scheduling on a single parallel-batch machine with linear lookahead. The main character of the linear lookahead model is that at any time $t$, one can foresee the jobs that will come in the time interval $(t, \lambda t+\beta]$ with $\lambda\geq1, \beta\geq0$. The length of the interval $(t, \lambda t+\beta]$ is changed as the time $t$ going on, having the tend of steady growth. When $\lambda=1$, it is in fact the $LK_\beta$ lookahead model. In this paper, the objective is to minimize the makespan. When the capacity of the batch is unbounded and the jobs arrive with no-decreasing processing times, for different values of $\lambda, \beta$, it gives optimal algorithm and best possible online algorithm, respectively.