Abstract:

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$.

Key words: on-line algorithm, lookahead interval, incompatible family, competitive ratio, minimize the maximum completion time