Heuristics for Vector Bin Packing
Heuristics for Vector Bin Packing
复制标题
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
R. Panigrahy;Kunal Talwar;Lincoln K. Uyeda;Udi Wieder
中科院分区：
文献类型：
--
作者：
R. Panigrahy;Kunal Talwar;Lincoln K. Uyeda;Udi Wieder
受虚拟机布局问题的启发，我们研究了向量装箱问题，其中我们需要包装n个项目表示的d维向量，到尽可能少的箱子大小为1。我们系统地研究的第一次拟合递减（FFD）算法，已提出了这个问题的变种。受FFD类型算法的坏实例的启发，我们提出了新的几何算法，对于合理的n和d值，它几乎和FFD一样快。我们报告基于FFD的经验评估，以及新的大家庭的分布。我们确定了哪些FFD变体在大多数情况下效果最好，并表明我们的新算法通常优于基于FFD的算法，有时可以减少多达10%的箱数。此外，在我们能够计算最优解的所有情况下，我们发现我们的新算法在最优的几个百分点之内。我们的结论是，这些新的化学品是一个很好的替代FFD为基础的化学品，并在实践中使用的主要候选人。
Inspired by virtual machine placement problems, we study heuristics for the Vector Bin Packing problem, where we are required to pack n items represented by d-dimensional vectors, into as few bins of size 1 each as possible. We systematically study variants of the First Fit Decreasing (FFD) algorithm that have been proposed for this problem. Inspired by bad instances for FFD-type algorithms, we propose new geometric heuristics that run nearly as fast as FFD for reasonable values of n and d. We report on empirical evaluations of the FFD-based, as well as the new heuristics on large families of distributions. We identify which FFD variants work best in most cases and show that our new heuristics usually outperform FFD-based heuristics and can sometimes reduce the number of bins used by up to ten percent. Further, in all cases where we were able to compute the optimal solution we found our new heuristics within few percent of optimal. We conclude that these new heuristics are an excellent alternative to FFD-based heuristics and are prime candidates to be used in practice.