Asymptotic Properties of Stochastic Greedy Bin-Packing

摘要

An adaptive or greedy policy for packing I bins, or equivalently for schedulingjobs 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 laissez-faire policy of equal access is quantified, and seen to depend upon number of bins or processors. Greedy algorithm, Bin packing, Job scheduling, Asymptotic results, Ornstein-Uhlenbeck process.