2026-07-20T05:38:33Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8992 2024-03-06T10:43:05Z ddc:004 open_access

Intractability Issues in Mixed-Criticality Scheduling Agrawal, Kunal Baruah, Sanjoy mixed-criticality scheduling speedup factor competitive ratio approximation ratio NP-completeness results sporadic tasks In seeking to develop mixed-criticality scheduling algorithms, one encounters challenges arising from two sources. First, mixed-criticality scheduling is an inherently an on-line problem in that scheduling decisions must be made without access to all the information that is needed to make such decisions optimally - such information is only revealed over time. Second, many fundamental mixed-criticality schedulability analysis problems are computationally intractable - NP-hard in the strong sense - but we desire to solve these problems using algorithms with polynomial or pseudo-polynomial running time. While these two aspects of intractability are traditionally studied separately in the theoretical computer science literature, they have been considered in an integrated fashion in mixed-criticality scheduling theory. In this work we seek to separate out the effects of being inherently on-line, and being computationally intractable, on the overall intractability of mixed-criticality scheduling problems. Speedup factor is widely used as quantitative metric of the effectiveness of mixed-criticality scheduling algorithms; there has recently been a bit of a debate regarding the appropriateness of doing so. We provide here some additional perspective on this matter: we seek to better understand its appropriateness as well as its limitations in this regard by examining separately how the on-line nature of some mixed-criticality problems, and their computational complexity, contribute to the speedup factors of two widely-studied mixed-criticality scheduling algorithms. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Kunal Agrawal and Sanjoy Baruah 2018 Is Part Of LIPIcs, Volume 106, 30th Euromicro Conference on Real-Time Systems (ECRTS 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ECRTS.2018.11 urn:nbn:de:0030-drops-89925 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2018.11 eng https://creativecommons.org/licenses/by/3.0/legalcode