Periodic chains scheduling on dedicated resources - A crucial problem in time-sensitive networks

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F25%3A00383081" target="_blank" >RIV/68407700:21230/25:00383081 - isvavai.cz</a>

Nalezeny alternativní kódy

RIV/68407700:21730/25:00383081

Výsledek na webu

<a href="https://doi.org/10.1016/j.cor.2025.107072" target="_blank" >https://doi.org/10.1016/j.cor.2025.107072</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.cor.2025.107072" target="_blank" >10.1016/j.cor.2025.107072</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Periodic chains scheduling on dedicated resources - A crucial problem in time-sensitive networks

Popis výsledku v původním jazyce

Periodic messages transfer data from sensors to actuators in cars, planes, and complex production machines. When considering a given routing, the unicast message starts at its source and goes over several dedicated resources to reach its destination. Such unicast message can be represented as a chain of point-to-point communications. Thus, the scheduling of the periodic chains is a principal problem in time-triggered Ethernet, like IEEE 802.1Qbv Time-Sensitive Networks. This paper studies a strongly NP-hard periodic scheduling problem with harmonic periods, task chains, and dedicated resources. We analyze the problem on several levels and provide proofs of complexity and approximation algorithms for several special cases. We describe a solution methodology to find a feasible schedule that minimizes the chains’ degeneracy related to start-to-end latency normalized in the number of periods. We use the local search with the first fit scheduling heuristic, which we warm-start with a constraint programming model. This notably improves the schedulability of instances with up to 100% utilization and thousands (and more) of tasks, with high-quality solutions found in minutes. An efficient constraint programming matheuristic significantly reduces the degeneracy of the found schedules even further. The method is evaluated on sets of industrial-, avionic-, and automotive-inspired instances.

Název v anglickém jazyce

Periodic chains scheduling on dedicated resources - A crucial problem in time-sensitive networks

Popis výsledku anglicky

Periodic messages transfer data from sensors to actuators in cars, planes, and complex production machines. When considering a given routing, the unicast message starts at its source and goes over several dedicated resources to reach its destination. Such unicast message can be represented as a chain of point-to-point communications. Thus, the scheduling of the periodic chains is a principal problem in time-triggered Ethernet, like IEEE 802.1Qbv Time-Sensitive Networks. This paper studies a strongly NP-hard periodic scheduling problem with harmonic periods, task chains, and dedicated resources. We analyze the problem on several levels and provide proofs of complexity and approximation algorithms for several special cases. We describe a solution methodology to find a feasible schedule that minimizes the chains’ degeneracy related to start-to-end latency normalized in the number of periods. We use the local search with the first fit scheduling heuristic, which we warm-start with a constraint programming model. This notably improves the schedulability of instances with up to 100% utilization and thousands (and more) of tasks, with high-quality solutions found in minutes. An efficient constraint programming matheuristic significantly reduces the degeneracy of the found schedules even further. The method is evaluated on sets of industrial-, avionic-, and automotive-inspired instances.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

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

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2025

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 periodika

Computer & Operations Research

ISSN

0305-0548

e-ISSN

1873-765X

Svazek periodika

180

Číslo periodika v rámci svazku

August

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

19

Strana od-do

—

Kód UT WoS článku

001461902000001

EID výsledku v databázi Scopus

2-s2.0-105001493637