liu.seSearch for publications in DiVA
Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
A matheuristic approach to large-scale avionic scheduling
Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska fakulteten. Saab AB, SE-581 88 Linköping.ORCID-id: 0000-0002-9498-1924
Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska fakulteten. Saab AB, SE-581 88 Linköping.
Saab AB, SE-581 88 Linköping.
Saab AB, SE-581 88 Linköping.
2019 (engelsk)Rapport (Annet vitenskapelig)
Abstract [en]

Pre-runtime scheduling of avionic systems is used to ensure that the systems provide the desired functionality at the correct time. This paper considers scheduling of an integrated modular avionic system which from a more general perspective can be seen as a multiprocessor scheduling problem that includes a communication network. The addressed system is practically relevant and the computational evaluations are made on large-scale instances developed together with the industrial partner Saab. A subset of the instances is made publicly available.

Our contribution is a matheuristic for solving these large-scale instances and it is obtained by improving the model formulations used in a previously suggested constraint generation procedure and by including an adaptive large neighbourhood search to extend it into a matheuristic. Characteristics of our adaptive large neighbourhood search are that it is made over both discrete and continuous variables and that it needs to balance the search for feasibility and profitable objective value. The repair operation is to apply a mixed-integer programming solver on a model where most of the constraints are treated as soft and a violation of them is instead penalised in the objective function. The largest solved instance, with respect to the number of tasks, has 45 988 tasks and 2 011 communication messages.

sted, utgiver, år, opplag, sider
Linköping: Linköping University Electronic Press, 2019. , s. 40
Serie
LiTH-MAT-R, ISSN 0348-2960 ; 2019:2
Emneord [en]
Multiprocessor scheduling; avionic system; matheuristic; adaptive large neighbourhood search; integer programming; scheduling
HSV kategori
Identifikatorer
URN: urn:nbn:se:liu:diva-157140ISRN: LiTH-MAT-R--2019/02--SEOAI: oai:DiVA.org:liu-157140DiVA, id: diva2:1318929
Tilgjengelig fra: 2019-05-29 Laget: 2019-05-29 Sist oppdatert: 2019-05-29
Inngår i avhandling
1. Optimisation-based scheduling of an avionic system
Åpne denne publikasjonen i ny fane eller vindu >>Optimisation-based scheduling of an avionic system
2019 (engelsk)Licentiatavhandling, med artikler (Annet vitenskapelig)
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.

sted, utgiver, år, opplag, sider
Linköping: Linköping University Electronic Press, 2019. s. 38
Serie
Linköping Studies in Science and Technology. Licentiate Thesis, ISSN 0280-7971 ; 1844
HSV kategori
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 (engelsk)
Opponent
Veileder
Tilgjengelig fra: 2019-05-24 Laget: 2019-05-09 Sist oppdatert: 2019-05-29bibliografisk kontrollert

Open Access i DiVA

Fulltekst mangler i DiVA

Personposter BETA

Karlsson, EmilRönnberg, Elina

Søk i DiVA

Av forfatter/redaktør
Karlsson, EmilRönnberg, Elina
Av organisasjonen

Søk utenfor DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric

urn-nbn
Totalt: 418 treff
RefereraExporteraLink to record
Permanent link

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