Approximate Dynamic Programming for Service Systems

本研究为服务系统设计新的近似动态规划（ADP）方法提供了理论和计算基础。我计划从理论上研究基于时变逼近值函数的新ADP方法衍生的策略。在这个框架中，允许近似参数在有限视界内随时间变化；此后，参数变得平稳。最近的研究结果表明，对于某些排队控制问题，这种时变近似的性能优于平稳近似，无论是在最优解的边界质量还是策略性能方面。我打算进一步研究它的性能，并研究是否可以为更广泛的服务问题提供性能保证。接下来，我计划专注于在adp中使用非线性近似，这些近似在实践中往往不具有计算效率，并检查变量/约束聚合作为推导更紧凑公式的一种方法的合理性。特别是，我计划1)量化由于聚合而导致的准确性损失，2)设计一种系统的方法，通过合并额外的约束来提高聚合公式的质量，以及3)开发分解技术以提高计算效率。我的研究将为服务业运筹学和运营管理领域做出理论和实践上的贡献。从理论角度来看，本研究的意义在于为时变adp得到的策略的性能提供保证。运筹学文献高度重视近似策略的性能保证。一旦提供了这种保证，时变adp将以合理的信任程度广泛应用于不同的操作问题。在应用方面，本研究提出的ADP方法由于其规模随问题规模线性增加，保证了计算量的减少。它们也有望在实践中表现良好，因为通过添加额外的约束和采用新的分解技术来提高近似的质量。现有ADP技术的主要缺点是它们是计算密集型的。然而，本提案中提出的方法将使从业者能够将我们的adp应用于需要频繁和快速解决决策模型的问题。

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.