FFD bin packing for item sizes with distributions on [0,1/2]

We study the expected behavior of the FFD binpacking algorithm applied to items whose sizes are distributed in accordance with a Poisson process with rate N on the interval [0,1/2] of item sizes. By viewing the algorithm as a succession of queueing processes we show that the expected wasted space fo...

Full description

Saved in:
Bibliographic Details
Main Authors: Floyd, Sally, Karp, Richard
Format: Conference Proceeding
Language:English
Subjects:
Computer science
H infinity control
History
Mathematics
Upper bound
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We study the expected behavior of the FFD binpacking algorithm applied to items whose sizes are distributed in accordance with a Poisson process with rate N on the interval [0,1/2] of item sizes. By viewing the algorithm as a succession of queueing processes we show that the expected wasted space for FFD bin-packing is bounded above by 9.4 bins, independent of N. We extend this upper bound to a FFD bin-packing of items in accordance with a non-homogeneous Poisson process with a nonincreasing intensity function λ(t) on [0,1/2].
ISSN:0272-5428
DOI:10.1109/SFCS.1986.18