• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>IEEE Transactions on Parallel and Distributed Systems >On Fault-Tolerant Bin Packing for Online Resource Allocation
【24h】

On Fault-Tolerant Bin Packing for Online Resource Allocation

机译：在线资源分配的容错装箱

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We study an online fault-tolerant bin packing problem that models reliable resource allocation. In this problem, each item is replicated and has $f+1$f+1 replicas including one primary and $f$f standbys. The packing of items is required to tolerate up to $f$f faulty bins, i.e., to guarantee that at least one correct replica of each item is available regardless of which $f$f bins turn to be faulty. Any feasible packing algorithm must satisfy an exclusion constraint and a space constraint. The exclusion constraint is generalized from the fault-tolerance requirement and the space constraint comes from the capacity planning. The target of bin packing is to minimize the number of bins used. We first derive a lower bound on the number of bins needed by any feasible packing algorithm. We then study three heuristic algorithms named mirroring, shifting and mixing under a particular setting where all items have the same size. The mirroring algorithm has a low utilization of the bin capacity. Compared with the mirroring algorithm, the shifting algorithm requires fewer bins. However, in online packing, the process of opening bins by the shifting algorithm is not smooth. It turns out that even for packing a few items, the shifting algorithm needs to quickly open a large number of bins. The mixing algorithm adopts a dual average strategy to gradually open new bins for incoming items. We prove that the mixing algorithm is feasible and show that it balances the number of bins used and the process of opening bins. Finally, to pack items with different sizes, we extend the mirroring algorithm by adopting the First-Fit strategy and extend both the shifting and mixing algorithms by involving the harmonic strategy. The asymptotic competitive ratios of the three extended algorithms are analyzed respectively.
机译：我们研究了在线容错箱包装问题，该问题对可靠的资源分配进行建模。在此问题中，每个项目都被复制并具有$ f + 1 $ f + 1个副本，其中包括一个主副本和$ f $ f个备用副本。需要包装物品以容忍最多$ f $ f个有问题的垃圾箱，即，保证每个物品至少有一个正确的副本可用，而与哪个$ f $ f个垃圾箱有问题无关。任何可行的打包算法都必须满足排除约束和空间约束。排除约束是从容错要求中得出的，而空间约束是从容量规划中得出的。垃圾箱包装的目标是最大程度地减少使用的垃圾箱数量。我们首先得出任何可行打包算法所需的箱数的下限。然后，我们研究在所有项目都具有相同大小的特定设置下的三种启发式算法，分别是镜像，移位和混合。镜像算法对存储柜容量的利用率较低。与镜像算法相比，移位算法需要较少的bin。但是，在在线包装中，通过移位算法打开垃圾箱的过程并不顺利。事实证明，即使要打包一些物品，移位算法也需要快速打开大量的箱柜。混合算法采用对偶平均策略来逐渐打开新的收件箱。我们证明了混合算法是可行的，并且表明它可以平衡使用的料仓数量和打开料仓的过程。最后，为了包装不同尺寸的物品，我们通过采用“先适应”策略扩展了镜像算法，并通过引入了谐波策略扩展了移位算法和混合算法。分别分析了三种扩展算法的渐近竞争率。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号