Pre-Runtime Scheduling of an Avionics System
Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesis
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.
Place, publisher, year, edition, pages
2016. , 48 p.
Engineering and Technology
IdentifiersURN: urn:nbn:se:uu:diva-300679OAI: oai:DiVA.org:uu-300679DiVA: diva2:951889
Master Programme in Computer Science
Flener, PierreNgai, Edith