All

What are you looking for?

All
Projects
Results
Organizations

Quick search

  • Projects supported by TA ČR
  • Excellent projects
  • Projects with the highest public support
  • Current projects

Smart search

  • That is how I find a specific +word
  • That is how I leave the -word out of the results
  • “That is how I can find the whole phrase”

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