...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >Lower and upper bounds for the Bin Packing Problem with Fragile Objects
【24h】

Lower and upper bounds for the Bin Packing Problem with Fragile Objects

机译：易碎物品箱装箱问题的上限和下限

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

摘要

We are given a set of items, each characterized by a weight and a fragility, and a large number of uncapacitated bins. Our aim is to find the minimum number of bins needed to pack all items, in such a way that in each bin the sum of the item weights is less than or equal to the smallest fragility of an item in the bin. The problem is known in the literature as the Bin Packing Problem with Fragile Objects, and appears in the telecommunication field, when one has to assign cellular calls to available channels by ensuring that the total noise in a channel does not exceed the noise acceptance limit of a call. We propose several techniques to compute lower and upper bounds for this problem. For what concerns lower bounds, we present combinatorial techniques with guaranteed worst case and a more complex bound based on a column generation algorithm. We also present a technique to compute, in a fast heuristic way, dual information that is used to strengthen the convergence of the column generation. For what concerns upper bounds, we present a large set of constructive heuristics followed by a Variable Neighborhood Search algorithm. Our heuristic techniques are aimed at both computing upper bounds and strengthening the behavior of the lower bounds in a matheuristic fashion. Extensive computational tests show the effectiveness of the proposed algorithms.
机译：我们给了我们一组物品，每个物品都有重量和易碎性，还有大量无能力的垃圾箱。我们的目标是找到包装所有物品所需的最小箱数，以使每个箱中物品重量的总和小于或等于该箱中物品的最小脆性。该问题在文献中被称为“带有易碎物体的装箱问题”，并且出现在电信领域，当人们必须通过确保某个信道中的总噪声不超过噪声接收限制时，将蜂窝呼叫分配给可用信道时，就会出现该问题。一个电话。我们提出了几种技术来计算此问题的上下限。对于涉及下限的问题，我们提出了基于列生成算法的组合技术，这些组合技术可以保证最坏的情况和更复杂的边界。我们还提出了一种以快速启发式方式计算双重信息的技术，该技术用于增强列生成的收敛性。对于涉及上限的问题，我们提出了一系列建设性的启发式方法，然后提出了可变邻域搜索算法。我们的启发式技术旨在以数学方式同时计算上限和增强下限的行为。大量的计算测试证明了所提出算法的有效性。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号