...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >Two-dimensional strip packing with unloading constraints?
【24h】

Two-dimensional strip packing with unloading constraints?

机译：带卸载约束的二维带状包装？

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

摘要

In this paper we present approximation algorithms for the two-dimensional strip packing problem with unloading constraints. In this problem, we are given a strip S of width 1 and unbounded height, and n items of C different classes, each item ai with height h(ai), width w(ai) and class c(ai). As in the strip packing problem, we have to pack all items, minimizing the height used, but now we have the additional constraint that items of higher classes cannot block the way out of items of lower classes. For the case in which horizontal and vertical movements for removing the items are allowed, we design an algorithm whose asymptotic performance bound is 3. For the case in which only vertical movements are allowed, we design a bin packing based algorithm with an asymptotic approximation ratio of 5.745. Moreover, we also design approximation algorithms for restricted cases of both versions of the problem. These problems have practical applications in dealing with routing problems with loading/unloading constraints.
机译：在本文中，我们提出了带有卸载约束的二维带钢包装问题的近似算法。在这个问题中，我们给定条带S的宽度1和无限制的高度，以及n个C类不同的项，每个项ai具有高度h（ai），宽度w（ai）和类c（ai）。就像带包装问题一样，我们必须打包所有物品，以最大程度地减少使用的高度，但是现在我们有了附加的约束，即高级物品不能阻挡走出低级物品的道路。对于允许移除物品的水平和垂直运动的情况，我们设计了一种渐近性能界限为3的算法。对于仅允许垂直运动的情况，我们设计了一种基于渐近逼近比的基于装箱算法5.745。此外，我们还针对问题的两个版本的受限情况设计了近似算法。这些问题在处理带有加载/卸载约束的路由问题中具有实际应用。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号