Time-sharing scheduling with tolerance capacities

Motivated by time-sharing systems with deadlines, we introduce the study of the following problem. We are given m machines and n jobs, as well as a set of tolerance capacities u i j ≥ 0 for every job j and machine i. Can we assign the jobs so that, if job j ends up on machine i, the total size of jobs that are processed on i is at most u i j ? We define two natural optimization versions: (i) Maximize the total weight of jobs that can be assigned without violating the tolerance capacities. (ii) Minimize the amount ρ ≥ 1 by which capacities have to be scaled so that all jobs can be assigned. For (i), we provide constant-factor approximations even in the presence of additional side-constraints. For (ii), we provide a strong inapproximability result and integrality gap lower bounds for two key relaxations.