The Bottom-Left Bin-Packing Heuristic: An Efficient Implementation

Research output: Contribution to journalArticle

218 Scopus citations

Abstract

We study implementations of the bottom-left heuristic for two-dimensional bin-packing. To pack N rectangles into an infinite vertical strip of fixed width, the strategy considered here places each rectangle in turn as low as possible in the strip in a left-justified position. For reasons of simplicity and good performance, the bottom-left heuristic has long been a favorite in practical applications; however, the best implementations found so far require a number of steps O(N3). In this paper, we present an implementation of the bottom-left heuristic which requires linear space and quadratic time. The algorithm is fairly practical, and we believe that even for relatively small values of N, it gives the most efficient implementation of the heuristic, to date. It proceeds by first determining all the possible locations where the next rectangle can fit, then selecting the lowest of them. It is optimal among all the algorithms based on this exhaustive strategy, and its generality makes it adaptable to different packing heuristics.

Original languageEnglish (US)
Pages (from-to)697-707
Number of pages11
JournalIEEE Transactions on Computers
VolumeC-32
Issue number8
DOIs
StatePublished - Jan 1 1983
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Computational Theory and Mathematics
  • Hardware and Architecture
  • Software
  • Theoretical Computer Science
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'The Bottom-Left Bin-Packing Heuristic: An Efficient Implementation'. Together they form a unique fingerprint.

  • Cite this