Strictly periodic scheduling in IMA-based architectures

The avionic industry has recently adopted the Integrated Modular Avionics (IMA). Such architectures allow the execution of avionic functions on a shared computing platform while avoiding any interference between them. This is done through hard memory and temporal segregation constraints. Although IMA reduces the weight and the power consumption and shortens the design-cycle times, it gives rise to a complex multiprocessor scheduling problem. One of the key difficulties of this problem is related to the strict periodicity of tasks, which means that the time separating two successive executions of the same task is strictly equal to the associated period. In order to help the system designer in producing a proper schedule, an exact formulation based on Integer Linear Programming and a heuristic inspired from Game Theory are proposed. To enhance the solution quality of the heuristic, a?multi-start method, which gives some probabilistic guarantees on the optimality of the solutions, is also introduced.