.png){kind=icon}
返回
Approximation Algorithms on a Scheduling Problem with Connectivity Constraints
.png){kind=icon}
PRE
AI
DOI：10.1142/s0129054126490043.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
我们提出一个具有连通性约束的新型调度问题。该问题定义了一个连通图G = (V,E)，其中每条边e∈E关联一个处理时间t(e)和成本c(e)，即t,c : E → ℝ⁺ ∪ {0}，其中ℝ⁺是正实数集合。目标是在G中选择一条路径P以建立两个给定顶点之间的连通性，并进一步将对应边在m台平行机器上进行调度，以最小化完工时间和总成本之和。该问题是强NP难的，结合了图论和平行机调度元素。本文关注均匀平行机环境，为此我们开发了近似算法并提供了最坏情况分析。我们的结果为组合优化的调度理论做出贡献，并为资源约束下的网络恢复提供了新的见解。
Keyword:
Scheduling
connectivity constraints
approximation algorithm
uniform machines
期刊
I
IF:
0.6
论文数:
46
被引数:
0
机构
引用论文
暂无论文信息