An Analysis of the Non-preemptive Mixed-criticality Match-up Scheduling Problem

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F16%3A00243323" target="_blank" >RIV/68407700:21230/16:00243323 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1007/s10951-016-0468-y" target="_blank" >http://dx.doi.org/10.1007/s10951-016-0468-y</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/s10951-016-0468-y" target="_blank" >10.1007/s10951-016-0468-y</a>

Jazyk výsledku

angličtina

Název v původním jazyce

An Analysis of the Non-preemptive Mixed-criticality Match-up Scheduling Problem

Popis výsledku v původním jazyce

Many applications have a mixed-criticality nature. They contain tasks with a different criticality, meaning that a task with a lower criticality can be skipped if a task with a higher criticality needs more time to be executed. This paper deals with a mixed-criticality scheduling problem where each task has a criticality given by a positive integer number. The exact processing time of the task is not known. Instead, we use different upper bounds of the processing time for different criticality levels of the schedule. A schedule with different criticality levels is generated off-line, but its on-line execution switches among the criticality levels depending on the actual values of the processing times. The advantage is that after the transient prolongation of a higher criticality task, the system is able to match up with the schedule on a lower criticality level. While using this model, we achieve significant schedule efficiency (assuming that the prolongation of the higher criticality task rarely occurs), and at the same time, we are able to grant a sufficient amount of time to higher criticality tasks (in such cases, some of the lower criticality tasks may be skipped). This paper shows a motivation for the non-preemptive mixed-criticality match-up scheduling problem arising from the area of the communication protocols. Using a polynomial reduction from the 3-partition problem, we prove the problem to be NP-hard in the strong sense even when the release dates and deadlines are dropped and only two criticality levels are considered.

Název v anglickém jazyce

An Analysis of the Non-preemptive Mixed-criticality Match-up Scheduling Problem

Popis výsledku anglicky

Many applications have a mixed-criticality nature. They contain tasks with a different criticality, meaning that a task with a lower criticality can be skipped if a task with a higher criticality needs more time to be executed. This paper deals with a mixed-criticality scheduling problem where each task has a criticality given by a positive integer number. The exact processing time of the task is not known. Instead, we use different upper bounds of the processing time for different criticality levels of the schedule. A schedule with different criticality levels is generated off-line, but its on-line execution switches among the criticality levels depending on the actual values of the processing times. The advantage is that after the transient prolongation of a higher criticality task, the system is able to match up with the schedule on a lower criticality level. While using this model, we achieve significant schedule efficiency (assuming that the prolongation of the higher criticality task rarely occurs), and at the same time, we are able to grant a sufficient amount of time to higher criticality tasks (in such cases, some of the lower criticality tasks may be skipped). This paper shows a motivation for the non-preemptive mixed-criticality match-up scheduling problem arising from the area of the communication protocols. Using a polynomial reduction from the 3-partition problem, we prove the problem to be NP-hard in the strong sense even when the release dates and deadlines are dropped and only two criticality levels are considered.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

JC - Počítačový hardware a software

OECD FORD obor

—

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2016

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

Journal of Scheduling

ISSN

1094-6136

e-ISSN

—

Svazek periodika

19

Číslo periodika v rámci svazku

5

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

7

Strana od-do

601-607

Kód UT WoS článku

000383661100006

EID výsledku v databázi Scopus

2-s2.0-84960086345