Stochastic Convexity in Queueing Networks and Its Application

该提案由加州大学伯克利分校的J.G. Shanthikumar和哈佛大学的D.D. Yao共同提交。提出的研究项目的重点是研究排队网络的凸性。这些特性在排队网络的优化设计和控制中通常是必不可少的，在过去的三十年中，排队网络已经成为研究复杂随机系统（如计算机系统、通信网络、数据库系统和制造系统）的主要工具。PI提出了随机凸性的新概念，并重点介绍了其在制造系统排队网络模型中的应用。这个新概念捕捉了排队网络中随机过程相对于时间和其他参数变化的二阶（例如，凸性或凹性）行为。他们所关注的排队网络模型是对经典模型的重大背离；例如，它们允许一般的到达间隔和服务时间分配、有限缓冲区和阻塞。注意力也集中在这些网络的动态行为的（瞬态）分析。基于样本路径分析，他们提出了新的方法来建立这些网络背后的某些关键过程的随机凸性。近年来，基于蒙特卡罗模拟的随机优化方法得到了发展，用于解决排队网络中的各种优化设计问题。随机凸性结果为这些方法提供了二阶最优性条件，从而显著地增加了排队网络的理论和应用。

This proposal is jointly submitted by J.G. Shanthikumar of the University of California, Berkeley, and by D.D. Yao of Harvard University. The focus of the proposed research project is on studying convexity properties in queueing networks. Such properties are often indispensable in the optimal design and control of queueing networks, which for the last three decades have been major tools in studying complex stochastic systems such as computer systems, communication networks, data-base systems, and manufacturing systems. The PI's propose a new concept of stochastic convexity, and highlight its applications in queueing network models of manufacturing systems. This new concept captures the second-order (e.g., convexity or concavity) behavior of the stochastic processes in queueing networks with respect to temporal and other parametric changes. The queueing network models that they focus on are major departures from classical models; for instance, they allow general interarrival and service time distributions, finite buffers and blocking. Attention is also focused on the (transient) analysis of the dynamic behavior of these networks. Based on sample path analysis, they propose new approaches to establish stochastic convexity of certain key processes that underlie these networks. Recently, stochastic optimization approaches that are based on Monte- Carlo simulation have been developed to solve various optimal design problems in queueing networks. Stochastic convexity results provide second-order optimality conditions for those approaches, and hence significantly add to the theory and applications of queueing networks.