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.
