.png){kind=icon}
返回
Logic-based Benders decomposition with a partial assignment acceleration technique for avionics scheduling
.png){kind=icon}
OA
AI
DOI：10.1016/j.cor.2022.105916.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
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.
Keyword:
Logic-basedBendersdecomposition
Accelerationtechnique
Cutstrengthening
Mixed-integerprogramming
Constraintprogramming
Avionicsscheduling
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
C
IF:
4.3
论文数:
6.5K
被引数:
1.8W
机构
引用论文
分享收藏Treatment of osteoporosis with human parathyroid peptide and observations on effect of sodium fluoride..png)
BMJ
OAAI
BMJIF0
OAAI分享收藏MIPLIB 2017: data-driven compilation of the 6th mixed-integer programming libraryMIPLIB 2017: 第6个混合整数编程库的数据驱动编译OAAI
OAAI分享收藏A Benders decomposition-based framework for solving quay crane scheduling problems基于Benders分解的码头起重机调度问题求解框架OAAI
OAAI分享收藏分享收藏
查看更多内容