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

作     者：黄海 李松斌 HUANG Hai;LI Songbin

作者机构：莆田学院信息工程学院福建莆田351100 中国科学院声学研究所南海研究站海口570105 中国科学院声学研究所国家网络新媒体工程技术研究中心北京100190 

基　　金：国家自然科学基金(No.61303249) 福建省教育厅A类科技项目(No.JA15443) 福建省莆田市科技项目(No.2014G16) 

出 版 物：《计算机工程与应用》 (Computer Engineering and Applications)

年 卷 期：2017年第53卷第11期

页      码：73-78页

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

主 题 词：在线装箱问题 预留箱体 绝对近似比 配对绑定 

学科分类：08[工学] 081202[081202] 0812[工学-测绘类] 

D　O　I：10.3778/j.issn.1002-8331.1701-0001

馆 藏 号：203232532...