Multichain Markov Decision Optimization: Theoretical Studies And Applications On The Joint Replacement Problem

For the significant importance, those services related processes are attracting more and more attentions. Some assets e.g., jet engine, consist of many parts. The maintenance of these assets are quite expensive. When some parts are replaced jointly, some costs, e.g., setup cost, can be shared and saved because of the economics of scale. However, it is very hard to obtain good replacement policies. This is caused by the difficulty of evaluating an action, large problem scale and irregular structures of optimal policies. Such a joint replacement problem can be modeled as Markov decision problem. However, as most of related Markov model, the large state space makes it intractable to directly solve real problems. In our work, we explore the problem structure and develop a serial of approaches to address this problem based on Markov decision theory. The main contributions and novelties are summarized as follows.1. Develop time aggregated approach for weakly communicating Markov decision processes. Existing time aggregated approach is developed under single chain Markov models. However, it is NP-hard to determine whether a Markov decision model is single-chain or not. Some of problems, e.g., our joint replacement problem, is not a single chain problem. We give a formulation of time aggregation approach for weakly communicating Markov model which is more general than single chain cases. An incremental optimization approach is developed. More importantly, the approach motivated a value iteration algorithm for time aggregated Markov decision problems. All these algorithms are applicable for weakly communicating problems. Compared with existing methods, our value iteration solves larger problems and requires less storage and computational resources.2. Based on time aggregation, "One Stage Analysis" is developed for solving large joint replacement problems as a heuristic method. Compared with generally used threshold, One-Stage-Analysis method achieves better performance especially when the maintenance setup cost is large or the asset failure rate is small. The policies ob- tained by this method are proved to share similar structures with optimal policies.3. The Rollout algorithm for general large multichain problems is developed. The algorithm is an online one step of policy iteration for improving a base policy. The parameters of the algorithm are analyzed. To improve the efficiency, Ordinal Optimization and Optimal Computing Budge Allocation techniques are introduced to the algorithm.In practice, when it is doable store the state space, time aggregated approach can obtain optimal policy. When the state space is large, One-stage Analysis can obtain near optimal policy efficiently. When the time constrains are not critical, heuristic methods can be improved by the Rollout algorithm. These results are tested by our numerical experiments. In addition, good results are also obtained through applying these methods onto real data.