An analysis of the non-preemptive mixed-criticality match-up scheduling problem

Many applications have a mixed‐criticality nature. They contain tasks with a different criticality, meaning that a task with a lower criticality can be skipped if a task with a higher criticality needs more time to be executed. This paper deals with a mixed‐criticality scheduling problem where each task has a criticality given by a positive integer number. The exact processing time of the task is not known. Instead, we use different upper bounds of the processing time for different criticality levels of the schedule. A schedule with different criticality levels is generated off‐line, but its on‐line execution switches among the criticality levels depending on the actual values of the processing times. The advantage is that after the transient prolongation of a higher criticality task, the system is able to match up with the schedule on a lower criticality level. While using this model, we achieve significant schedule efficiency (assuming that the prolongation of the higher criticality task rarely occurs), and at the same time, we are able to grant a sufficient amount of time to higher criticality tasks (in such cases, some of the lower criticality tasks may be skipped). This paper shows a motivation for the non‐preemptive mixed‐criticality match‐up scheduling problem arising from the area of the communication protocols. Using a polynomial reduction from the 3‐partition problem, we prove the problem to be $\mathcal{NP}$ ‐hard in the strong sense even when the release dates and deadlines are dropped and only two criticality levels are considered.