Asymptotic Optimality of the Binomial-Exhaustive Policy for Polling Systems with Large Switchover Times

DOI10.1214/22-AAP1803arXiv2005.08840MaRDI QIDQ6340936FDOQ6340936

Publication date: 18 May 2020

Abstract: 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.

Mathematics Subject Classification ID

Methods involving semicontinuity and convergence; relaxation (49J45) Stochastic network models in operations research (90B15)

This page was built for publication: Asymptotic Optimality of the Binomial-Exhaustive Policy for Polling Systems with Large Switchover Times

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6340936)