物品大小不超过1/2的一维在线装箱模型研究

Research on Online Bin Packing Model with Item Size No More than 1/2

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

In this paper we study the online bin packing for items size no more than1/2 .Based on item size partition a new online bin pacing algorithm is purposed. In our setting, the items are released over list such that the decision on packing each item of list into some open bin must be made on its arrival and future informationis unknown. During the processing of our algorithm all items are divided into five categories and bins are also divided into seven types. Each type bins can load given category items exclusively. At any time at most seven bins are open. Meanwhile we need not extra space store the items temporarily and every item can not be repacked once it has been put into some bin. Every bin can not be reopened once it is closed. This decision result meets the actual cires better. Lastly we arrive at the conclusion that our algorithm can achieve an ACR of 1.4236. At the same time we give a new lower bound 1.4231 leaving a gap with 0.0005 on our model.