| 本文已被：浏览 4463次 下载 6335次 |
码上扫一扫！ |
|
|
| 受启动空间约束的装箱问题 |
|
顾晓东1, 许胤龙1, 陈国良1, 黄刘生1
|
|
国家高性能计算中心,合肥,安徽,合肥,230027,中国科学技术大学,计算机科学与技术系,安徽,合肥,230027
|
|
| 摘要: |
| 提出了一种带有启动空间的约束装箱问题(start-up bin packing problem,简称SBPP),即不同类型的物品放入同一箱子中需要一个启动空间.该问题在工作分配、任务调度和日常生活中的包装等问题中有着广泛的应用背景.给出了一个求解SBPP的线性脱线算法C-NF,其最坏情况渐近性能比为2,与启动空间的大小无关.对该算法的平均性能进行了实验分析.另外,还分析了SBPP的在线特性,指出大量的经典在线装箱算法应用于SBPP都不存在确定的最坏情况渐近性能比,也给出了一种具有确定的最坏情况渐近性能比的在线算法. |
| 关键词: 装箱问题 组合优化 近似算法 最坏情况渐近性能比 平均性能比 |
| DOI： |
| 分类号: |
| 基金项目:国家重点基础研究发展规划973资助项目(G1998030403) |
|
| On a Constrained Bin Packing Problem with Start-Up Space |
|
GU Xiao-dong,XU Yin-long,CHEN Guo-liang,HUANG Liu-sheng
|
| Abstract: |
| 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. |
| Key words: bin packing problem combinatorial optimization approximation algorithm asymptotic worst-case performance ratio average-case performance ratio |
