Τίτλος:
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.
Συγγραφείς:
Karakostas, G.
Kolliopoulos, S.G.
Περιοδικό:
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Εκδότης:
Springer Science and Business Media Deutschland GmbH
Λέξεις-κλειδιά:
Internet of things, Deadline; Generalisation; Integrality gaps; On-machines; Optimisations; Scheduling; Time-sharing; Time-sharing systems; Tolerance capacity; Weights of jobs, Approximation algorithms
DOI:
10.1007/978-3-031-22050-0_7
