Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

University of Alberta

$23,000.00

Approximate Dynamic Programming for Service Systems

FY 2024-25

Summary
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.
Program
Discovery Grants Program - Individual
Location
Alberta, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
RGPIN-2020-04229
Name nom
Samiedaluie, Saied
Department département
Alberta School of Business/Accounting, Operations, and Information Systems
Organization id
9
Institution établissement
University of Alberta
Province en
Alberta
Province fr
Alberta
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2024
Competition year année de concours
2020
Award amount
23000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR LA DÉCOUVERTE
Committee code
1509
Committee name en
Civil, Industrial and Systems Engineering
Committee name fr
Génie civil, industriel et des systèmes
Area of application code
1200
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Advancement of knowledge
Area of application fr
Avancement des connaissances
Research subject code
1601
Research subject group en
Industrial engineering
Research subject group fr
Génie industriel
Research subject en
Operations research and management science
Research subject fr
Recherche opérationnelle et science de la gestion
Field of research list names en
Not available
Field of research list names fr
Non disponible
Socioeconomic objective list names en
Not available
Socioeconomic objective list names fr
Non disponible
Application title
Approximate Dynamic Programming for Service Systems
Keywords
dynamic programming and optimization; approximate dynamic programming; service systems; operations management; queueing systems
Application summary
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.