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”

Scheduling with uncertain processing times in mixed-criticality systems

The result's identifiers

  • Result code in IS VaVaI

    <a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F19%3A00332277" target="_blank" >RIV/68407700:21230/19:00332277 - isvavai.cz</a>

  • Alternative codes found

    RIV/68407700:21730/19:00332277

  • Result on the web

    <a href="https://doi.org/10.1016/j.ejor.2019.05.038" target="_blank" >https://doi.org/10.1016/j.ejor.2019.05.038</a>

  • DOI - Digital Object Identifier

    <a href="http://dx.doi.org/10.1016/j.ejor.2019.05.038" target="_blank" >10.1016/j.ejor.2019.05.038</a>

Alternative languages

  • Result language

    angličtina

  • Original language name

    Scheduling with uncertain processing times in mixed-criticality systems

  • Original language description

    Many scheduling problems that can be identified inside safety-critical applications, such as in autonomous cars, tend to be mixed-critical. Such scheduling problems consider tasks to have different criticalities depending on the safety levels (activation of brakes vs. activation of air-conditioning). The biggest challenge in those scheduling problems arises from the uncertainty of processing times as it disturbs the predictability of the system and thus makes the certification of the system difficult. To overcome this uncertainty, we model the tasks to have multiple processing times concerning their criticality. This approach converts these scheduling problems into a deterministic scheduling with alternative processing times. Here, we study an NP-hard single machine scheduling problem with makespan minimization, where the non-preemptive tasks can have multiple processing times. To solve the problem, we propose an approximation algorithm, a novel mixed-integer linear programming block formulation, and an efficient exact branch-and-price decomposition for two criticality levels. Furthermore, we demonstrate that the optimal schedules are represented as trees, which enables to formulate an exact algorithm for the problem with three criticality levels. The efficiency of the proposed method is demonstrated for difficult problem instances with up to 1000 tasks. The experimental evaluation demonstrates that our algorithms have improved the results of the best-known method by nearly two orders of magnitude.

  • Czech name

  • Czech description

Classification

  • Type

    J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database

  • CEP classification

  • OECD FORD branch

    10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Result continuities

  • Project

    Result was created during the realization of more than one project. More information in the Projects tab.

  • Continuities

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

Others

  • Publication year

    2019

  • 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

    European Journal of Operational Research

  • ISSN

    0377-2217

  • e-ISSN

    1872-6860

  • Volume of the periodical

    279

  • Issue of the periodical within the volume

    3

  • Country of publishing house

    NL - THE KINGDOM OF THE NETHERLANDS

  • Number of pages

    17

  • Pages from-to

    687-703

  • UT code for WoS article

    000481560600002

  • EID of the result in the Scopus database

    2-s2.0-85068037622