Asymptotic Properties of Stochastic Greedy Bin-Packing
Loading...
Authors
Gaver, Donald P.
Jacobs, Patricia A.
Subjects
greedy algorithm
bin packing
job scheduling
asymptotic results
Ornstein-Uhlenbeck process
bin packing
job scheduling
asymptotic results
Ornstein-Uhlenbeck process
Advisors
Purdue, Peter
Date of Issue
1993-11
Date
Nov 1993
Publisher
Monterey, California. Naval Postgraduate School
Language
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 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.
Type
Technical Report
Description
Series/Report No
Department
Operations Research
Identifiers
NPS Report Number
NPS-OR-93-017
Sponsors
This report was prepared in conjunction with research funded by the Naval Postgraduate School Direct Funded Research Program.
Funder
Format
Citation
Distribution Statement
Approved for public release; distribution is unlimited.
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.