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 processesperformance measuresmatrix-analytic methodsqueueing theorypositive recurrencebin packingstationary distributionsLyapunov function techniques

Mathematics Subject Classification ID

Stationary stochastic processes (60G10) Stochastic network models in operations research (90B15) Deterministic scheduling theory in operations research (90B35) Queueing theory (aspects of probability theory) (60K25) Queues and service in operations research (90B22) Inventory, storage, reservoirs (90B05) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Applications of queueing theory (congestion, allocation, storage, traffic, etc.) (60K30)

Related Items (4)

Limit theorems and structural properties of the cat-and-mouse Markov chain and its generalisations ⋮ Fast Approximation Methods for Online Scheduling of Outpatient Procedure Centers ⋮ Interior-Point-Based Online Stochastic Bin Packing ⋮ Stability of a Markov-modulated Markov Chain, with application to a wireless network governed by two protocols

Cites Work

• 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
• Average-case analyses of first fit and random fit bin packing
• 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

This page was built for publication: Analysis of Stochastic Online Bin Packing Processes