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

Result code in 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>

Alternative codes found

RIV/68407700:21730/22:00353816

Result on the web

<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>

Result language

angličtina

Original language name

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

Original language description

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.

Czech name

—

Czech description

—

Type

J_imp - 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)

Project

<a href="/en/project/EF15_003%2F0000466" target="_blank" >EF15_003/0000466: Artificial Intelligence and Reasoning</a><br>

Continuities

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

Publication year

2022

Confidentiality

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

Name of the periodical

Annals of Operations Research

ISSN

0254-5330

e-ISSN

1572-9338

Volume of the periodical

309

Issue of the periodical within the volume

1

Country of publishing house

US - UNITED STATES

Number of pages

24

Pages from-to

209-232

UT code for WoS article

000736784600001

EID of the result in the Scopus database

2-s2.0-85122668693