Multidimensional Bin Packing and Other Related Problems : A Survey ∗
Multidimensional Bin Packing and Other Related Problems : A Survey ∗
复制标题
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
H. Christensen;A. Khan;S. Pokutta;P. Tetali
中科院分区：
文献类型：
--
作者：
H. Christensen;A. Khan;S. Pokutta;P. Tetali
装箱问题是组合优化中的一个重要问题。在经典的装箱问题中，我们给出了一个（0，1）中的真实的数字列表，目标是将它们放置在最小数量的箱子中，以便没有箱子容纳总和超过1的数字。该问题在实际中非常重要，在调度、路由和资源分配问题中有许多应用。理论上，这个问题与差异理论、迭代方法、熵舍入有着丰富的联系，并导致了几种算法技术的发展。在这篇综述中，我们考虑了装箱问题的几个经典推广，如几何装箱，向量装箱和各种其他相关问题。在二维几何装箱问题中，给定一个矩形物品的集合，将其装入最小数量的单位尺寸的正方形箱子中。这种变体在切割库存，车辆装载，托盘包装，内存分配和其他几个物流和机器人相关问题中有很多应用。在d维向量箱包装中，每个项目是需要包装到单位向量箱中的d维向量。该问题在资源受限调度和云计算中的虚拟机布局中具有重要意义。我们还考虑了其他几个概括的装箱，如几何背包，带包装和其他相关问题，如向量调度，向量覆盖等。我们调查这些问题的算法在离线和在线设置，也提到几个重要的特殊情况下的结果。我们简要地提到了这些算法的设计和分析中使用的相关技术，并调查了一些在实践中工作良好的算法。最后，我们总结了一系列悬而未决的问题。这项研究得到了NSF EAGER奖赠款CCF-1415496和CCF-1415498的支持。电子邮件：hic@cc.gatech.edu瑞士智能研究所（IDSIA），意大利科技大学（SUPSI），意大利科技大学（USI），瑞士。电子邮件：arindam.khan@supsi. ch。这项工作的一部分是在作者还是格鲁吉亚理工学院学生时完成的。§美国亚特兰大格鲁吉亚理工学院。电子邮件：塞巴斯蒂安. isye.gatech.edu格鲁吉亚理工学院，亚特兰大，美国。电子邮件地址：tetali@math.gatech.edu
The bin packing problem is a well-studied problem in combinatorial optimization. In the classical bin packing problem, we are given a list of real numbers in (0, 1] and the goal is to place them in a minimum number of bins so that no bin holds numbers summing to more than 1. The problem is extremely important in practice and finds numerous applications in scheduling, routing and resource allocation problems. Theoretically the problem has rich connections with discrepancy theory, iterative methods, entropy rounding and has led to the development of several algorithmic techniques. In this survey we consider several classical generalizations of bin packing problem such as geometric bin packing, vector bin packing and various other related problems. In two-dimensional geometric bin packing, we are given a collection of rectangular items to be packed into a minimum number of unit size square bins. This variant has a lot of applications in cutting stock, vehicle loading, pallet packing, memory allocation and several other logistics and robotics related problems. In d-dimensional vector bin packing, each item is a d-dimensional vector that needs to be packed into unit vector bins. This problem is of great significance in resource constrained scheduling and in recent virtual machine placement in cloud computing. We also consider several other generalizations of bin packing such as geometric knapsack, strip packing and other related problems such as vector scheduling, vector covering etc. We survey algorithms for these problems in offline and online setting, and also mention results for several important special cases. We briefly mention related techniques used in the design and analysis of these algorithms and also survey some heuristics that work well in practice. In the end we conclude with a list of open problems. ∗This research was supported by NSF EAGER award grants CCF-1415496 and CCF-1415498 †Georgia Institute of Technology, Atlanta, USA. Email: hic@cc.gatech.edu ‡Istituto Dalle Molle di studi sull’Intelligenza Artificiale (IDSIA), Scuola universitaria professionale della Svizzera italiana (SUPSI), Universit della Svizzera italiana (USI), Switzerland. email: arindam.khan@supsi.ch. Supported by SNF Grant 200021 159697/1. A part of this work was done when the author was a student at Georgia Institute of Technology. §Georgia Institute of Technology, Atlanta, USA. Email: sebastian.pokutta@isye.gatech.edu ¶Georgia Institute of Technology, Atlanta, USA. Email: tetali@math.gatech.edu