Narrow Results

In this paper, we propose a new online scheduling model with linear lookahead intervals, which has the character that at any time $t$, one can foresee the jobs that will coming in the time interval $(t,\lambda t+\beta ]$ in which $\lambda >1,\beta >0$. In this new lookahead model, the length of the lookahead intervals are variable as the time going on and the number of jobs increasing, and has the tend of steady growth. In this paper, we consider online scheduling of unit length jobs on $m$ identical parallel-batch machines under this new lookahead model to minimize makespan. The batch capacity is unbounded, that is $b=\infty$. We present an optimal online algorithm for $\lambda >1,\beta \ge \frac{\lambda -1}{{\lambda }^m-1}$, and provide a best possible online algorithm of competitive ratio $1+{\alpha }_m$ for $\lambda >1,0<\beta <\frac{\lambda -1}{{\lambda }^m-1}$, where ${\alpha }_m$ is the positive root of ${(1+{\alpha }_m)}^{m+1}{\lambda }^m+(1+\beta -\lambda ){\sum }_{i=1}^m{(1+{\alpha }_m)}^i{\lambda }^{i-1}=2+{\alpha }_m$.