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

• 作者: 李松斌 黄海
• 来源期刊: 计算机科学
• 学科: 工学
• 关键词: u-分组 二维装箱 近似算法 NP难度 启发式
• 年，卷（期）: 2017,（5）
• 所属期刊栏目: 人工智能
• 页码范围: 290-293,303
• 页数: 5页
• 分类号: TP308|TP301.6
• 字数: 7202字
• 语种: 中文
• DOI: 10.11896/j.issn.1002-137X.2017.05.053

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	黄海	莆田学院信息工程学院	13	13	3.0	3.0