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

Direct link
Referera
Referensformat
  • apa
  • 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
Optimisation methods for solving a large-scale avionics scheduling problem
Linköpings universitet, Matematiska institutionen, Tillämpad matematik. Linköpings universitet, Tekniska fakulteten.ORCID-id: 0000-0002-9498-1924
2021 (engelsk)Doktoravhandling, med artikler (Annet vitenskapelig)
Abstract [en]

Modern computer systems in aircraft are 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. To avoid malfunction, there are many aspects to consider. One aspect is to ensure that the activities in the system get sufficient computing and network communication resources while being completed in time. This thesis contributes to addressing this challenge by studying an avionics scheduling problem proposed by Saab.

In this problem, tasks are performed on modules and the messages are sent on a communication network that links the modules. A schedule specifies start times for tasks on modules and the choices of time slots for messages on the communication network. For a schedule to be feasible, constraints must be respected: precedence constraints between tasks, timing constraints on tasks and messages, and communication network constraints involving both tasks and messages. For future platforms, it is expected that large-scale instances need to be solved. The methods introduced in this thesis solve instances with up to 55,000 tasks and 2500 messages.

The thesis includes three papers that introduce methods for solving the avionics scheduling problem and one paper that compares techniques to improve the performance of a specific type of decomposition method. The solution methods for the avionics problem differ in how the decomposition is made, how the subproblems are solved, and if the algorithm is guaranteed to find a feasible solution or not, given enough time. Together, the contributions of these papers give an insight into the structure of this type of avionics scheduling problem and how this structure can be exploited to construct efficient exact and matheuristic scheduling methods.

Paper A introduces a constraint generation procedure tailored for the avionics scheduling problem. In the constraint generation procedure, a preliminary, possibly infeasible, schedule is constructed by solving a master problem. This schedule is used to define a restriction of the problem, which is solved to find a complete schedule. If no schedule is found within a time-limit, constraints are added to the master problem, which is then solved again. This procedure relies on solving Mixed-Integer Programming (MIP) models. In Paper B, the constraint generation procedure is extended into a matheuristic, where the master problem is solved with a MIP-based adaptive large neighbourhood search. The methods in Paper A and Paper B can solve instances with up to 37,000 tasks and 1700 messages, and 55,000 tasks and 2500 messages, respectively.

Logic-Based Benders Decomposition (LBBD) algorithms are treated in Paper C and Paper D. In both papers, a MIP solver is applied to the master problem while a constraint programming solver is used for the subproblem. Paper C addresses the avionics scheduling problem and introduces a new acceleration technique for LBBD. This technique exploits information obtained during cut strengthening to make educated guesses about where feasible solutions might be found. With this technique, the LBBD algorithm outperforms the methods from Paper A and Paper B both with respect to solution time and RAM usage. Paper D investigates cut strengthening for LBBD in a wider context, by evaluating different cut-strengthening algorithms for LBBD on three problems from the literature. The computational evaluation shows that it is advantageous to invest time in finding strong cuts.

sted, utgiver, år, opplag, sider
Linköping: Linköping University Electronic Press, 2021. , s. 48
Serie
Linköping Studies in Science and Technology. Dissertations, ISSN 0345-7524 ; 2136
Emneord [en]
Optimisation, Decomposition, Large-scale scheduling, Avionics scheduling
HSV kategori
Identifikatorer
URN: urn:nbn:se:liu:diva-173564DOI: 10.3384/diss.diva-173564ISBN: 9789179296735 (tryckt)OAI: oai:DiVA.org:liu-173564DiVA, id: diva2:1530784
Disputas
2021-06-04, Online through Zoom (contact elina.ronnberg@liu.se), 13:15 (engelsk)
Opponent
Veileder
Tilgjengelig fra: 2021-04-30 Laget: 2021-02-24 Sist oppdatert: 2021-04-30bibliografisk kontrollert
Delarbeid
1. An optimisation approach for pre-runtime scheduling of tasks and communication in an integrated modular avionic system
Åpne denne publikasjonen i ny fane eller vindu >>An optimisation approach for pre-runtime scheduling of tasks and communication in an integrated modular avionic system
2018 (engelsk)Inngår i: Optimization and Engineering, ISSN 1389-4420, E-ISSN 1573-2924, Vol. 19, nr 4, s. 977-1004Artikkel i tidsskrift (Fagfellevurdert) 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.

Emneord
Avionic system Scheduling Discrete optimisation Integer programming Multiprocessor scheduling Constraint generation
HSV kategori
Identifikatorer
urn:nbn:se:liu:diva-148854 (URN)10.1007/s11081-018-9385-6 (DOI)000447870700007 ()
Merknad

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

Tilgjengelig fra: 2018-06-20 Laget: 2018-06-20 Sist oppdatert: 2021-02-24
2. A matheuristic approach to large-scale avionic scheduling
Åpne denne publikasjonen i ny fane eller vindu >>A matheuristic approach to large-scale avionic scheduling
2021 (engelsk)Inngår i: Annals of Operations Research, ISSN 0254-5330, E-ISSN 1572-9338, Vol. 302, s. 425-459Artikkel i tidsskrift (Fagfellevurdert) Published
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 54,731 tasks and 2530 communication messages.

sted, utgiver, år, opplag, sider
SPRINGER, 2021
Emneord
Multiprocessor scheduling; Avionic system; Matheuristic; Adaptive large neighbourhood search; Integer programming; Scheduling
HSV kategori
Identifikatorer
urn:nbn:se:liu:diva-166177 (URN)10.1007/s10479-020-03608-6 (DOI)000532612400001 ()
Merknad

Funding Agencies|Linkoping University - Center for Industrial Information Technology (CENIIT) [16.05]; Research School in Interdisciplinary Mathematics at Linkoping University

Tilgjengelig fra: 2020-06-09 Laget: 2020-06-09 Sist oppdatert: 2022-10-03

Open Access i DiVA

fulltext(12980 kB)1545 nedlastinger
Filinformasjon
Fil FULLTEXT02.pdfFilstørrelse 12980 kBChecksum SHA-512
f5409ae1715fecf4fe68c614b4a1c8647223906e94c0cc4be667504b96b68339fa6b927901929bc48fbe6893a42170d789057af0ccc1e682eb25b892f4feeb84
Type fulltextMimetype application/pdf
Bestill online >>

Andre lenker

Forlagets fulltekst

Person

Karlsson, Emil

Søk i DiVA

Av forfatter/redaktør
Karlsson, Emil
Av organisasjonen

Søk utenfor DiVA

GoogleGoogle Scholar
Totalt: 1554 nedlastinger
Antall nedlastinger er summen av alle nedlastinger av alle fulltekster. Det kan for eksempel være tidligere versjoner som er ikke lenger tilgjengelige

doi
isbn
urn-nbn

Altmetric

doi
isbn
urn-nbn
Totalt: 2951 treff
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • 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