Packing-Inspired Algorithms for Periodic Scheduling Problems with Harmonic Periods

Kód výsledku v 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>

Nalezeny alternativní kódy

RIV/68407700:21730/24:00373056

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Packing-Inspired Algorithms for Periodic Scheduling Problems with Harmonic Periods

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Packing-Inspired Algorithms for Periodic Scheduling Problems with Harmonic Periods

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/EH22_008%2F0004590" target="_blank" >EH22_008/0004590: Robotika a pokročilá průmyslová výroba</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2024

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Proceedings of the 13th International Conference on Operations Research and Enterprise Systems

ISBN

978-989-758-681-1

ISSN

2184-4372

e-ISSN

—

Počet stran výsledku

12

Strana od-do

101-112

Název nakladatele

SciTePress

Místo vydání

Setùbal

Místo konání akce

Řím

Datum konání akce

24. 2. 2024

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—