| 尺寸可变的装箱问题的近似算法的研究 |
| |
| 引用本文： | 张玉栋,蔡静,郝自军,何尚录. 尺寸可变的装箱问题的近似算法的研究[J]. 兰州交通大学学报, 2007, 26(1): 146-148 |
| |
| 作者姓名： | 张玉栋 蔡静 郝自军 何尚录 |
| |
| 作者单位： | 兰州交通大学,数理与软件工程学院,甘肃,兰州,730070;贵州大学,理学院,贵州,贵阳,550000 |
| |
| 摘 要： | 给定物品系列,要求将所有物品装入到不同类型的箱子中,以实现从第1个箱子到最后1个箱子被使用的箱子的总尺寸最小化.用最坏情况绝对性能研究在线算法,给出了一种最坏情况绝对性能比是3的近似算法.作为这种算法的应用,给出了一种脱线算法,其最坏情况绝对性能比是2.
|
| 关 键 词： | 尺寸可变的装箱问题 近似算法 最坏情况绝对性能分析 |
| 文章编号： | 1001-4373(2007)01-0146-03 |
| 修稿时间： | 2006-09-16 |
Approximation Algorithms for Variable-sized Bin Packing |
| |
| Zhang Yudong,Cai Jing,Hao Zijun,He Shanglu. Approximation Algorithms for Variable-sized Bin Packing[J]. Journal of Lanzhou Jiaotong University, 2007, 26(1): 146-148 |
| |
| Authors: | Zhang Yudong Cai Jing Hao Zijun He Shanglu |
| |
| Abstract: | For a list of given items,how to pack them into a list of variable-sized bins in sequence so as to minimize the total size of bins ranging from the first one to the last one.The on-line algorithms is studied in terms of the absolute worst-case ratio.A simple on-line algorithm is shown to have an absolute worst-case ratio of 3.Also,we present a very simple off-line algorithm by applying the algorithm to a sorted list of items.It proves that the absolute worst-case ratio is 2. |
| |
| Keywords: | variable-sized bin packing on-line approximation algorithm absolute worst-case performance analysis |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
