An optimal online algorithm for single parallel-batch machine scheduling with incompatible job families to minimize makespan

We consider the online scheduling of incompatible job families on an unbounded parallel-batch machine to minimize the makespan, where jobs arrive over time and the number of job families, ff, is known in advance. We provide an optimal online algorithm for the problem with a competitive ratio of 1+4f2+1−12f.