| 箱子是在线到达的带核元变尺寸装箱问题 |
| |
| 引用本文： | 帅天平,王海明.箱子是在线到达的带核元变尺寸装箱问题[J].应用数学学报,2004,27(3):423-429. |
| |
| 作者姓名： | 帅天平 王海明 |
| |
| 作者单位： | 1. 中国科学院数学与系统科学研究院,北京,100080
2. 兰州大学数学系,兰州,730000 |
| |
| 基金项目： | 国家自然科学基金(70221001，60373012号)资助项目. |
| |
| 摘 要： | 本文考虑了一类箱子在线到达的带核元变尺寸装箱问题．假定箱子的尺寸可以是不同的．箱子是在线到达的，仅当箱子到达后其尺寸才知道．给定一个带有核元的物件表，目标是要将表中元素装入到达的箱子中，使得所用的箱子总长最小．我们首先证明了该问题是强NP—Hard，其次分析了经典算法NF(D)和FF(D)的性能界，指出NF(D)和FF(D)算法的性能界可以任意大．最后我们给出了相应的修改算法MNF(D)和MFF(D)，证明了它们的性能界都是3，此界是紧的．
|
| 关 键 词： | 组合最优化 性能界 装箱算法 长度集合 NP-Hard 非核元 |
VARIABLE-SIZED BIN PACKING PROBLEMS WITH KERNELS WHERE BINS ARRIVE IN AN ON-LINE WAY |
| |
| SHUAI TIANPING,WANG Haiming.VARIABLE-SIZED BIN PACKING PROBLEMS WITH KERNELS WHERE BINS ARRIVE IN AN ON-LINE WAY[J].Acta Mathematicae Applicatae Sinica,2004,27(3):423-429. |
| |
| Authors: | SHUAI TIANPING WANG Haiming |
| |
| Abstract: | We consider a class of on-line variable-sized bin packing problems as follows: Given a list of items, some of them are kernels, One needs to put them into bins which arrive on time one by one or batch by batch with capacities varying from time to time. The objective is to minimize the total size of bins used. We first show the performance ratios of NF(D) and FF(D) algorithms go arbitrarily large. We then present modified algorithms MNF(D) and MFF(D) with tight performance ratio 3. |
| |
| Keywords: | Bin packing on-line algorithm variable-sized kernel performance ratio |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
