Asymptotic Properties of Stochastic Greedy Bin-Packing
Gaver, Donald P.
Jacobs, Patricia A.
MetadataShow full item record
An adaptive or greedy policy for packing I bins, or equivalently for scheduling jobs for the attention of a number, I, of processors is studied. It is shown that the suitably normalized bin contents become nearly jointly but degenerately Gaussian/normal if the rate of approach of jobs becomes large. Explicit and simple parameter characterizations are supplied and the asymptotics are compared with simulation. The advantage of the greedy policy over a laissezfaire policy of equal access is quantified, and seen to depend upon number of bins or processors.
Approved for public release; distribution is unlimited.