Resource Time-Sharing for IoT Applications with Deadlines

Motivated by time-sharing systems with deadlines, such as 2-way synchronization of Digital Twins, we introduce the study of a very natural problem which can be abstracted as follows. We are given m machines and n jobs, as well as a set of tolerance capacities$$u_{ij}\ge 0$$ for every job j and machine i. Can we assign the jobs so that, if job j ends up on machine i, at most $$u_{ij}$$ jobs in total are processed on i? We define two natural optimization versions: (i) Maximize the total weight of jobs that can be assigned without violating the tolerance capacities $$u_{ij}$$, and (ii) minimize the amount $$\rho \ge 1,$$ by which capacities have to be scaled so that all jobs can be assigned. For the first problem and its generalizations we provide an $$(1-1/e)$$-approximation algorithm. For the second problem we show that it is $$n^{1/2-\varepsilon }$$-inapproximable and provide linear integrality gap lower bounds for two key relaxations.