Many scheduling problems that can be identified inside safety-critical applications, such as in autonomous cars, tend to be mixed-critical. Such scheduling problems consider tasks to have different criticalities depending on the safety levels (activation of brakes vs. activation of air-conditioning). The biggest challenge in those scheduling problems arises from the uncertainty of processing times as it disturbs the predictability of the system and thus makes the certification of the system difficult. To overcome this uncertainty, we model the tasks to have multiple processing times concerning their criticality. This approach converts these scheduling problems into a deterministic scheduling with alternative processing times. Here, we study an N P-hard single machine scheduling problem with makespan minimization, where the non-preemptive tasks can have multiple processing times. To solve the problem, we propose an approximation algorithm, a novel mixed-integer linear programming block formulation, and an efficient exact branch-and-price decomposition for two criticality levels. Furthermore, we demonstrate that the optimal schedules are represented as trees, which enables to formulate an exact algorithm for the problem with three criticality levels. The efficiency of the proposed method is demonstrated for difficult problem instances with up to 1000 tasks. The experimental evaluation demonstrates that our algorithms have improved the results of the best-known method by nearly two orders of magnitude.

Introduction

This paper addresses scheduling in mixed-criticality systems where tasks have different degrees of importance (criticalities) and share a common resource. The key requirement of these systems is to isolate tasks such that a lower-criticality task does not influence any higher-criticality task. When the processing time of tasks is uncertain, the unexpected prolongation of a task may affect the execution of another task with higher criticality, which is extremely dangerous for safety-critical systems. A naive solution assuming the worst-case processing times leads to inefficient utilization of the resource. This is problematic, especially for embedded systems having limited computational and hardware resources. To overcome the processing time uncertainty, we utilize the so-called F-shaped tasks, where each task has an integer criticality and a set of alternative processing times. The schedules with F-shaped tasks are proactive and contain exponentially many alternative schedules, with the alternative being selected based on the realized processing time of a task that occurs during the runtime execution of the schedule. The structure of the schedule guarantees that in any of these alternatives, all highly critical tasks are performed, rejecting low-criticality tasks only if a more critical one is prolonged. At the same time, the resource is efficiently utilized since when critical tasks are not prolonged, low-criticality tasks may use the resource. Therefore, the proactive schedules with Fshaped tasks achieve a trade-off between the required safety margins and an efficient resource usage. An important advantage of this approach is that despite such flexibility, the schedules only take polynomial-sized space. In addition, even though the corresponding optimization problem is N P-hard, our exact algorithms are computationally efficient in practice.