سخنرانی علمی: كاربرد روش هاي جديد برنامه ريزي پوياي تقريبي براي مسائل كنترل صف

: تعداد بازدید: 1184

عنوان سخنرانی: كاربرد روش هاي جديد برنامه ريزي پوياي تقريبي براي مسائل كنترل صف

سخنران: آقای دکتر سعید سمیعی دلوئی، استادیار دانشگاه آلبرتا کانادا

چکیده:

Admission control for loss systems is a classical queueing control problem with a wide variety of applications. The loss system is a queue accessed by multiple classes of customers and arriving customers are rejected if all servers are busy. 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 propose approximate linear programming methods to solve the problem under three approximation architectures: affine, finite affine, and separable piecewise linear. Affine and separable piecewise linear approximations are popular approximation architectures in the literature while finite affine approximation is relatively new. For both affine and finite affine approximations, we derive reduced formulations which are equivalent to the original approximate linear programs, but are more compact in size and therefore can be efficiently solved. We also propose a column generation algorithm to solve the separable piecewise linear approximation. While there is no definite relationship between the bounds from finite affine and separable piecewise linear approximations, they both produce tighter upper bounds on the optimal value function than the affine approximation. Our numerical results show that affine and separable piecewise linear approximations demonstrate similar performance both in terms of the quality of the bounds and the policy performance when the number of servers is large. Both approximations are inferior to the finite affine approximation when the number of servers is large and/or the load on the system is high. Therefore, the finite affine approximation emerges as a competitive and efficient approximation architecture. We believe it can be useful for a wide variety of queueing control problems.

زمان برگزاری: 1 بهمن 1398

فایل صوتی سخنرانی:

accessed by multiple classes of customers and arriving customers are rejected if all servers are busy. 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 propose approximate linear programming methods to solve the problem under three approximation architectures: affine, finite affine, and separable piecewise linear. Affine and separable piecewise linear approximations are popular approximation architectures in the literature while finite affine approximation is relatively new. For both affine and finite affine approximations, we derive reduced formulations which are equivalent to the original approximate linear programs, but are more compact in size and therefore can be efficiently solved. We also propose a column generation algorithm to solve the separable piecewise linear approximation. While there is no definite relationship between the bounds from finite affine and separable piecewise linear approximations, they both produce tighter upper bounds on the optimal value function than the affine approximation. Our numerical results show that affine and separable piecewise linear approximations demonstrate similar performance both in terms of the quality of the bounds and the policy performance when the number of servers is large. Both approximations are inferior to the finite affine approximation when the number of servers is large and/or the load on the system is high. Therefore, the finite affine approximation emerges as a competitive and efficient approximation architecture. We believe it can be useful for a wide variety of queueing control problems.