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.