...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>RAIRO Operation Research >ONLINE LIB PROBLEMS: HEURISTICS FOR BIN COVERING AND LOWER BOUNDS FOR BIN PACKING
【24h】

ONLINE LIB PROBLEMS: HEURISTICS FOR BIN COVERING AND LOWER BOUNDS FOR BIN PACKING

机译：在线库问题：料箱盖的启发式方法和料箱包装的下限

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

摘要

We consider the NP Hard problems of online Bin Covering and Packing while requiring that larger (or longer, in the one dimensional case) items be placed at the bottom of the bins, below smaller (or shorter) items — we call such a version, the LIB version of problems. Bin sizes can be uniform or variable. We look at computational studies for both the Best Fit and Harmonic Fit algorithms for uniform sized bin covering. The Best Fit heuristic for this version of the problem is introduced here. The approximation ratios obtained were well within the theoretical upper bounds. For variable sized bin covering, a more thorough analysis revealed definite trends in the maximum and average approximation ratios. Finally, we prove that for online LIB bin packing with uniform size bins, no heuristic can guarantee an approximation ratio better than 1.76 under the online model considered.
机译：我们考虑了在线垃圾箱覆盖和包装的NP Hard问题，同时要求将较大（或更长，在一维情况下）的物品放在垃圾箱的底部，放在较小（或更短）物品的下面-我们称之为此类版本， LIB版本的问题。料仓大小可以是统一的或可变的。我们着眼于针对均匀大小的箱盖的最佳拟合和谐波拟​​合算法的计算研究。这里介绍了针对此问题版本的最佳拟合启发式方法。所获得的近似比率完全在理论上限之内。对于可变大小的垃圾箱覆盖物，更彻底的分析显示出最大和平均近似比的明确趋势。最后，我们证明了对于具有统一大小的垃圾箱的在线LIB垃圾箱包装，在考虑的在线模型下，没有启发法可以保证逼近率大于1.76。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号