An Analysis of the Non-preemptive Mixed-criticality Match-up Scheduling Problem
The result's identifiers
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>
Alternative languages
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
—
Classification
Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
JC - Computer hardware and software
OECD FORD branch
—
Result continuities
Project
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2016
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
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