| 一类带约束的装箱问题的在线算法 |
| |
| 引用本文： | 肖教燎,毛燕玲,余国松. 一类带约束的装箱问题的在线算法[J]. 南昌大学学报(理科版), 2006, 30(6): 522-524 |
| |
| 作者姓名： | 肖教燎 毛燕玲 余国松 |
| |
| 作者单位： | 南昌大学,管理科学与工程系,江西,南昌,330031;南昌大学,管理科学与工程系,江西,南昌,330031;南昌大学,管理科学与工程系,江西,南昌,330031 |
| |
| 基金项目： | 南昌大学校科研和教改项目 |
| |
| 摘 要： | A型装箱问题（ASBP）是BP（Backing Problem）的一种变型问题，与经典的BP问题不同的是，在ASBP中物品有两个参数：高度和半径。在装箱过程中，除了要求箱子中所有物品的高度和不大于1之外，还要求后到达的物品放在先到达的物品之上且上层物品的半径不超过下层物品的半径。分析了无穷数目的不同半径和有限数目的不同半径两种情形。对于无穷数目的不同半径的情形，我们证明了NF（Next Fit）、FF（First Fit）、BF（Best Fit）、RBF（Radius Best Fit）和AF（Any Fit）算法的渐近最坏比为无穷大；对于有限数目的不同半径的情形，我们得到了FF、RBF算法的精确渐近最坏界。
|
| 关 键 词： | 组合优化 装箱问题 算法分析 |
| 文章编号： | 1006-0464（2006）06-0522-03 |
| 收稿时间： | 2005-12-20 |
| 修稿时间： | 2005-12-20 |
On-line Algorithms for the Constrained Bin Packing Problem |
| |
| XIAO Jiao-liao,MAO Yan-ling,YU Guo-song. On-line Algorithms for the Constrained Bin Packing Problem[J]. Journal of Nanchang University(Natural Science), 2006, 30(6): 522-524 |
| |
| Authors: | XIAO Jiao-liao MAO Yan-ling YU Guo-song |
| |
| Affiliation: | Department of Management Science and Engineering, Nanchang University, Nanchang 330031, China |
| |
| Abstract: | The A-shaped bin packing problem(ASBP) is a variant of the classical on-dimensional bin packing problem,in which each item has two parameters:height and diameter.In ASBP,the items must be packed into an A-shape in each bin,i.e.an item's radius should be equal to or not less than that of the item above it.The paper It analysises the cases that the number of the different radii is infinite and the number of the different radii is finite.It proves that the asymptotic worst-case ratios of NF,FF,BF,RBF and AF are infinite if the number of the different radii is infinite.It also gives the exact asymptotic worst bounds of FF and RBF if the number of the different radii is finite. |
| |
| Keywords: | combinational optimization bin packing problem algorithms analysis |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
