On Solving Non-preemptive Mixed-criticality Match-up Scheduling Problem with Two and Three Criticality Levels
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F16%3A00322374" target="_blank" >RIV/68407700:21230/16:00322374 - isvavai.cz</a>
Alternative codes found
RIV/68407700:21730/16:00322374
Result on the web
<a href="https://arxiv.org/abs/1610.07384" target="_blank" >https://arxiv.org/abs/1610.07384</a>
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
On Solving Non-preemptive Mixed-criticality Match-up Scheduling Problem with Two and Three Criticality Levels
Original language description
In this paper, we study an NP-hard problem of a single machine scheduling minimizing the makespan, where the mixed-critical tasks with an uncertain processing time are scheduled. We show the derivation of F-shaped tasks from the probability distribution function of the processing time, then we study the structure of problems with two and three criticality levels for which we propose efficient exact algorithms and we present computational experiments for instances with up to 200 tasks. Moreover, we show that the considered problem is approximable within a constant multiplicative factor.
Czech name
—
Czech description
—
Classification
Type
O - Miscellaneous
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
<a href="/en/project/GA16-23509S" target="_blank" >GA16-23509S: Flexible Scheduling and Optimization Algorithms for Distributed Real-time Embedded Systems</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2016
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů