Approximate Dynamic Programming for Service Systems

服务系统的近似动态规划

• 批准号: RGPIN-2020-04229
• 负责人: Samiedaluie, Saied
• 金额: $ 1.68万
• 依托单位: University of Alberta
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2022
• 资助国家: 加拿大
• 起止时间: 2022-01-01 至 2023-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=746458
• 关键词: Approximate; Dynamic; Programming; 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.

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