Computing the Moments of Polling Models with Batch Poisson Arrivals by Transform Inversion

Wu-Lin Chen ()
Additional contact information
Wu-Lin Chen: Department of Computer Science and Information Management, Providence University, Taichung City, 43301, Taiwan (Republic of China)

INFORMS Journal on Computing, 2019, vol. 31, issue 3, 515–526

Abstract:

A polling model is defined as a queueing station with a single server serving multiple queues following a certain rule to determine when to stop serving one queue and which queue to serve next. The key to much of the analysis of these systems is to obtain the first two moments of queue lengths at polling instants, which are defined as the instants when the server starts to serve each queue. This study develops a novel approach, in which the generating functions of queue lengths at polling instants are computed iteratively. Transform inversion is then applied to invert these generating functions to obtain their first two moments efficiently. Because the expected waiting time of each queue depends on some basic distributions, such as the service time distributions, the switchover distributions, and the arrival batch distributions only through their first two moments, this study proposes a new transform inversion technique that is called “the pseudotransform inversion algorithm” by introducing “pseudotransforms” of these distributions, which are simply approximations to the transforms with Taylor’s expansions that agree up to a certain order. Then, the expected waiting times can be computed using transform inversion, because they are simply functions of two moments. This study also discusses the special case involving zero switchover times. The strongest benefit of the pseudotransform inversion algorithm over current approaches is that it significantly decreases the computation effort when the number of queues is large. Several numerical examples are devised to validate our approach and show its efficiency in analyzing polling models. The results show that the pseudotransform inversion algorithm is indeed quite efficient for analyzing polling stations. Although polling models are the best example that we have found to date, in any situation where the quantity to be computed depends only on the first several moments of the input distributions, the pseudotransform inversion algorithm holds promise as a computational algorithm.

Keywords: transform inversion; polling models; pseudo-transforms; cyclic servers (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://doi.org/10.1287/ijoc.2018.0844 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:31:y:2019:i:3:p:515-526

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().