Accession Number:

ADA273378

Title:

Asymptotic Properties of Stochastic Greedy Bin-Packing

Descriptive Note:

Technical rept.,

Corporate Author:

NAVAL POSTGRADUATE SCHOOL MONTEREY CA DEPT OF OPERATIONS RESEARCH

Report Date:

1993-11-01

Pagination or Media Count:

27.0

Abstract:

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.

Subject Categories:

  • Statistics and Probability

Distribution Statement:

APPROVED FOR PUBLIC RELEASE