2020/05/18 by Yue Hu, Jing Dong, Hu, Yue +3
Business, Management and Accounting · Computer Science · Mathematics · #37A50 #60F17 #60K25 #90B15 #Advanced Queuing Theory Analysis #Age of Information Optimization #FOS: Mathematics #Probability (math.PR) #Stochastic processes and statistical mechanics
paper · pdf · doi:10.48550/arxiv.2005.08840
openalex publication_date 2020/05/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study an optimal-control problem of polling systems with large switchover times, when a holding cost is incurred on the queues. In particular, we consider a stochastic network with a single server that switches between several buffers (queues) according to a pre-specified order, assuming that the switchover times between the queues are large relative to the processing times of individual jobs. Due to its complexity, computing an optimal control for such a system is prohibitive, and so we instead search for an asymptotically optimal control. To this end, we first solve an optimal control problem for a deterministic relaxation (namely, for a fluid model), that is represented as a hybrid dynamical system. We then "translate" the solution to that fluid problem to a binomial-exhaustive policy for the underlying stochastic system, and prove that this policy is asymptotically optimal in a large-switchover-time scaling regime, provided a certain uniform integrability (UI) condition holds. Finally, we demonstrate that the aforementioned UI condition holds in the following cases: (i) the holding cost has (at most) linear growth, and all service times have finite second moments; (ii) the holding cost grows at most at a polynomial rate (of any degree), and the service-time distributions possess finite moment generating functions.