NSF Young Investigator: Investigation of Multi-Class Queuing Networks

NSF 青年研究员：多类排队网络的研究

• 批准号: 9457336
• 负责人: Jiangang Dai
• 金额: $ 31.25万
• 依托单位: Georgia Tech Research Corporation
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1994
• 资助国家: 美国
• 起止时间: 1994-09-01 至 2001-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9457336&HistoricalAwards=false
• 关键词: NSF; Young; Investigator; Investigation; Multi

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.

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