Asymptotic Properties of Stochastic Greedy Bin-Packing

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 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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Nov 01, 1993
Accession Number
ADA273378

Entities

People

  • Donald P. Gaver Jr.
  • Patricia A. Jacobs

Organizations

  • Naval Postgraduate School

Tags

Communities of Interest

  • Biomedical
  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Business Administration
  • Data Science
  • Differential Equations
  • Engineering
  • Equations
  • Information Processing
  • Information Science
  • Mathematics
  • New York
  • Operations Research
  • Probability
  • Public Health
  • Random Variables
  • Scheduling (Production)
  • Standards
  • Statistics

Readers

  • Operations Research
  • Statistical inference.