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