Periodic chains scheduling on dedicated resources - A crucial problem in time-sensitive networks
The result's identifiers
Result code in 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>
Alternative codes found
RIV/68407700:21730/25:00383081
Result on the web
<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>
Alternative languages
Result language
angličtina
Original language name
Periodic chains scheduling on dedicated resources - A crucial problem in time-sensitive networks
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
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
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2025
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
Name of the periodical
Computer & Operations Research
ISSN
0305-0548
e-ISSN
1873-765X
Volume of the periodical
180
Issue of the periodical within the volume
August
Country of publishing house
US - UNITED STATES
Number of pages
19
Pages from-to
—
UT code for WoS article
001461902000001
EID of the result in the Scopus database
2-s2.0-105001493637