Analysis of Stochastic Online Bin Packing Processes

Analysis of Stochastic Online Bin Packing Processes
复制标题

随机在线装箱过程分析

DOI：
--
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
M. Squillante
M. Squillante
中科院分区：
--
文献类型：
--
作者：
D. Gamarnik;M. Squillante

文献摘要

被引文献

相似文献

摘要经典箱包装问题的一个随机在线版本，其中箱对应于在离散时间单位的请求流中分配的资源容量，是在各种应用领域出现的一个基本问题，包括网络带宽分配，计算机内存管理和槽口网络通道中的消息传输。本文基于李雅普诺夫函数技术和矩阵解析方法的结合，给出了相应的多维随机过程的数学分析，每个维度都可能是无限的。我们的分析得到了这种随机装箱过程在一般概率分布下的稳定性条件和平稳分布。我们进一步提供了一些算法技术来进行这些测量的数值计算。
Abstract A stochastic online version of the classical bin packing problem, where a bin corresponds to the capacity of a resource allocated among streams of requests at discrete time units, is a fundamental problem that arises in a wide variety of application areas including bandwidth allocation in networks, memory management in computers, and message transmission in slotted network channels. We derive a mathematical analysis of the corresponding multi-dimensional stochastic process, potentially infinite in each dimension, under a general class of scheduling policies based on a combination of a Lyapunov function technique and matrix-analytic methods. Our analysis yields stability conditions and stationary distributions for this stochastic bin packing process under general probability distributions. We further provide some algorithmic techniques for the numerical computation of these measures.