首页 | 本学科首页   官方微博 | 高级检索  
     

两种准在线装箱算法
引用本文:陈建新,杨宇航,龚玲,曾鹏.两种准在线装箱算法[J].计算机工程,2006,32(13):4-5,17.
作者姓名:陈建新  杨宇航  龚玲  曾鹏
作者单位:1. 上海交通大学电子工程系,上海,200030
2. 南京邮电学院计算机科学技术系,南京,210003
摘    要:在装箱问题中,下次填充法(NF)由于其在线特性,而被广泛应用。然而这种算法由于按照物件到达先后顺序来填充,资源利用率比较低。该文根据计算机通信网络中的实际应用,在NF算法基础上添加了置换功能,提出两种新的算法:最后物件置换算法和每个物件置换算法。由于物件被置换后,可能会被填充到后续箱内,因此称之为准在线算法。通过平均分析发现,这两种算法性能比NF算法有较大提高,类似于智能NF算法的性能。

关 键 词:准在线  装箱  性能比  置换
文章编号:1000-3428(2006)13-0004-02
收稿时间:2005-07-13
修稿时间:2005-07-13

Two Semi-online Algorithms for Bin Packing Problem
CHEN Jianxin,YANG Yuhang,GONG Ling,ZENG Peng.Two Semi-online Algorithms for Bin Packing Problem[J].Computer Engineering,2006,32(13):4-5,17.
Authors:CHEN Jianxin  YANG Yuhang  GONG Ling  ZENG Peng
Affiliation:1. Department of Electronics Engineering, Shanghai Jiaotong University, Shanghai 200030; 2. Department of Computer Science Technology, Nanjing University of Posts & Telecommunication, Nanjing 210003
Abstract:In online bin packing problem,for the online property of next fit(NF) algorithm,it is used widely.However,NF works according to the item arrival sequence,the resource utility ratio is low.This paper based on the computer communication network,adds repacking scheme to NF algorithm,and presents two new algorithms: the last item repacking and each item repacking.Because of being repacked,some items would be packed into the subsequent bin,hence they are called semi-online algorithms.By means of average-case analysis,the paper finds they perform much better than NF,and almost same to the smart next fit algorithm.
Keywords:Semi-online  Bin-packing  Performance ratio  Repacking
本文献已被 CNKI 维普 万方数据 等数据库收录!
点击此处可从《计算机工程》浏览原始摘要信息
点击此处可从《计算机工程》下载全文
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号