.png){kind=icon}
返回
A new approximation algorithm for unrelated parallel machine scheduling with release dates
.png){kind=icon}
PRE
AI
DOI：10.1007/s10479-019-03346-4.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
In the current study, an unrelated parallel machine scheduling problem with release dates is considered, which is to obtain a job assignment with minimal sum of weighted completion times. Although this problem is NP-hard in the strong sense, which renders the optimality seeking a formidable task within polynomial time, a 4-approximation algorithm based on the constant worst-case bound is devised and proved in comparison with the existing 16/3-approximation (Hall et al. in Math Oper Res 22(3):513-544, 1997). In the newly proposed algorithm, the original scheduling problem is divided into several sub-problems based on release dates. For each sub-problem, a convex quadratic integer programming model is constructed in accordance with the specific problem structure. Then a semi-definite programming approach is implemented to produce a lower bound via the semi-definite relaxation of each sub-problem. Furthermore, by considering the binary constraint, a branch and bound based method and a local search strategy are applied separately to locate the optimal solution of each sub-problem. Then the solution of the original scheduling problem is derived by integrating the outcomes of the sub-problems via the proposed approximation algorithm. In the numerical analysis, it is discovered that the proposed methods could always obtain a scheduling result within 1% of the optimal solution. And an asymptotic trend could be observed where the quality of solutions improves even further as the scale of the scheduling problem increases.
Keyword:
Unrelated parallel machine scheduling
Release dates
Semi-definite programming
Approximation algorithm
Branch and bound
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
4.5
论文数:
8.1K
被引数:
2.1W
机构
引用论文
.png){kind=icon}
Apocalyptic belief and prophecy: constructing political legitimacy during the Yuan-Ming transition
PREAI
分享收藏An iterated greedy algorithm for the large-scale unrelated parallel machines scheduling problem
PREAI
分享收藏
分享收藏
查看更多内容