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

Result code in 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>

Result on the web

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

Result language

angličtina

Original language name

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

Original language description

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.

Czech name

—

Czech description

—

Type

J_x - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)

CEP classification

JC - Computer hardware and software

OECD FORD branch

—

Project

—

Continuities

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year

2016

Confidentiality

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

Name of the periodical

Journal of Scheduling

ISSN

1094-6136

e-ISSN

—

Volume of the periodical

19

Issue of the periodical within the volume

5

Country of publishing house

NL - THE KINGDOM OF THE NETHERLANDS

Number of pages

7

Pages from-to

601-607

UT code for WoS article

000383661100006

EID of the result in the Scopus database

2-s2.0-84960086345