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

Yue Hu, Jing Dong, Ohad Perry

Research output: Contribution to journalArticlepeer-review

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. Our proofs that the UI condition holds in these two cases may be of an independent interest.

MSC Codes 60K25, 60F17, 90B15, 37A50

Original languageEnglish (US)
JournalUnknown Journal
StatePublished - May 18 2020

ASJC Scopus subject areas

  • General

Fingerprint Dive into the research topics of 'Asymptotic Optimality of the Binomial-Exhaustive Policy for Polling Systems with Large Switchover Times'. Together they form a unique fingerprint.

Cite this