Online scheduling of incompatible unit-length job families with lookahead

We consider the online scheduling of incompatible unit-length job families on an unbounded parallel-batch machine with lookahead. In this paper online means that jobs arrive over time. The objective is to mininize the makespan. In the lookahead model, at a time instant t, an online algorithm can foresee the information of all jobs arriving in the time segment (t,t+β]. Incompatible job families mean that jobs which belong to different families cannot be assigned to the same batch. For this problem, we provide a best possible online algorithm of competitive ratio 1+αf for 0≤β<1, where αf is the positive root of the equation f⋅αf2+(1+β)αf+β−f=0 and f is the number of job families which is known in advance.