%0 Journal Article
%T On a Constrained Bin Packing Problem with Start-Up Space<br>受启动空间约束的装箱问题
%A GU Xiao-dong
%A XU Yin-long
%A CHEN Guo-liang
%A HUANG Liu-sheng
%A <br>顾晓东
%A 许胤龙
%A 陈国良
%A 黄刘生
%J 软件学报
%D 2002
%I 
%X A constrained bin packing problem with start-up space (SBPP) is proposed in this paper, in which an additional start-up space is needed if different items are put into a same bin. The problem has many applications such as job allocation, multiprocessor scheduling and real-world packing. A linear offline approximation algorithm C-NF is presented to solve the SBPP problem. It is proved that the C-NF algorithm has an asymptotic worst-case performance ratio of 2, which is independent of the size of start-up space.And the experimental average-case performances of C-NF are given.Also,the online property of SBPP is studied.It is pointed out that most of the classic online algorithms cannot offer definite worst-case performance ratios when applied on SBPP.And an online algorithm is proposed with a finite asymptotic worst-case performance ratio for any start-up space.
%K bin packing problem
%K combinatorial optimization
%K approximation algorithm
%K asymptotic worst-case performance ratio
%K average-case performance ratio<br>装箱问题
%K 组合优化
%K 近似算法
%K 最坏情况渐近性能比
%K 平均性能比
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=7735F413D429542E610B3D6AC0D5EC59&aid=8FA0F95AA2DD011C&yid=C3ACC247184A22C1&vid=FC0714F8D2EB605D&iid=38B194292C032A66&sid=A22854835F81B3F8&eid=21D8CE17EE5EE354&journal_id=1000-9825&journal_name=软件学报&referenced_num=1&reference_num=8