On the optimality of the LP-based algorithm for online scheduling with GoS eligibility constraints

We consider the online scheduling problem on mm identical machines subject to the Grade of Service (GoS) eligibility constraints. The goal is to minimize the makespan. For fractional jobs that can be arbitrarily split between machines and can be processed in parallel, we provide an optimal online algorithm based on the solution of linear programming.