| 1. |
- Karlsson, Emil, 1990-
(författare)
-
Optimisation methods for solving a large-scale avionics scheduling problem
- 2021
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- 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.
|
|
| 2. |
- Karlsson, Emil, 1990-, et al.
(författare)
-
Strengthening of feasibility cuts in logic-based Benders decomposition
- 2021
-
Ingår i: INTEGRATION OF CONSTRAINT PROGRAMMING, ARTIFICIAL INTELLIGENCE, AND OPERATIONS RESEARCH. - Cham : Springer. - 9783030782290 - 9783030782306 ; , s. 45-61
-
Konferensbidrag (refereegranskat)abstract
- As for any decomposition method, the computational performance of a logic-based Benders decomposition (LBBD) scheme relies on the quality of the feedback information. Therefore, an important acceleration technique in LBBD is to strengthen feasibility cuts by reducing their sizes. This is typically done by solving additional subproblems to evaluate potential cuts. In this paper, we study three cut-strengthening algorithms that differ in the computational efforts made to find stronger cuts and in the guarantees with respect to the strengths of the cuts. We give a unified description of these algorithms and present a computational evaluation of their impact on the efficiency of a LBBD scheme. This evaluation is made for three different problem formulations, using over 2000 instances from five different applications. Our results show that it is usually beneficial to invest the time needed to obtain irreducible cuts. In particular, the use of the depth-first binary search cut-strengthening algorithm gives a good performance. Another observation is that when the subproblem can be separated into small independent problems, the impact of cut strengthening is dominated by that of the separation, which has an automatic strengthening effect.
|
|
| 3. |
- Lehtveer, Mariliis, 1983, et al.
(författare)
-
Actuating the European Energy System Transition: Indicators for Translating Energy Systems Modelling Results into Policy-Making
- 2021
-
Ingår i: Frontiers in Energy Research. - : Frontiers Media SA. - 2296-598X. ; 9
-
Tidskriftsartikel (refereegranskat)abstract
- In this paper, we define indicators, with a focus on the electricity sector, that translate the results of energy systems modelling to quantitative entities that can facilitate assessments of the transitions required to meet stringent climate targets. Such indicators, which are often overlooked in model scenario presentations, can be applied to make the modelling results more accessible and are useful for managing the transition on the policy level, as well as for internal evaluations of modelling results. We propose a set of 13 indicators related to: 1) the resource and material usages in modelled energy system designs; 2) the rates of transition from current to future energy systems; and 3) the energy security in energy system modelling results. To illustrate its value, the proposed set of indicators is applied to energy system scenarios derived from an electricity system investment model for Northern Europe. We show that the proposed indicators are useful for facilitating discussions, raising new questions, and relating the modelling results to Sustainable Development Goals and thus facilitate better policy processes. The indicators presented here should not be seen as a complete set, but rather as examples. Therefore, this paper represents a starting point and a call to other modellers to expand and refine the list of indicators.
|
|
