Asymptotic Properties of Stochastic Greedy Bin-Packing
NAVAL POSTGRADUATE SCHOOL MONTEREY CA DEPT OF OPERATIONS RESEARCH
Pagination or Media Count:
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 Gaussiannormal 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.
- Statistics and Probability