Sökning: WFRF:(Karlsson Emil 1990 )
> (2022) >
Logic-based Benders...
Logic-based Benders decomposition with a partial assignment acceleration technique for avionics scheduling
-
- Karlsson, Emil, 1990- (författare)
- Linköpings universitet,Tillämpad matematik,Tekniska fakulteten,Saab AB, Linköping, Sweden
-
- Rönnberg, Elina, 1981- (författare)
- Linköpings universitet,Tillämpad matematik,Tekniska fakulteten
-
(creator_code:org_t)
- Elsevier, 2022
- 2022
- Engelska.
-
Ingår i: Computers & Operations Research. - : Elsevier. - 0305-0548 .- 1873-765X. ; 146
- Relaterad länk:
-
https://liu.diva-por... (primary) (Raw object)
-
visa fler...
-
https://urn.kb.se/re...
-
https://doi.org/10.1...
-
visa färre...
Abstract
Ämnesord
Stäng
- 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.
Ämnesord
- NATURVETENSKAP -- Matematik -- Beräkningsmatematik (hsv//swe)
- NATURAL SCIENCES -- Mathematics -- Computational Mathematics (hsv//eng)
Nyckelord
- Logic-based Benders decomposition
- Acceleration technique
- Cut strengthening
- Mixed-integer programming
- Constraint programming
- Avionics scheduling
Publikations- och innehållstyp
- ref (ämneskategori)
- art (ämneskategori)
Hitta via bibliotek
Till lärosätets databas