Approximate linear programming for a queueing control problem

作     者：Samiedaluie, Saied Zhang, Dan Zhang, Rui 

作者机构：Univ Alberta Alberta Sch Business Edmonton AB Canada Univ Colorado Leeds Sch Business Boulder CO 80309 USA 

出 版 物：《COMPUTERS & OPERATIONS RESEARCH》 (计算机与运筹学研究)

年 卷 期：2024年第169卷

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：Dynamic programming Queues Approximate Linear Programming Admission 

摘      要：Admission decisions for loss systems accessed by multiple customer classes are a classical queueing control problem with a wide variety of applications. When a server is available, the decision is whether to admit an arriving customer and collect a lump-sum revenue. The system can be modeled as a continuous-time infinite-horizon dynamic program, but suffers from the curse of dimensionality when different customer classes have different service rates. We use approximate linear programming to solve the problem under three approximation architectures: affine, separable piecewise linear and finite affine. The finite affine approximation is a recently proposed generalization of the affine approximation, which allows for non-stationary parameters. For both affine and finite affine approximations, we derive equivalent, but more compact, formulations that can be efficiently solved. We propose a column generation algorithm for the separable piecewise linear approximation. Our numerical results show that the finite affine approximation can obtain the tightest bounds for 75% of the instances among the three approximations. Especially, when the number of servers is large and/or the load on the system is high, the finite affine approximation always achieves the tightest bounds. Regarding policy performance, the finite affine approximation has the best performance on average compared to the other two approximations and the achievable performance region method (Bertsimaset al., 1994, Kumar and Kumar, 1994). Furthermore, the finite affine approximation is 4 to 5 orders of magnitude faster than the achievable performance region method and the separable piecewise linear approximation for large-scale instances. Therefore, considering bounds, policy performance, and computational efficiency, the finite affine approximation emerges as a competitive approximation architecture for the class of problems studied here.