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 for every job j and machine i. Can we assign the jobs so that, if job j ends up on machine i, at mostjobs 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, and (ii) minimize the amount by which capacities have to be scaled so that all jobs can be assigned. For the first problem and its generalizations we provide an -approximation algorithm. For the second problem we show that it is -inapproximable and provide linear integrality gap lower bounds for two key relaxations. © 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG