Type
Text
Type
Dissertation
Advisor
Zelinsky, Gregory J. | Jiaqiao Hu | Thomas Robertazzi.
Date
2010-12-01
Keywords
Markov decision process, queueing system, trunk reservation policy, unichain classification | Operations Research -- Applied Mathematics
Department
Department of Applied Mathematics and Statistics
Language
en_US
Source
This work is sponsored by the Stony Brook University Graduate School in compliance with the requirements for completion of degree.
Identifier
http://hdl.handle.net/11401/72715
Publisher
The Graduate School, Stony Brook University: Stony Brook, NY.
Format
application/pdf
Abstract
My dissertation addresses the unichain classification problem for any finite Markov decision process (MDP) with a recurrent or stopping state and the optimal admission problem for an M/M/k/N controlled queue with holding costs. In the first chapter, we study the unichain classification problem for MDPs. The unichain classification problem is to detect whether an MDP with finite states and actions is unichain or not. This problem has been proven to be NP-hard. We study this problem while an MDP contains a state which is either recurrent under all deterministic policies or absorbing under some action. We introduce the definitions of avoidable and reachable sets and provide the corresponding polynomial algorithms that finds the states from which a given set is avoidable or reachable. We also provide a polynomial algorithm that detects whether a state is recurrent and solves the unichain classification problem for an MDP with a recurrent state and a polynomial algorithm for finding all recurrent and stopping states and solving the unichain classification problem with recurrent or stopping states. At the end of the first chapter, we discuss detecting all transient states in an MDP in polynomial time.In the second chapter, we study optimal admission of arrivals to an M/M/k/N queue. The arriving customers are classified into m types. The rewards and holding costs depend on customer types. Upon admitting an arriving customer, the system collects the reward from the admitted customer and pays the holding cost to the admitted customer. We study average reward per unit time for the problem. We prove the existence of an optimal trunk reservation policy and describe the structures of stationary optimal, canonical, bias optimal, and Blackwell optimal policies. If there exist two or more stationary optimal policies, we apply more sensitive optimality criteria to detect the best policy among all stationary optimal policies. We show that bias optimal and Blackwell optimal policies are unique, coincide, and are the trunk reservation policies with the largest optimal control level for each customer type.
Recommended Citation
Yang, Fenghsu, "Classification Problems for MDPs and Optimal Customer Admission to M/M/k/N Queues" (2010). Stony Brook Theses and Dissertations Collection, 2006-2020 (closed to submissions). 1918.
https://commons.library.stonybrook.edu/stony-brook-theses-and-dissertations-collection/1918