Bin packing: Maximizing the number of pieces packed

E. G. Coffman, J. Y.T. Leung, D. W. Ting

Research output: Contribution to journalArticlepeer-review

55 Scopus citations

Abstract

We consider a variant of the classical one-dimensional bin-packing problem: The number of bins is fixed and the object is to maximize the number of pieces packed from some given set. Both problems have applications in processor and storage allocation in computer systems in addition to a broad application in operations research. It can easily be shown that both problems are NP-complete; our approach will be to propose and analyze very fast heuristics. We consider a class of algorithms and bound the performance of an arbitrary algorithm in that class. Finally we propose an algorithm, the first-fit-increasing algorithm, and analyze its running time and relative performance.

Original languageEnglish (US)
Pages (from-to)263-271
Number of pages9
JournalActa Informatica
Volume9
Issue number3
DOIs
StatePublished - Sep 1 1978

All Science Journal Classification (ASJC) codes

  • Software
  • Information Systems
  • Computer Networks and Communications

Fingerprint

Dive into the research topics of 'Bin packing: Maximizing the number of pieces packed'. Together they form a unique fingerprint.

Cite this