liu.seSök publikationer i DiVA
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
An optimisation approach for pre-runtime scheduling of tasks and communication in an integrated modular avionic system
Saab AB, Linköping, Sweden.
Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska fakulteten. Saab AB, Linköping, Sweden.ORCID-id: 0000-0002-9498-1924
Saab AB, Linköping, Sweden.
Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska fakulteten. Saab AB, Linköping, Sweden.ORCID-id: 0000-0002-2081-2888
2018 (Engelska)Ingår i: Optimization and Engineering, ISSN 1389-4420, E-ISSN 1573-2924, Vol. 19, nr 4, s. 977-1004Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

In modern integrated modular avionic systems, applications share hardware resources on a common avionic platform. Such an architecture necessitates strict requirements on the spatial and temporal partitioning of the system to prevent fault propagation between different aircraft functions. One way to establish a temporal partitioning is through pre-runtime scheduling of the system, which involves creating a schedule for both tasks and a communication network. While avionic systems are growing more and more complex, so is the challenge of scheduling them. The scheduling of the system has an important role in the development of new avionic systems, since functionality is typically added to the system over a period of several years and a scheduling tool is used both to detect if the platform can host the new functionality and, if this is possible, to create a new schedule. For this reason an exact solution strategy for avionics scheduling is preferred over a heuristic one. In this paper we present a mathematical model for an industrially relevant avionic system and present a constraint generation procedure for the scheduling of such systems. We apply our optimisation approach to instances provided by our industrial partner. These instances are of relevance for the development of future avionic systems and contain up to 20,000 tasks to be scheduled. The computational results show that our optimisation approach can be used to create schedules for such instances within a reasonable time.

Ort, förlag, år, upplaga, sidor
2018. Vol. 19, nr 4, s. 977-1004
Nyckelord [en]
Avionic system Scheduling Discrete optimisation Integer programming Multiprocessor scheduling Constraint generation
Nationell ämneskategori
Matematik
Identifikatorer
URN: urn:nbn:se:liu:diva-148854DOI: 10.1007/s11081-018-9385-6ISI: 000447870700007OAI: oai:DiVA.org:liu-148854DiVA, id: diva2:1221929
Anmärkning

Funding agencies: Swedish Armed Forces; Swedish Defence Materiel Administration; Swedish Governmental Agency for Innovation Systems [NFFP6-2014-00917]; Center for Industrial Information Technology (CENIIT); Research School in Interdisciplinary Mathematics at Linkoping Univ

Tillgänglig från: 2018-06-20 Skapad: 2018-06-20 Senast uppdaterad: 2019-05-24
Ingår i avhandling
1. Optimisation-based scheduling of an avionic system
Öppna denna publikation i ny flik eller fönster >>Optimisation-based scheduling of an avionic system
2019 (Engelska)Licentiatavhandling, sammanläggning (Övrigt vetenskapligt)
Abstract [en]

Modern computer systems in aircraft are often based on an integrated modular avionic architecture. In this architecture, software applications share hardware resources on a common avionic platform. Many functions in an aircraft are controlled by software and a failure in such software can have severe consequences. In order to avoid malfunction, there are many aspects to consider. One aspect is to ensure that the activities in the system is done at the right time with the right resources. To analyse if this is possible or not is often called schedulability analysis.

When multiple functions are using the same resources, the schedulability analysis becomes increasingly challenging. This thesis focuses on a pre-runtime scheduling problem of an integrated modular avionic system proposed by our industrial partner Saab. The purpose of this problem is to find a feasible schedule or prove that none exists as part of a schedulability analysis.

For the system that we study, there are two major challenges. One is that task and communication scheduling are integrated and the other is that there is a large amount of tasks to schedule. For the largest instances, there are more than 10 000 tasks on a single module. In order to solve such problems, we have developed a matheuristic. At the core of this matheuristic is a constraint generation procedure designed to handle the challenges of the scheduling problem.

The constraint generation procedure is based on first making a relaxed scheduling decision and then evaluating this in a separate problem where a complete schedule is produced. This yields a decomposition where most technical details are considered in the relaxed problem, and the actual scheduling of tasks is handled in a subproblem. Both the relaxed problem and the subproblem are formulated and solved as mixed integer programs.

The heuristic component of the matheuristic is that the relaxed problem is solved using an adaptive large neighbourhood search method. Instead of solving the relaxed problem as a single mixed integer program, the adaptive large neighbourhood search explores neighbourhoods through solving a series of mixed integer programs. Features of this search method are that it is made over both discrete and continuous variables and it needs to balance feasibility against profitable objective value.

The matheuristic described in this thesis has been implemented in a scheduling tool. This scheduling tool has been applied to instances provided by our industrial partner and to a set of public instances that we have developed. With this tool, we have solved instances with more than 45 000 tasks.

Ort, förlag, år, upplaga, sidor
Linköping: Linköping University Electronic Press, 2019. s. 38
Serie
Linköping Studies in Science and Technology. Licentiate Thesis, ISSN 0280-7971 ; 1844
Nationell ämneskategori
Matematik
Identifikatorer
urn:nbn:se:liu:diva-156695 (URN)10.3384/lic.diva-156695 (DOI)9789176850565 (ISBN)
Presentation
2019-06-13, Nobel BL32, B Building, Campus Valla, Linköping, 13:15 (Engelska)
Opponent
Handledare
Tillgänglig från: 2019-05-24 Skapad: 2019-05-09 Senast uppdaterad: 2020-03-12Bibliografiskt granskad

Open Access i DiVA

fulltext(1288 kB)112 nedladdningar
Filinformation
Filnamn FULLTEXT01.pdfFilstorlek 1288 kBChecksumma SHA-512
9dbf859085deafbe032c9f44973116829a53d3075b02187683786fc989e2cfbf915af773d82a9462c9e5cff9da59185343d5701cd7b1c0738a4798355787c006
Typ fulltextMimetyp application/pdf

Övriga länkar

Förlagets fulltext

Personposter BETA

Karlsson, EmilRönnberg, Elina

Sök vidare i DiVA

Av författaren/redaktören
Blikstad, MathiasKarlsson, EmilRönnberg, Elina
Av organisationen
OptimeringsläraTekniska fakulteten
I samma tidskrift
Optimization and Engineering
Matematik

Sök vidare utanför DiVA

GoogleGoogle Scholar
Totalt: 112 nedladdningar
Antalet nedladdningar är summan av nedladdningar för alla fulltexter. Det kan inkludera t.ex tidigare versioner som nu inte längre är tillgängliga.

doi
urn-nbn

Altmetricpoäng

doi
urn-nbn
Totalt: 254 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf