本文研究两台单位流水作业上, 具有前瞻区间的两个不相容工件族无界批处理的在线排序问题。单位流水车间问题是指任何工件在每台机器上的加工长度均为$, 工件按时到达, 目标是最小化最大完工时间。具有前瞻区间是指在时刻$t$, 在线算法能预见$(t, t+\beta]$区间内到达工件的信息。不可相容工件族是指属于不同工件族的工件不能安排在同一批加工。本文提供了一个竞争比为$1+\alpha$的在线算法$A_1(\beta)$, 其中$\alpha=\displaystyle\frac{\sqrt{\beta^{2}-8 \beta+28}-(\beta+2)}{6}$$(\displaystyle\frac{\sqrt{21}-3}{6} <\alpha\leqslant \displaystyle\frac{\sqrt{7}-1}{3})$是方程$3\alpha^{2}+(\beta+2) \alpha+\beta-2=0$的一个正根, 这里$0 \leqslant \beta<1$。

This paper studies on-line scheduling problem on two unit flowshop machines, in which there exist unbounded batch processing of two incompatible job families and lookahead intervals. The unit flowshop is that the processing time of any job is 1 at two machines. The jobs arrive on time. The goal is to minimize the maximum completion time of the jobs. At time $t$, the lookahead interval means on-line algorithm can predict the information of arriving workpieces in the interval $(t, t+\beta]$. Incompatible workpieces family means that workpieces belonging to different workpieces family cannot be arranged in the same batch. For this problem, we provide a best possible online algorithm $A_1(\beta)$ of competitive ratio $1+\alpha$ for $0 \leqslant \beta<1$, where $\alpha$ is the positive root of the equation $3 \alpha^{2}+(\beta+2) \alpha+\beta-2=0$.