The ordered open-end bin-packing problem

Jian Yang, Joseph Y.T. Leung

Research output: Contribution to journalArticlepeer-review

19 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)759-770
Number of pages12
JournalOperations Research
Volume51
Issue number5
DOIs
StatePublished - Sep 2003

All Science Journal Classification (ASJC) codes

  • Computer Science Applications
  • Management Science and Operations Research

Keywords

  • Mathematics: combinatorics
  • Probability: stochastic model applications
  • Transportation: costs

Fingerprint

Dive into the research topics of 'The ordered open-end bin-packing problem'. Together they form a unique fingerprint.

Cite this