Exact Approach to the Scheduling of F-shaped Tasks with Two and Three Criticality Levels

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F17%3A00311480" target="_blank" >RIV/68407700:21230/17:00311480 - isvavai.cz</a>

Nalezeny alternativní kódy

RIV/68407700:21730/17:00311480

Výsledek na webu

<a href="http://dx.doi.org/10.5220/0006198101600170" target="_blank" >http://dx.doi.org/10.5220/0006198101600170</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.5220/0006198101600170" target="_blank" >10.5220/0006198101600170</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Exact Approach to the Scheduling of F-shaped Tasks with Two and Three Criticality Levels

Popis výsledku v původním jazyce

The communication is an essential part of a fault tolerant and dependable system. Safety-critical systems are often implemented as time-triggered environments, where the network nodes are synchronized by clocks and follow a static schedule to ensure determinism and easy certification. The reliability of a communication bus can be further improved when the message retransmission is permitted to deal with lost messages. However, constructing static schedules for non-preemptive messages that account for retransmissions while preserving the efficient use of resources poses a challenging problem. In this paper, we show that the problem can be modeled using so-called F-shaped tasks. We propose efficient exact algorithms solving the non-preemptive message scheduling problem with retransmissions. Furthermore, we show a new complexity result, and we present computational experiments for instances with up to 200 messages.

Název v anglickém jazyce

Exact Approach to the Scheduling of F-shaped Tasks with Two and Three Criticality Levels

Popis výsledku anglicky

The communication is an essential part of a fault tolerant and dependable system. Safety-critical systems are often implemented as time-triggered environments, where the network nodes are synchronized by clocks and follow a static schedule to ensure determinism and easy certification. The reliability of a communication bus can be further improved when the message retransmission is permitted to deal with lost messages. However, constructing static schedules for non-preemptive messages that account for retransmissions while preserving the efficient use of resources poses a challenging problem. In this paper, we show that the problem can be modeled using so-called F-shaped tasks. We propose efficient exact algorithms solving the non-preemptive message scheduling problem with retransmissions. Furthermore, we show a new complexity result, and we present computational experiments for instances with up to 200 messages.

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/GA16-23509S" target="_blank" >GA16-23509S: Flexibilní rozvrhovací a optimalizační algoritmy pro distribuované systémy reálného času</a><br>

Návaznosti

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

Rok uplatnění

2017

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 6th International Conference on Operations Research and Enterprise Systems

ISBN

978-989-758-218-9

ISSN

—

e-ISSN

—

Počet stran výsledku

11

Strana od-do

160-170

Název nakladatele

SciTePress

Místo vydání

Madeira

Místo konání akce

Porto

Datum konání akce

23. 2. 2017

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

WRD - Celosvětová akce

Kód UT WoS článku

000413254200015