NSF Young Investigator: Investigation of Multi-Class Queuing Networks

本研究的重点是对复杂制造系统中产生的多类排队网络的几个方面进行研究。研究的范围将从这些网络的基本数学模型的发展到一些现实世界应用的模型的计算机实现。具体的研究课题包括晶圆生产线的调度、多类排队网络的稳定性、非先进先出（非先进先出）策略下的布朗模型、大流量收敛以及反射布朗运动（RBM）的平稳分布计算。如果相应的确定性流体极限最终达到零并保持在那里，则称排队网络是稳定的。对晶圆线制造的研究将调查这些线的当前操作政策是否稳定。如果系统在不稳定的策略下运行，则可能被误认为资源不足。排队网络的稳定性研究将探讨这样一个猜想：如果访问一个站点的所有客户类别具有相同的平均服务时间，并且每个站点的名义负载小于1，则任何节省工作的策略都是稳定的。还将研究两种稳定政策的流体模型。布朗模型已被证明对排队网络的近似分析是有效的。也证明了迄今为止大多数布朗模型所采用的FIFO在某些网络中可能是不稳定的。尽管大量的流量限制被用来证明使用布朗模型的合理性，但对于任何策略下具有反馈的一般多类网络，不存在这样的极限定理。对于同一站点的顾客具有相同的平均服务率的情况，建立了FIFO策略下的大流量限制定理的证明。为了改进和扩展现有的计算任意多面体区域内RBM平稳分布的算法，本文将采用有限元法。这将使封闭排队网络和有限缓冲排队网络产生的rbm的平稳分布的计算成为可能。布朗模型在排队网络的性能分析和最优或接近最优调度中都起着重要的作用。布朗近似将用于分析大多数在实践中有趣的排队网络模型。布朗近似方案的计算机实现将预测各种排队网络的性能，包括那些在制造和电信系统中出现的网络。

9457336 Dai The focus of this research is the investigation of several aspects of multi-class queuing networks that arise from complex manufacturing systems. The scope of the research will range from the development of fundamental mathematical models of such networks to the computer implementation of the models for some real world applications. Specific research topics to be investigated include the scheduling of wafer fabrication lines, stability of multi-class queuing networks, Brownian models under non-FIFO (non-first in-first out) policies, heavy traffic convergence, and computation of stationary distribution for a reflected Brownian motion (RBM). A queuing network is said to be stable if the corresponding deterministic fluid limit eventually reaches zero and remains there. Research on wafer line fabrication will investigate whether the current operating policies of such lines are stable. If a system operates under an unstable policy, it could be mistaken to have insufficient resources. Study of stability of queuing networks will investigate the conjecture that if all customer classes visiting a station have the same mean service time, and the nominal load at each station is less than one, then any work-conserving policy is stable. Fluid models of two stable policies will also be investigated. Brownian models have been proved to be effective for the approximate analysis of queuing networks. It has also been proved that FIFO which most Brownian models to date employ may be unstable in some networks. Although a heavy traffic limit is used to justify the use of Brownian models, no such limit theorem exist for a general multi-class network with feedback under any policies. A proof for the heavy traffic limit theorem under the FIFO policy will be established for the case in which customers that visit the same station also have the same mean service rate. To improve and extend the existing algorithm for computing the stationary distribution of an RBM in an arbitrary polyhedral domain, fin ite element method will be used. This will enable the computation of stationary distribution of RBMs arising from closed queuing networks and finite buffer queuing networks. Brownian models play important roles in both performance analysis and optimal or near optimal scheduling of queuing networks. The Brownian approximation will be used to analyze most queuing network models that are interesting in practice. The computer implementation of the Brownian approximation scheme will predict the performances of a variety of queuing networks, including those that arise in manufacturing and telecommunication systems.