First-fit allocation of queues: Tight probabilistic bounds on wasted space

DOI10.1016/0304-4149(90)90098-DzbMath0722.60094OpenAlexW2000320900MaRDI QIDQ756295

Leopold Flatto, Frank Thompson Leighton, Edward G. jun. Coffman

Publication date: 1990

Published in: Stochastic Processes and their Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-4149(90)90098-d

zbMATH Keywords

queuesrandom walkPoisson processfirst-in-first-outprocessor sharingsteady state in heavy traffic

Mathematics Subject Classification ID

Sums of independent random variables; random walks (60G50) Queueing theory (aspects of probability theory) (60K25) Queues and service in operations research (90B22)

Related Items

Asymptotic expansions for a stochastic model of queue storage, Some Exact and Asymptotic Solutions to Single Server Models of Dynamic Storage, Geometrical Optics and Models of Computer Memory Fragmentation, The distribution of wasted spaces in the M/M/∞ queue with ranked servers, Packings in two dimensions: Asymptotic average-case analysis of algorithms, Storage allocation under processor sharing. I: Exact solutions and asymptotics, Average-case analysis of cutting and packing in two dimensions, Storage allocation under processor sharing II: Further asymptotic results

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A provably efficient algorithm for dynamic storage allocation
• The M/M/\(\infty\) service system with ranked servers in heavy traffic. With a preface by Franz Ferschl
• Some interesting processes arising as heavy traffic limits in an M/M/\(\infty\) storage process
• Sunset over Brownistan
• Markov chain models - rarity and exponentiality
• Stochastic Models of Queue Storage
• A Stochastic Model of Fragmentation in Dynamic Storage Allocation
• Probability Inequalities for Sums of Bounded Random Variables