Yiduo Zhou

May 2012
Probabilistic Policies in Re-Entrant Queueing Systems with a Product-Form Steady-State Distribution
Committee Members: Advisor: Advisor: James R. Perkins,SE/ME; Pirooz Vakili, SE/ME; Michael Caramanis, SE/ME; Erol Pekoz, OTM/SE; Appointed Chair: Dan Cole, ME

Abstract: This dissertation presents several new scheduling policies based on real-time information and probabilistic controls for re-entrant (non-acyclic) Markovian queueing systems. One interpretation of the results contained in this dissertation is that they provide a generalization of the results for Jackson networks to re-entrant systems with buffer-dependent routing and non-identical service-time distributions at the machines. This introduces a machine scheduling component that is analogous to going from a 2-D to a 3-D point-of-view. These policies require minimal computational effort, often achieve solid performance, and are scalable to systems with an arbitrary number of machines and buffers. Most importantly, under these scheduling policies, the steady-state buffer-level probability distribution may be determined analytically for a wide variety of Markovian queueing system architectures, including open, closed, or mixed re-entrant systems, systems with deterministic or probabilistic routing, multi-class systems, and systems with parallel servers. Using the product-form buffer-level probability distribution, and modifying standard algorithms for Jackson networks, it is straightforward to evaluate the steady-state performance of these policies, for arbitrarily large re-entrant systems. Thus, the results contained in this dissertation provide the first scalable benchmark for such systems. It is anticipated that the methods and results used in this dissertation will provide a foundation for considerable further research in this area.