Stochastic Convexity in Queueing Networks and Its Application

这项提案是由加州大学伯克利分校的J.G.Shanthikumar和哈佛大学的D.D.姚联合提交的。该研究项目的重点是研究排队网络的凸性性质。这些性质在排队网络的最优设计和控制中往往是不可或缺的，在过去的三十年里，排队网络一直是研究复杂随机系统的主要工具，如计算机系统、通信网络、数据库系统和制造系统。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.