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

Antonin Novak () and Zdenek Hanzalek
Additional contact information
Antonin Novak: Czech Technical University in Prague
Zdenek Hanzalek: Czech Technical University in Prague

Annals of Operations Research, 2022, vol. 309, issue 1, No 9, 209-232

Abstract: Abstract 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 $$\#{\mathcal {P}}$$ # 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.

Keywords: Mixed-criticality; Job replication; Scheduling; Bayesian networks; Computational complexity; Uncertain processing time (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10479-021-04445-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:309:y:2022:i:1:d:10.1007_s10479-021-04445-x

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-021-04445-x

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().