Stochastic Clearing Systems With Markovian Inputs: Performance Evaluation and Optimal Policies

Abstract

This thesis studies the stochastic clearing systems which are characterized by a non-decreasing stochastic input process {Y(t), t > 0}, where Y(t) is the cumulative quantity entering the system in [0, t], and an output mechanism that intermittently and instantaneously clears the system. Examples of such systems can be found in shipment consolidation, inventory backlog, lot sizing, shuttle bus dispatch, bulk service queues, and other stochastic service and storage systems. In our model, the input process is governed by an underlying discrete-time Markov chain such that, the distribution of the input in any given period depends on the underlying state in that period. The outstanding inputs in the system are recorded in strings to keep track of the ages, i.e., the time elapsed since their arrival, of each input. The decision of when to clear the system depends on a \clearing policy" which itself depends on the input quantities, ages, and the underlying state. Clearing the system will incur a fixed cost and a variable cost depending on the quantities cleared; a penalty is charged to the outstanding inputs in every period, and such penalty is non-decreasing in both the quantities and the ages of the inputs. We model the system as a tree structured Markov chain with Markovian input processes and evaluate the clearing policies with respect to the expected total costs over a finite horizon, the expected total discounted cost over an infinite horizon, as well as the expected average total cost per period over an infinite horizon. Relying on theories of Markov Decision Processes and stochastic dynamic programming, we then proceed to show some properties unique to the optimal clearing policies, and prove that a state-dependent threshold policy can be optimal under special conditions. We develop algorithms or heuristics to evaluate a given clearing policy and find the optimal clearing policy. We also use Matrix Analytic Methods to evaluate a given clearing policy and develop an efficient heuristic to find near-optimal clearing policies. Finally, we conduct extensive numerical analyses to verify the correctness, complexity, and optimality gap of our algorithms and heuristics. Our numerical examples successfully demonstrate the analytical results we proved.