Abstract:

 We consider the on-line scheduling of incompatible unit-length job families  on unbounded parallel-batch machines with lookahead when the number of
job families is equal to the number of machines. In this paper online means that jobs arrive over time. The objective is to minimize the makespan. In the lookahead model, at a time instant  t , an on-line algorithm can foresee the information of all jobs arriving in the time segment  (t,t+\beta). By incompatible job
families, we  mean that jobs from different families cannot be assigned together in the same batch. When \beta \geq 1, we provide an optimal online algorithm; When 0\leq \beta < 1, we give a best possible online algorithm of competitive ratio 1+\alpha, where \alpha is the positive root of the equation \alpha^{2}+(1+\beta) \alpha+\beta-1=0.  We also provide a new lower bound on the competitive ratio for dense-algorithms, and present a best possible dense-algorithm matching this lower bound.

Key words:  on-line scheduling, parallel batching, incompatible job families, makespan, competitive ratio