Change search
ReferencesLink to record
Permanent link

Direct link
Pre-Runtime Scheduling of an Avionics System
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology.
2016 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesis
Abstract [en]

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.
Series
IT, 16043
National Category
Engineering and Technology
Identifiers
URN: urn:nbn:se:uu:diva-300679OAI: oai:DiVA.org:uu-300679DiVA: diva2:951889
Educational program
Master Programme in Computer Science
Supervisors
Examiners
Available from: 2016-08-10 Created: 2016-08-10 Last updated: 2016-08-10Bibliographically approved

Open Access in DiVA

fulltext(587 kB)22 downloads
File information
File name FULLTEXT01.pdfFile size 587 kBChecksum SHA-512
e51582cdea2a5014a70232fdbb1c5353b985ed88523560d01a7ec75814383f1a55d1dc085a325eda8aaf7dafd264fc4c50ca20b8eb14e44ab1ee35940272db37
Type fulltextMimetype application/pdf

By organisation
Department of Information Technology
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar
Total: 22 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 104 hits
ReferencesLink to record
Permanent link

Direct link