Packing-Inspired Algorithms for Periodic Scheduling Problems with Harmonic Periods
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F24%3A00373056" target="_blank" >RIV/68407700:21230/24:00373056 - isvavai.cz</a>
Alternative codes found
RIV/68407700:21730/24:00373056
Result on the web
<a href="https://doi.org/10.5220/0012325800003639" target="_blank" >https://doi.org/10.5220/0012325800003639</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.5220/0012325800003639" target="_blank" >10.5220/0012325800003639</a>
Alternative languages
Result language
angličtina
Original language name
Packing-Inspired Algorithms for Periodic Scheduling Problems with Harmonic Periods
Original language description
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 an efficient static schedule 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 2D packing of rectangles (we name it height-divisible 2D packing). 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 problem instances ins pired by the communication of messages on one channel.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
<a href="/en/project/EH22_008%2F0004590" target="_blank" >EH22_008/0004590: Robotics and advanced industrial production</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach
Others
Publication year
2024
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Proceedings of the 13th International Conference on Operations Research and Enterprise Systems
ISBN
978-989-758-681-1
ISSN
2184-4372
e-ISSN
—
Number of pages
12
Pages from-to
101-112
Publisher name
SciTePress
Place of publication
Setùbal
Event location
Řím
Event date
Feb 24, 2024
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—