NSF Young Investigator: Investigation of Multi-Class Queuing Networks

点击翻译按钮获取中文摘要

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.