A stochastic model of bin-packing

E. G. Coffman; Kimming So; Micha Hofri; A. C. Yao

doi:10.1016/S0019-9958(80)90050-9

A stochastic model of bin-packing

E. G. Coffman
, Kimming So
, Micha Hofri
, A. C. Yao

Faculty of Electronic and Information Engineering

University of California at Santa Barbara
Technion-Israel Institute of Technology

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

66 Scopus citations

Abstract

Recent research in combinatorial bin-packing models is extended to a stochastic model in which an arbitrary distribution of piece sizes is assumed. The asymptotic expected bin occupancy is obtained for a simple on-line algorithm. Convergence properties are also presented so that, for a given set of pieces, this measure can be related to the expected number of bins required relative to an optimization rule.

Original language	English
Pages (from-to)	105-115
Number of pages	11
Journal	Information and Control
Volume	44
Issue number	2
DOIs	https://doi.org/10.1016/S0019-9958(80)90050-9
State	Published - Feb 1980

Access to Document

10.1016/S0019-9958(80)90050-9

Cite this

@article{461189b44c9448a79b9c52dde55eabe7,

title = "A stochastic model of bin-packing",

abstract = "Recent research in combinatorial bin-packing models is extended to a stochastic model in which an arbitrary distribution of piece sizes is assumed. The asymptotic expected bin occupancy is obtained for a simple on-line algorithm. Convergence properties are also presented so that, for a given set of pieces, this measure can be related to the expected number of bins required relative to an optimization rule.",

author = "Coffman, \{E. G.\} and Kimming So and Micha Hofri and Yao, \{A. C.\}",

year = "1980",

month = feb,

doi = "10.1016/S0019-9958(80)90050-9",

language = "英语",

volume = "44",

pages = "105--115",

journal = "Information and Control",

issn = "0019-9958",

publisher = "Academic Press Inc.",

number = "2",

}

TY - JOUR

T1 - A stochastic model of bin-packing

AU - Coffman, E. G.

AU - So, Kimming

AU - Hofri, Micha

AU - Yao, A. C.

PY - 1980/2

Y1 - 1980/2

N2 - Recent research in combinatorial bin-packing models is extended to a stochastic model in which an arbitrary distribution of piece sizes is assumed. The asymptotic expected bin occupancy is obtained for a simple on-line algorithm. Convergence properties are also presented so that, for a given set of pieces, this measure can be related to the expected number of bins required relative to an optimization rule.

AB - Recent research in combinatorial bin-packing models is extended to a stochastic model in which an arbitrary distribution of piece sizes is assumed. The asymptotic expected bin occupancy is obtained for a simple on-line algorithm. Convergence properties are also presented so that, for a given set of pieces, this measure can be related to the expected number of bins required relative to an optimization rule.

UR - https://www.scopus.com/pages/publications/0018985939

U2 - 10.1016/S0019-9958(80)90050-9

DO - 10.1016/S0019-9958(80)90050-9

M3 - 文章

AN - SCOPUS:0018985939

SN - 0019-9958

VL - 44

SP - 105

EP - 115

JO - Information and Control

JF - Information and Control

IS - 2

ER -

A stochastic model of bin-packing

Abstract

Access to Document

Other files and links

Fingerprint

Cite this