This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Yang, J. Articles by Leung, J. Y.-T. Search for Related Content

The Ordered Open-End Bin-Packing Problem

Department of Industrial and Manufacturing Engineering, New Jersey Institute of Technology, Newark, New Jersey 07102
Department of Computer Science, New Jersey Institute of Technology, Newark, New Jersey 07102
yang{at}adm.njit.edu
leung{at}cis.njit.edu

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.

Subject classifications: Mathematics: combinatorics; Probability: stochastic model applications; Transportation: costs.
History: Received April 2001; revision received July 2001; revision received December 2001; revision received July 2002; revision received October 2002; accepted November 2002.