Bin packing: Maximizing the number of pieces packed

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

doi:10.1007/BF00288885

Bin packing: Maximizing the number of pieces packed

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

Research output: Contribution to journal › Article › peer-review

59 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 language	English (US)
Pages (from-to)	263-271
Number of pages	9
Journal	Acta Informatica
Volume	9
Issue number	3
DOIs	https://doi.org/10.1007/BF00288885
State	Published - Sep 1978
Externally published	Yes

All Science Journal Classification (ASJC) codes

Software
Information Systems
Computer Networks and Communications

Access to Document

10.1007/BF00288885

Cite this

@article{f79acb8278904f5ba9d9b23955f71f8d,

title = "Bin packing: Maximizing the number of pieces packed",

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.",

author = "Coffman, {E. G.} and Leung, {J. Y.T.} and Ting, {D. W.}",

year = "1978",

month = sep,

doi = "10.1007/BF00288885",

language = "English (US)",

volume = "9",

pages = "263--271",

journal = "Acta Informatica",

issn = "0001-5903",

publisher = "Springer New York",

number = "3",

}

TY - JOUR

T1 - Bin packing

T2 - Maximizing the number of pieces packed

AU - Coffman, E. G.

AU - Leung, J. Y.T.

AU - Ting, D. W.

PY - 1978/9

Y1 - 1978/9

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0008785637&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0008785637&partnerID=8YFLogxK

U2 - 10.1007/BF00288885

DO - 10.1007/BF00288885

M3 - Article

AN - SCOPUS:0008785637

SN - 0001-5903

VL - 9

SP - 263

EP - 271

JO - Acta Informatica

JF - Acta Informatica

IS - 3

ER -

Bin packing: Maximizing the number of pieces packed

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this