liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Explicit modelling of multiple intervals in a constraint generation procedure for multiprocessor scheduling
Linköping University, Department of Mathematics, Optimization . Linköping University, Faculty of Science & Engineering. Saab AB, Linköping, Sweden.ORCID iD: 0000-0002-9498-1924
Linköping University, Department of Mathematics, Optimization . Linköping University, Faculty of Science & Engineering. Saab AB, Linköping, Sweden.ORCID iD: 0000-0002-2081-2888
2017 (English)In: Operations Research Proceedings 2017 / [ed] N. Kliewer, J.F. Ehmke and R. Borndörfer, Springer, 2017, p. 567-572Conference paper, Published paper (Refereed)
Abstract [en]

Multiprocessor scheduling is a well studied NP-hard optimisation problem that occurs in variety of forms. The focus of this paper is explicit modelling of multiple task intervals. This work extends a constraint generation procedure previously developed for an avionics scheduling context. We here address a relaxation of the original problem and this relaxation can be considered as multiprocessor scheduling with precedence relations and multiple intervals.

The explicit modelling of multiple intervals strengthens the formulation used in the constraint generation procedure and we illustrate the computational effects on an industrial relevant avionics scheduling problem.

Place, publisher, year, edition, pages
Springer, 2017. p. 567-572
Series
Operations Research Proceedings, ISSN 0721-5924
Keywords [en]
multiprocessor scheduling, multiple intervals, avionics scheduling and constraint generation
National Category
Computational Mathematics
Identifiers
URN: urn:nbn:se:liu:diva-143021DOI: 10.1007/978-3-319-89920-6_75ISBN: 978-3-319-89919-0 (print)ISBN: 978-3-319-89920-6 (electronic)OAI: oai:DiVA.org:liu-143021DiVA, id: diva2:1157697
Conference
Operations Research 2017, Freie Universität Berlin, Berlin, Germany, September 6-8, 2017
Available from: 2017-11-16 Created: 2017-11-16 Last updated: 2019-05-24Bibliographically approved
In thesis
1. Optimisation-based scheduling of an avionic system
Open this publication in new window or tab >>Optimisation-based scheduling of an avionic system
2019 (English)Licentiate thesis, comprehensive summary (Other academic)
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.

Place, publisher, year, edition, pages
Linköping: Linköping University Electronic Press, 2019. p. 38
Series
Linköping Studies in Science and Technology. Licentiate Thesis, ISSN 0280-7971 ; 1844
National Category
Mathematics
Identifiers
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 (English)
Opponent
Supervisors
Available from: 2019-05-24 Created: 2019-05-09 Last updated: 2019-05-29Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full text

Authority records BETA

Karlsson, EmilRönnberg, Elina

Search in DiVA

By author/editor
Karlsson, EmilRönnberg, Elina
By organisation
Optimization Faculty of Science & Engineering
Computational Mathematics

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 1177 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf