求解online packing problem的F-B绝对近似算法  被引量:1

F-B absolute algorithm for packing problem

在线阅读下载全文

作  者:黄海[1] 李松斌[2,3] HUANG Hai;LI Songbin(College of Information Engineering, Putian University, Putian, Fujian 351100, China;Haikou Laboratory, Institute of Acoustics, Chinese Academy of Sciences, Haikou 570105, China;National Network New Media Engineering Research Center, Institute of Acoustics, Chinese Academy of Sciences, Beijing 100190, China)

机构地区:[1]莆田学院信息工程学院,福建莆田351100 [2]中国科学院声学研究所南海研究站,海口570105 [3]中国科学院声学研究所国家网络新媒体工程技术研究中心,北京100190

出  处:《计算机工程与应用》2017年第11期73-78,共6页Computer Engineering and Applications

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

摘  要:FF算法由于其在线特性在处理在线装箱问题得到广泛使用,但它无法预测后面达到物品造成装箱率低,提出一种预留一定比例的各类未装满箱体的装箱算法。首先对未装满箱体分类并给出相应的数据结构,接着设计一种绑定配对策略来预留各类未装满箱体数目,并引入间隔函数控制新箱体的启用,最后基于FF算法结合预留策略对物品进行装箱来保证装箱的绝对近似比。提出了一种预留绑定配对策略为后续输入物品提供预测空间,特别的是F-B算法能得到5/3的绝对近似比。In online packing problem,FF algorithm is widely used for the online property.But it can not predict the result of the latter to achieve the packing rate is low.A new algorithm is proposed for online packing problem with absolute ratio.First,unfilled boxes are classified and given the corresponding data structure.Then,a binding pairing strategy is designed to reserve the number of unclaimed boxes and introduce the interval function to control the opening of the new box.Finally,an approximation algorithm based on the FF algorithm combined with the reservation strategy is proposed.In particular,it proposes a reservation binding pairing strategy to provide predictive space for subsequent input items,and the F-B algorithm can obtain5/3approximation ratio.

关 键 词:在线装箱问题 预留箱体 绝对近似比 配对绑定 

分 类 号:TP301.6[自动化与计算机技术—计算机系统结构]

 

参考文献:

正在载入数据...

 

二级参考文献:

正在载入数据...

 

耦合文献:

正在载入数据...

 

引证文献:

正在载入数据...

 

二级引证文献:

正在载入数据...

 

同被引文献:

正在载入数据...

 

相关期刊文献:

正在载入数据...

相关的主题
相关的作者对象
相关的机构对象