Pre-Runtime Scheduling of an Avionics System

Sammanfattning: This master's thesis addresses a scheduling problem arising when designing avionics – the electronic systems used on aircraft. Currently, the problem is commonly solved using mixed integer programming (MIP). We prove the scheduling problem at-hand, which is similar to the well-studied cyclic job shop scheduling problem, is NP-hard. Furthermore, we propose an approach using constraint programming (CP) – a programming paradigm where entities called constraints define the relations between variables. Constraints do not specify a step or sequence of steps to execute, but rather the necessary properties of a solution. The CP approach implemented in the high-quality free OscaR CP solver manages around 1500 tasks in total over 10 processors within a 10 minute timeout, which is good enough for CP to be investigated further as a possible paradigm for solving the considered scheduling problem. We also compare Gurobi Optimizer, a high-quality commercial MIP solver, to Gecode, another high-quality free CP solver, when run on a model for the problem described in the MiniZinc modelling language.