Approximate Dynamic Programming for Service Systems

点击翻译按钮获取中文摘要

This research develops theoretical and computational foundations for designing novel approximate dynamic programming (ADP) methodologies for service systems. I plan to theoretically investigate the policy derived from a new ADP approach that is based on time-varying approximation of value functions. In this framework, the approximation parameters are allowed to change over time for a finite horizon; thereafter, the parameters become stationary. Recent research findings suggest that, for some queueing control problems, the performance of such time-varying approximation is better, compared to the stationary approximations, both in terms of quality of the bounds on the optimal solution and the policy performance. I intend to investigate its performance further, and study whether performance guarantees can be provided for a broader range of service problems. Next, I plan to focus on using nonlinear approximations in ADPs that tend not to be computationally efficient in practice and examine the plausibility of variable/constraint aggregation as one approach to deriving more compact formulations. In particular, I plan to 1) quantify the loss in accuracy as a result of aggregation, 2) design a systematic way to improve the quality of aggregated formulations by incorporating additional constraints, and 3) develop decomposition techniques to enhance computational efficiency. My research will make theoretical and practical contributions to the fields of Operations Research and Operations Management in service sectors. From the theoretical perspective, the significance of this research is that it will provide an assurance for the performance of the policies obtained from time-varying ADPs. Performance guarantees for approximate policies are highly valued in the Operations Research literature. Once such guarantees are provided, the time-varying ADPs will be extensively applied with a reasonable degree of confidence to different operational problems. On the application side, the ADP methods proposed in this research are guaranteed to take less computational efforts because their size increases linearly with the problem size. They are also expected to perform well in practice as the quality of approximation is improved by adding additional constraints and by employing novel decomposition techniques. The major drawback with the existing ADP techniques is that they are computationally intensive. The proposed methods in this proposal, however, will enable practitioners to apply our ADPs to the problems where the decision-making model needs to be solved frequently and quickly.