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

[摘要] 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 quantityentering 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 anygiven period depends on the underlying state in that period. The outstanding inputs inthe system are recorded in strings to keep track of the ages, i.e., the time elapsed sincetheir arrival, of each input. The decision of when to clear the system depends on a clearingpolicy;; 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 quantitiescleared; a penalty is charged to the outstanding inputs in every period, and such penalty isnon-decreasing in both the quantities and the ages of the inputs. We model the system asa tree structured Markov chain with Markovian input processes and evaluate the clearingpolicies 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.

[发布机构] University of Waterloo

[关键词] Management Sciences