2026-07-21T11:08:49Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26613 2026-07-02T09:39:09Z ddc:004 open_access

Semi-Clairvoyant Scheduling for Jobs with Multiple Criticalities Agrawal, Kunal Thai, Tung Duc Zhao, Jinhao mixed-criticality semi-clairvoyance schedulers linear programming This paper considers scheduling jobs semi-clairvoyantly in mixed-criticality systems. In the semi-clairvoyant model, unlike the non-clairvoyant model, we know the WCET mode of the job at job arrival. Prior work has only considered this model for dual criticality jobs. We consider this problem for an arbitrary number of criticalities. We prove that there exist semi-clairvoyant schedulers that guarantee schedulability with speedup (2^m-1)/2^{m-1} for systems with m criticality levels. In addition, we prove that this bound is tight by providing a job set construction that requires this speed for any semi-clairvoyant scheduler. Finally we provide a linear programming formulation that optimally schedules the semi-clairvoyant system of jobs. The number of variables and constraints is polynomial in the number of jobs, but exponential in the number of criticalities. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Kunal Agrawal and Tung Duc Thai and Jinhao Zhao 2026 Is Part Of LIPIcs, Volume 375, 38th European Conference on Real-Time Systems (ECRTS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ECRTS.2026.21 urn:nbn:de:0030-drops-266130 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2026.21 eng https://creativecommons.org/licenses/by/4.0/legalcode