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

Clc Number:

Fund Project:

  • Article
  • |
  • Figures
  • |
  • Metrics
  • |
  • Reference
  • |
  • Related
  • |
  • Cited by
  • |
  • Materials
  • |
  • Comments
    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.

    Reference
    Related
    Cited by
Get Citation

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

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:January 25,2000
  • Revised:August 22,2000
  • Adopted:
  • Online:
  • Published:
You are the firstVisitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063