| 1. |
- Blikstad, Mathias, et al.
(författare)
-
An optimisation approach for pre-runtime scheduling of tasks and communication in an integrated modular avionic system
- 2018
-
Ingår i: Optimization and Engineering. - : Springer Science and Business Media LLC. - 1389-4420 .- 1573-2924. ; 19:4, s. 977-1004
-
Tidskriftsartikel (refereegranskat)abstract
- 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.
|
|
| 2. |
- Karlsson, Emil, 1990-, et al.
(författare)
-
A matheuristic approach to large-scale avionic scheduling
- 2019
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- 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.
|
|
| 3. |
|
|
| 4. |
|
|
| 5. |
- Karlsson, Emil, 1990-, et al.
(författare)
-
Instance dataset for a multiprocessor scheduling problem with multiple time windows and time lags : Similar instances with large differences in difficulty
- 2022
-
Ingår i: Data in Brief. - : Elsevier. - 2352-3409. ; 45
-
Tidskriftsartikel (refereegranskat)abstract
- The dataset presented in this paper introduces 384 new instances for the feasibility version of a multiprocessor scheduling problem with multiple time windows, positive time lags and exact time lags. The instances are constructed from subproblems in a logic-based Benders decomposition scheme introduced in "Logic-based Benders decomposition with a partial assignment acceleration technique for an avionics scheduling problem" (Karlsson, E., Rönnberg, E., Computers & Operations Research, 2022) [1]. A key aspect of the dataset is that even if two instances are highly similar, the computational performance of solving them with an IBM ILOG CP Optimizer model can be vastly different. There exists for example 47 pairs of instances with the same number of tasks and exact time lags, and the number of positive time lags differs with at most two, where one instance can be solved within 5 minutes and the other instance cannot be solved within 24 hours. Such differences make the instance dataset useful for investigating differences in computational performance of constraint programming solvers. The dataset can also be used to benchmark methods for multiprocessor scheduling. The dataset has been released under the Creative Commons Attribution 4.0 International license and can be used as it is or be adapted.
|
|
| 6. |
- Karlsson, Emil, 1990-, et al.
(författare)
-
Logic-based Benders decomposition with a partial assignment acceleration technique for avionics scheduling
- 2022
-
Ingår i: Computers & Operations Research. - : Elsevier. - 0305-0548 .- 1873-765X. ; 146
-
Tidskriftsartikel (refereegranskat)abstract
- Pre-runtime scheduling of large-scale electronic systems, as those in modern aircraft, can be computationally challenging. In this paper, we study a distributed integrated modular avionic system of practical relevance where the scheduling includes to assign communication messages to time slots and to sequence tasks on modules. For this problem, the challenge is the huge number of tasks to be scheduled and the intricate interaction between the communication and task scheduling. We present a method based on Logic-Based Benders Decomposition (LBBD) to solve this problem. In a master problem, formulated as a mixed-integer program, communication messages are assigned to time slots and in a subproblem, formulated as a constraint program, tasks are scheduled.Our LBBD scheme is accelerated by using cut strengthening, a subproblem relaxation, and components for preprocessing and initialisation of the scheme. The cut strengthening is of the kind that systematically investigates subsets of variables to include in the cut by solving additional subproblems. To further enhance the efficiency of the scheme, we propose a new strategy that extends cut strengthening to also try to construct feasible solutions by using information from solving the additional subproblems. Our computational evaluation is based on publicly available instances with up to 2530 messages and 54,731 tasks. It shows that our method outperforms previous methods for the problem with respect to both solution times and RAM usage. A further evaluation of the different components in the method shows that our new acceleration strategy is important to achieve these results.
|
|
| 7. |
- Karlsson, Emil, 1990-
(författare)
-
Optimisation-based scheduling of an avionic system
- 2019
-
Licentiatavhandling (övrigt vetenskapligt/konstnärligt)abstract
- 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.
|
|
| 8. |
- 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.
|
|
| 9. |
- 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.
|
|
| 10. |
- 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.
|
|
