张明会^1,2，韩鑫¹

1. 大连理工大学软件学院软件工程系, 大连 116620;2.大连东软信息学院软件工程系,大连 116023

出版日期:2017-03-25发布日期:2017-04-28

Research on Online Bin Packing Model with Item Size\\ No More than $\frac{\bf 1}{\bf 2}$

ZHANG Minghui ^1,2 ,HAN Xin¹

1.School of Software Technology, Dalian University of Technology, Dalian 116620; 2. Software Engineering Department, Dalian Neusoft University of Information, Dalian 116023)

Online:2017-03-25Published:2017-04-28







摘要
图/表
参考文献
相关文章
编辑推荐
-->Metrics
本文评论

研究主要针对所有装入物品大小上限为$\frac{1}{2}$时的一维装箱问题模型展开,根据物品尺寸大小划分的思想,提出一种新的一维在线装箱算法.本模型中,物品在线到来,对即将到来的物品信息及物品数量未知,算法执行过程中,首先根据物品尺寸大小将物品划分成7大类,再根据欲先设定的packing规则,将对应类物品放入对应类型箱子中,任何时刻,算法最多打开7个箱子.算法设计过程中,不再需要额外的空间存储物品,物品一旦装入箱子不允许取出重装,箱子关闭后不允许再打开装其他物品.最后,通过详细的分析计算,验证出本算法能获得1.4236的渐近竞争比.同时通过实例构建得出问题新的下界为1.4231,将上下界之间的缝隙缩小至0.0005.

分享此文:

()

No related articles found!

-->

PDF全文下载地址:

http://sysmath.com/jweb_xtkxysx/CN/article/downloadArticleFile.do?attachType=PDF&id=13102