| Bounded space algorithms for variant of variable-sized bin packing |
| |
| 作者姓名： | LI Bo ZHAO Dong-feng SHI Bing-xin SHEN Bin |
| |
| 作者单位： | [1]School of Information Science and Engineenng, Yunnan University. Kunming 650091, P.R. China [2]Department of Electronics and Information Engineenng, Huazhong University of Science and Technology,Wuhan 430074, P.R. China |
| |
| 摘 要： | Given a list of items and a sequence of variable-sized bins arriving one by one, it is NP-hard to pack the items into the bin list with a goal to minimize the total size of bins from the earliest one to the last used. In this paper a set of approximation algorithms is presented for cases in which the ability to preview at most k（〉=2） arriving bins is given. With the essential assumption that all bin sizes are not less than the largest item size, analytical results show the asymptotic worst case ratios of all k-bounded space and offiine algorithms are 2. Based on experiments by applying algorithms to instances in which item sizes and bin sizes are drawn independently from the continuous uniform distribution respectively in the interval 0,u] and u,l ], averagecase experimental results show that, with fixed k, algorithms with the Best Fit packing（closing） rule are statistically better than those with the First Fit packing（closing） rule.
|
| 关 键 词： | 有限空间 变量 离线法 规划论 渐进线 |
| 文章编号： | 1671-8224（2005）03-0164-06 |
| 收稿时间： | 2005-06-26 |
Bounded space algorithms for variant of variable-sized bin packing |
| |
| LI Bo ZHAO Dong-feng SHI Bing-xin SHEN Bin.Bounded space algorithms for variant of variable-sized bin packing[J].Journal of Chongqing University,2005,4(3):164-169. |
| |
| Authors: | LI;Bo;ZHAO;Dong-feng;SHI;Bing-xin;SHEN;Bin |
| |
| Abstract: | Given a list of items and a sequence of variable-sized bins arriving one by one, it is NP-hard to pack the items into the bin list with a goal to minimize the total size of bins from the earliest one to the last used. In this paper a set of approximation algorithms is presented for cases in which the ability to preview at most k(>=2) arriving bins is given. With the essential assumption that all bin sizes are not less than the largest item size, analytical results show the asymptotic worst case ratios of all k-bounded space and offline algorithms are 2. Based on experiments by applying algorithms to instances in which item sizes and bin sizes are drawn independently from the continuous uniform distribution respectively in the interval 0,u] and u,1], average-case experimental results show that, with fixed k, algorithms with the Best Fit packing(closing) rule are statistically better than those with the First Fit packing(closing) rule. |
| |
| Keywords: | variable-sized bin packing bounded space algorithms offline algorithms worst case performance average case performance |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《重庆大学学报(英文版)》浏览原始摘要信息 |
| 点击此处可从《重庆大学学报(英文版)》下载免费的PDF全文 |
