Online cardinality constrained scheduling
Leah Epstein, Alexandra Lassota, Asaf Levin, Marten Maack, Lars Rohwedder · Operations Research Letters · 2023
In online load balancing problems, jobs arrive over a list. Upon arrival of a job, the algorithm is required to assign it immediately and irrevocably to a machine. We consider such a makespan minimization problem with an additional cardinality constraint, i.e., at most k jobs may be assigned to each machine, where k is a parameter of the problem. We present both upper and lower bounds on the competitive ratio of online algorithms for this problem with identical machines.