受启动空间约束的装箱问题
DOI:
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

基金项目:

国家重点基础研究发展规划973资助项目(G1998030403)


On a Constrained Bin Packing Problem with Start-Up Space
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    提出了一种带有启动空间的约束装箱问题(start-up bin packing problem,简称SBPP),即不同类型的物品放入同一箱子中需要一个启动空间.该问题在工作分配、任务调度和日常生活中的包装等问题中有着广泛的应用背景.给出了一个求解SBPP的线性脱线算法C-NF,其最坏情况渐近性能比为2,与启动空间的大小无关.对该算法的平均性能进行了实验分析.另外,还分析了SBPP的在线特性,指出大量的经典在线装箱算法应用于SBPP都不存在确定的最坏情况渐近性能比,也给出了一种具有确定的最坏情况渐近性能比的在线算法.

    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.

    参考文献
    相似文献
    引证文献
引用本文

顾晓东,许胤龙,陈国良,黄刘生.受启动空间约束的装箱问题.软件学报,2002,13(3):390-397

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2000-01-25
  • 最后修改日期:2000-08-22
  • 录用日期:
  • 在线发布日期:
  • 出版日期:
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号