求解2-D Strip Packing问题的u-分组优化算法

摘要：

2-Dstrip packing问题指将带有价值的矩形物品装入长宽固定的箱子中,使其装入的物品价值最大.基于装箱的期望目标ε,提出一种新的分组构造函数,结合装箱矩形特点计算出最优分组参数u并对矩形进行分类,同时对不同类别的矩形引入相应的数据结构,最后对不同类别矩形基于箱子X轴的u等分点进行填充,使其装入的物品价值最大.文中的主要贡献在于:提出了一种有效的分组构造函数;计算出了对应的最优分组参数u;简化了不同类别箱体的数据结构以及相应的装箱算法;特别地,在期望目标ε、多项式时间复杂度和至少装入(1-ε) OPT价值物品的情况下,可将所需箱体宽度从1+ε减小到1,而高度保持不变.

关键词：u-分组、二维装箱、近似算法、NP难度、启发式

所属期刊栏目：44

分类号：TP308;TP301.6(计算技术、计算机技术)

资助基金：国家自然科学基金61303249;福建省教育厅A类科技项目JA15443;福建省莆田市科技项目2014G16

在线出版日期：2017-06-13（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：290-293,303