Show simple item record

dc.contributor.authorOngkunaruk, Pornthipaen_US
dc.date.accessioned2014-03-14T20:20:20Z
dc.date.available2014-03-14T20:20:20Z
dc.date.issued2005-10-07en_US
dc.identifier.otheretd-12152005-230125en_US
dc.identifier.urihttp://hdl.handle.net/10919/30105
dc.description.abstractThe 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.en_US
dc.publisherVirginia Techen_US
dc.relation.haspartfinal.pdfen_US
dc.rightsIn Copyrighten
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.subjectAsymptotic Worst-Case Performance Ratioen_US
dc.subjectOff-Line Algorithmsen_US
dc.subjectBin Packingen_US
dc.titleAsymptotic Worst-Case Analyses for the Open Bin Packing Problemen_US
dc.typeDissertationen_US
dc.contributor.departmentIndustrial and Systems Engineeringen_US
dc.description.degreePh. D.en_US
thesis.degree.namePh. D.en_US
thesis.degree.leveldoctoralen_US
thesis.degree.grantorVirginia Polytechnic Institute and State Universityen_US
thesis.degree.disciplineIndustrial and Systems Engineeringen_US
dc.contributor.committeechairChan, Lap Mui Annen_US
dc.contributor.committeememberSarin, Subhash C.en_US
dc.contributor.committeememberAnderson-Cook, Christine M.en_US
dc.contributor.committeememberBish, Ebru K.en_US
dc.identifier.sourceurlhttp://scholar.lib.vt.edu/theses/available/etd-12152005-230125/en_US
dc.contributor.committeecochairLin, Kyle Y.en_US
dc.date.sdate2005-12-15en_US
dc.date.rdate2008-01-06
dc.date.adate2006-01-06en_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record