Packing-Inspired Algorithms for Periodic Scheduling Problems with Harmonic Periods
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866915178086400000 |
|---|---|
| author | Grus, Josef Hanen, Claire Hanzálek, Zdeněk |
| author_facet | Grus, Josef Hanen, Claire Hanzálek, Zdeněk |
| contents | We tackle the problem of non-preemptive periodic scheduling with a harmonic set of periods. Problems of this kind arise within domains of periodic manufacturing and maintenance, and also during the design of industrial, automotive, and avionics communication protocols, where efficient scheduling of messages is crucial for the performance of a time-triggered network. We consider the decision variant of the periodic scheduling problem on a single highly-utilized machine. We first prove a bijection between periodic scheduling and a particular (so-called height-divisible) 2D packing of rectangles. We formulate the problem using Constraint Programming and compare it with equivalent state-of-the-art Integer Linear Programming formulation, showing the former's superiority on difficult instances. Furthermore, we develop a packing-inspired first fit heuristic, which we compare with methods described in the literature. We justify our proposed methods on synthetically generated problem instances inspired by the communication of messages on one channel. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_14756 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Packing-Inspired Algorithms for Periodic Scheduling Problems with Harmonic Periods Grus, Josef Hanen, Claire Hanzálek, Zdeněk Data Structures and Algorithms We tackle the problem of non-preemptive periodic scheduling with a harmonic set of periods. Problems of this kind arise within domains of periodic manufacturing and maintenance, and also during the design of industrial, automotive, and avionics communication protocols, where efficient scheduling of messages is crucial for the performance of a time-triggered network. We consider the decision variant of the periodic scheduling problem on a single highly-utilized machine. We first prove a bijection between periodic scheduling and a particular (so-called height-divisible) 2D packing of rectangles. We formulate the problem using Constraint Programming and compare it with equivalent state-of-the-art Integer Linear Programming formulation, showing the former's superiority on difficult instances. Furthermore, we develop a packing-inspired first fit heuristic, which we compare with methods described in the literature. We justify our proposed methods on synthetically generated problem instances inspired by the communication of messages on one channel. |
| title | Packing-Inspired Algorithms for Periodic Scheduling Problems with Harmonic Periods |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2410.14756 |