.png){kind=icon}
返回
On Online Approximation Algorithms for Two-Stage Bins
.png){kind=icon}
PRE
AI
DOI：10.1007/978-981-95-0215-8_6.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
受云计算应用启发，本文研究了一个结合并行两阶段流水车间调度问题与装箱问题的混合问题，即两阶段装箱问题。给定一系列两阶段作业，该问题旨在将它们装入最少数量的两阶段流水车间中，使得每个流水车间的完工时间不超过给定的时间限制。据我们所知，该问题此前尚未被研究过。认识到其NP难度，我们探讨了多种近似算法。首先，我们提出了两种基于广为人知的首次适应和下次适应策略的在线算法，分别实现了绝对近似比4（下界为3.166）和紧渐近近似比4。随后，我们介绍了一种算法，该算法对每个流水车间应用约翰逊顺序，并使用首次适应策略将到达的作业分配给流水车间，该算法被证明具有渐近近似比3.061（下界为2.66）。此外，我们还证明，在流水车间中应用约翰逊顺序无法在近似比方面改进下次适应策略。
Keyword:
Parallel two-stage flowshops
Bin packing
Approximation algorithm
First-fit
Next-fit
Cloud computing
期刊
C
IF:
0
论文数:
24
被引数:
0
机构
引用论文
.png){kind=icon}
查看更多内容