Analysis of Stochastic Online Bin Packing Processes

DOI10.1081/STM-200057127zbMath1090.90080MaRDI QIDQ5462796

David Gamarnik, Mark S. Squillante

Publication date: 27 July 2005

Published in: Stochastic Models (Search for Journal in Brave)

zbMATH Keywords

stochastic processes; performance measures; matrix-analytic methods; queueing theory; positive recurrence; bin packing; stationary distributions; Lyapunov function techniques

Mathematics Subject Classification ID

60G10: Stationary stochastic processes

90B15: Stochastic network models in operations research

90B35: Deterministic scheduling theory in operations research

60K25: Queueing theory (aspects of probability theory)

90B22: Queues and service in operations research

90B05: Inventory, storage, reservoirs

60J10: Markov chains (discrete-time Markov processes on discrete state spaces)

60J20: Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.)

60K30: Applications of queueing theory (congestion, allocation, storage, traffic, etc.)

Related Items

Stability of a Markov-modulated Markov Chain, with application to a wireless network governed by two protocols

Cites Work

• Unnamed Item
• Unnamed Item
• Markov chains and stochastic stability
• A dynamic storage process
• The average-case analysis of some on-line algorithms for bin packing
• Tight bounds for minimax grid matching with applications to the average case analysis of algorithms
• Spectral properties of the tandem Jackson network, seen as a quasi-birth-and-death process
• Stochastic bandwidth packing process: stability conditions via Lyapunov function technique
• Fluid limits of string valued Markov processes
• Finite birth-and-death models in randomly changing environments
• A Proof for the Queuing Formula: L = λW
• Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms
• Introduction to Matrix Analytic Methods in Stochastic Modeling
• Stochastic analysis of a slotted FIFO communication channel
• ON THE STABILITY OF A BANDWIDTH PACKING ALGORITHM
• Topics in the Constructive Theory of Countable Markov Chains
• On Deciding Stability of Constrained Homogeneous Random Walks and Queueing Systems