.png){kind=icon}
返回
An iterative exact algorithm for the weighted fair sequences problem
.png){kind=icon}
OA
AI
DOI：10.1016/j.cor.2022.106017.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
In this work, we present a new iterative exact solution algorithm for a recently introduced NP-hard sequencing problem. In the problem we are given an upper bound on the allowed solution sequence length and a list of symbols. For each symbol, there is a positive weight and a number, which gives the minimum amount of times the symbol has to occur in a feasible solution sequence. The goal is to find a feasible sequence, which minimizes the maximum weight-distance product, which is calculated for each consecutive appearance of each symbol in the sequence, including the last and first appearance in the sequence, i.e., the sequence is considered to be circular for the calculation of the objective function. Our proposed solution algorithm is based on a new mixed-integer programming model for the problem with a fixed sequence length. We also present various enhancements for our algorithm. We conduct a computational study on the instances from literature to assess the efficiency of our newly proposed solution approach.Our approach solves 404 of 440 instances to optimality within the given time limit, most of them within five minutes. The previous best existing solution approach for the problem only solves 229 of these instances and its exactness depends on an unproven conjecture. Moreover, our approach is up to two orders of magnitude faster compared to this best existing solution approach.
Keyword:
Scheduling problem
Mixed-integer programming
Sequencing problem
Iterative algorithm
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
C
IF:
4.3
论文数:
6.5K
被引数:
1.8W
机构
引用论文
.png){kind=icon}
分享收藏Lasmiditan for the treatment of acute migraine: a review and potential role in clinical practiceOAAI
OAAI分享收藏
查看更多内容