Title page for ETD etd-12152005-230125


Type of Document Dissertation
Author Ongkunaruk, Pornthipa
Author's Email Address pongkuna@vt.edu
URN etd-12152005-230125
Title Asymptotic Worst-Case Analyses for the Open Bin Packing Problem
Degree PhD
Department Industrial and Systems Engineering
Advisory Committee
Advisor Name Title
Chan, Lap Mui Ann Committee Chair
Lin, Kyle Y. Committee Co-Chair
Anderson-Cook, Christine M. Committee Member
Bish, Ebru K. Committee Member
Sarin, Subhash C. Committee Member
Keywords
  • Asymptotic Worst-Case Performance Ratio
  • Off-Line Algorithms
  • Bin Packing
Date of Defense 2005-10-07
Availability unrestricted
Abstract
The open bin packing problem (OBPP) is a new

variant of the well-known bin packing problem. In the OBPP, items

are packed into bins so that the total content before the last item

in each bin is strictly less than the bin capacity. The objective is

to minimize the number of bins used. The applications of the OBPP

can be found in the subway station systems in Hong Kong and Taipei

and the scheduling in manufacturing industries. We show that the

OBPP is NP-hard and propose two heuristic algorithms instead of

solving the problem to optimality. We propose two offline algorithms

in which the information of the items is known in advance. First, we

consider the First Fit Decreasing (FFD) which is a good

approximation algorithm for the bin packing problem. We prove that

its asymptotic worst-case performance ratio is no more than 3/2.

We observe that its performance for the OBPP is worse than that of

the BPP. Consequently, we modify it by adding the algorithm that the

set of largest items is the set of last items in each bin. Then, we

propose the Modified First Fit Decreasing (MFFD) as an alternative

and prove that its asymptotic worst-case performance ratio is no

more than 91/80. We conduct empirical tests to show their

average-case performance. The results show that in general, the FFD

and MFFD algorithms use no more than 33% and 1% of the number

of bins than that of optimal packing, respectively. In addition, the

MFFD is asymptotically optimal when the sizes of items are (0,1)

uniformly distributed.

Files
  Filename       Size       Approximate Download Time (Hours:Minutes:Seconds) 
 
 28.8 Modem   56K Modem   ISDN (64 Kb)   ISDN (128 Kb)   Higher-speed Access 
  final.pdf 436.51 Kb 00:02:01 00:01:02 00:00:54 00:00:27 00:00:02

Browse All Available ETDs by ( Author | Department )

dla home
etds imagebase journals news ereserve special collections
virgnia tech home contact dla university libraries

If you have questions or technical problems, please Contact DLA.