求解online packing problem的F-B绝对近似算法

• 作者: 李松斌 黄海
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: 在线装箱问题 预留箱体 绝对近似比 配对绑定
• 年，卷（期）: 2017,（11）
• 所属期刊栏目: 理论与研发
• 页码范围: 73-78
• 页数: 6页
• 分类号: TP301.6
• 字数: 8107字
• 语种: 中文
• DOI: 10.3778/j.issn.1002-8331.1701-0001

摘要

FF算法由于其在线特性在处理在线装箱问题得到广泛使用,但它无法预测后面达到物品造成装箱率低,提出一种预留一定比例的各类未装满箱体的装箱算法.首先对未装满箱体分类并给出相应的数据结构,接着设计一种绑定配对策略来预留各类未装满箱体数目,并引入间隔函数控制新箱体的启用,最后基于FF算法结合预留策略对物品进行装箱来保证装箱的绝对近似比.提出了一种预留绑定配对策略为后续输入物品提供预测空间,特别的是F-B算法能得到5/3的绝对近似比.

作者信息

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