Abstract:

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.

Key words: online scheduling, linear lookahead, parallel-batch, minimize makespan