The Ordered Open-End Bin-Packing Problem

Jian Yang () and Joseph Y.-T. Leung ()
Additional contact information
Jian Yang: Department of Industrial and Manufacturing Engineering, New Jersey Institute of Technology, Newark, New Jersey 07102
Joseph Y.-T. Leung: Department of Computer Science, New Jersey Institute of Technology, Newark, New Jersey 07102

Operations Research, 2003, vol. 51, issue 5, 759-770

Abstract: We study a variant of the classical bin-packing problem, the ordered open-end bin-packing problem, where first a bin can be filled to a level above 1 as long as the removal of the last piece brings the bin's level back to below 1 and second, the last piece is the largest-indexed piece among all pieces in the bin. We conduct both worst-case and average-case analyses for the problem. In the worst-case analysis, pieces of size 1 play distinct roles and render the analysis more difficult with their presence. We give lower bounds for the performance ratio of any online algorithm for cases both with and without the 1-pieces, and in the case without the 1-pieces, identify an online algorithm whose worst-case performance ratio is less than 2 and an offline algorithm with good worst-case performance. In the average-case analysis, assuming that pieces are independently and uniformly drawn from [0, 1], we find the optimal asymptotic average ratio of the number of occupied bins over the number of pieces. We also introduce other online algorithms and conduct simulation study on the average-case performances of all the proposed algorithms.

Keywords: Mathematics: combinatorics; Probability: stochastic model applications; Transportation: costs (search for similar items in EconPapers)
Date: 2003
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.51.5.759.16753 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:51:y:2003:i:5:p:759-770

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().