Computing the execution probability of jobs with replication in mixed-criticality schedules

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F22%3A00353816" target="_blank" >RIV/68407700:21230/22:00353816 - isvavai.cz</a>

Nalezeny alternativní kódy

RIV/68407700:21730/22:00353816

Výsledek na webu

<a href="https://doi.org/10.1007/s10479-021-04445-x" target="_blank" >https://doi.org/10.1007/s10479-021-04445-x</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/s10479-021-04445-x" target="_blank" >10.1007/s10479-021-04445-x</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Computing the execution probability of jobs with replication in mixed-criticality schedules

Popis výsledku v původním jazyce

Mixed-criticality scheduling addresses the problem of sharing common resources among jobs of different degrees of criticality and uncertain processing times. The processing time of jobs is observed during the online execution of the schedule with the prolongations of critical jobs being compensated by the rejection of less critical ones. One of the central questions in the field of mixed-criticality scheduling is ensuring the high reliability of the system with as few resources as possible. In this paper, we study the computation of the execution probability of jobs with uncertain processing times in a static mixed-criticality schedule. The aim is to compute the execution probability of jobs (i.e., the objective function of a schedule), which is a problem solvable by a closed-form formula when the jobs are not replicated. We introduce the job replication, i.e., scheduling a single job multiple times, as a new mechanism for increasing the execution probability of jobs. We show that the general problem with job replication becomes #P-hard, which is proven by the reduction from the counting variant of 3-SAT problem. To compute the execution probability, we propose an algorithm utilizing the framework of Bayesian networks. Furthermore, we show that cases of practical interest admit a polynomial-time algorithm and are efficiently solvable. The proposed methodology demonstrates an interesting connection between schedules with uncertain execution and probabilistic graphical models and opens a new approach to the analysis of mixed-criticality schedules.

Název v anglickém jazyce

Computing the execution probability of jobs with replication in mixed-criticality schedules

Popis výsledku anglicky

Mixed-criticality scheduling addresses the problem of sharing common resources among jobs of different degrees of criticality and uncertain processing times. The processing time of jobs is observed during the online execution of the schedule with the prolongations of critical jobs being compensated by the rejection of less critical ones. One of the central questions in the field of mixed-criticality scheduling is ensuring the high reliability of the system with as few resources as possible. In this paper, we study the computation of the execution probability of jobs with uncertain processing times in a static mixed-criticality schedule. The aim is to compute the execution probability of jobs (i.e., the objective function of a schedule), which is a problem solvable by a closed-form formula when the jobs are not replicated. We introduce the job replication, i.e., scheduling a single job multiple times, as a new mechanism for increasing the execution probability of jobs. We show that the general problem with job replication becomes #P-hard, which is proven by the reduction from the counting variant of 3-SAT problem. To compute the execution probability, we propose an algorithm utilizing the framework of Bayesian networks. Furthermore, we show that cases of practical interest admit a polynomial-time algorithm and are efficiently solvable. The proposed methodology demonstrates an interesting connection between schedules with uncertain execution and probabilistic graphical models and opens a new approach to the analysis of mixed-criticality schedules.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

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

Projekt

<a href="/cs/project/EF15_003%2F0000466" target="_blank" >EF15_003/0000466: Umělá inteligence a uvažování</a><br>

Návaznosti

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

Rok uplatnění

2022

Kód důvěrnosti údajů

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

Název periodika

Annals of Operations Research

ISSN

0254-5330

e-ISSN

1572-9338

Svazek periodika

309

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

24

Strana od-do

209-232

Kód UT WoS článku

000736784600001

EID výsledku v databázi Scopus

2-s2.0-85122668693