IDEAS home Printed from https://ideas.repec.org/a/inm/orijoc/v31y2019i3p515-526.html
   My bibliography  Save this article

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

Author

Listed:
  • Wu-Lin Chen

    (Department of Computer Science and Information Management, Providence University, Taichung City, 43301, Taiwan (Republic of China))

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.

Suggested Citation

  • Wu-Lin Chen, 2019. "Computing the Moments of Polling Models with Batch Poisson Arrivals by Transform Inversion," INFORMS Journal on Computing, INFORMS, vol. 31(3), pages 515-526, July.
    • Handle: RePEc:inm:orijoc:v:31:y:2019:i:3:p:515-526
    DOI: 10.1287/ijoc.2018.0844
    as

    Download full text from publisher

    File URL: https://doi.org/10.1287/ijoc.2018.0844
    Download Restriction: no
    File URL: https://libkey.io/10.1287/ijoc.2018.0844?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Michel Scholl & Leonard Kleinrock, 1983. "On the M / G /1 Queue with Rest Periods and Certain Service-Independent Queueing Disciplines," Operations Research, INFORMS, vol. 31(4), pages 705-719, August.
    2. S. W. Fuhrmann & Robert B. Cooper, 1985. "Stochastic Decompositions in the M / G /1 Queue with Generalized Vacations," Operations Research, INFORMS, vol. 33(5), pages 1117-1129, October.
    3. Gagan L. Choudhury & David M. Lucantoni, 1996. "Numerical Computation of the Moments of a Probability Distribution from its Transform," Operations Research, INFORMS, vol. 44(2), pages 368-381, April.
    4. Paul H. Zipkin, 1986. "Models for Design and Control of Stochastic, Multi-Item Batch Production Systems," Operations Research, INFORMS, vol. 34(1), pages 91-104, February.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Vladimir Vishnevsky & Olga Semenova, 2021. "Polling Systems and Their Application to Telecommunication Networks," Mathematics, MDPI, vol. 9(2), pages 1-30, January.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. P. H. Brill & C. M. Harris, 1992. "Waiting times for M/G/1 queues with service‐time or delay‐dependent server vacations," Naval Research Logistics (NRL), John Wiley & Sons, vol. 39(6), pages 775-787, October.
    2. Offer Kella & Uri Yechiali, 1988. "Priorities in M/G/1 queue with server vacations," Naval Research Logistics (NRL), John Wiley & Sons, vol. 35(1), pages 23-34, February.
    3. B. Kumar & D. Arivudainambi & A. Krishnamoorthy, 2006. "Some results on a generalized M/G/1 feedback queue with negative customers," Annals of Operations Research, Springer, vol. 143(1), pages 277-296, March.
    4. Jacob K. Daniel & R. Ramanarayanan, 1988. "An (s,S) inventory system with rest periods to the server," Naval Research Logistics (NRL), John Wiley & Sons, vol. 35(1), pages 119-123, February.
    5. Dimitris Bertsimas & José Niño-Mora, 1996. "Optimization of multiclass queueing networks with changeover times via the achievable region method: Part II, the multi-station case," Economics Working Papers 314, Department of Economics and Business, Universitat Pompeu Fabra, revised Aug 1998.
    6. Izak Duenyas & Diwakar Gupta & Tava Lennon Olsen, 1998. "Control of a Single-Server Tandem Queueing System with Setups," Operations Research, INFORMS, vol. 46(2), pages 218-230, April.
    7. B. Krishna Kumar & S. Pavai Madheswari & S. Anantha Lakshmi, 2011. "Queuing system with state-dependent controlled batch arrivals and server under maintenance," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 19(2), pages 351-379, December.
    8. E. Carrizosa & E. Conde & M. Muñoz-Márquez, 1998. "Admission Policies in Loss Queueing Models with Heterogeneous Arrivals," Management Science, INFORMS, vol. 44(3), pages 311-320, March.
    9. Sem Borst & Onno Boxma, 2018. "Polling: past, present, and perspective," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 26(3), pages 335-369, October.
    10. Dimitris Bertsimas & José Niño-Mora, 1999. "Optimization of Multiclass Queueing Networks with Changeover Times Via the Achievable Region Approach: Part I, The Single-Station Case," Mathematics of Operations Research, INFORMS, vol. 24(2), pages 306-330, May.
    11. Priyanka Kalita & Gautam Choudhury & Dharmaraja Selvamuthu, 2020. "Analysis of Single Server Queue with Modified Vacation Policy," Methodology and Computing in Applied Probability, Springer, vol. 22(2), pages 511-553, June.
    12. George C. Mytalas & Michael A. Zazanis, 2022. "Service with a queue and a random capacity cart: random processing batches and E-limited policies," Annals of Operations Research, Springer, vol. 317(1), pages 147-178, October.
    13. Wilhelm, W. E. & Som, Pradip, 1998. "Analysis of a single-stage, single-product, stochastic, MRP-controlled assembly system," European Journal of Operational Research, Elsevier, vol. 108(1), pages 74-93, July.
    14. Madhu Jain & Sandeep Kaur & Parminder Singh, 2021. "Supplementary variable technique (SVT) for non-Markovian single server queue with service interruption (QSI)," Operational Research, Springer, vol. 21(4), pages 2203-2246, December.
    15. S. Rajagopalan, 2002. "Make to Order or Make to Stock: Model and Application," Management Science, INFORMS, vol. 48(2), pages 241-256, February.
    16. Ioannis Dimitriou, 2016. "Queueing analysis of the DRX power saving mechanism in fault-tolerant 3GPP LTE wireless networks," Annals of Operations Research, Springer, vol. 239(2), pages 521-552, April.
    17. Yi Peng & Jinbiao Wu, 2020. "A Lévy-Driven Stochastic Queueing System with Server Breakdowns and Vacations," Mathematics, MDPI, vol. 8(8), pages 1-12, July.
    18. Paul Glasserman & Yashan Wang, 1998. "Leadtime-Inventory Trade-Offs in Assemble-to-Order Systems," Operations Research, INFORMS, vol. 46(6), pages 858-871, December.
    19. Jianjun Li & Liwei Liu & Tao Jiang, 2018. "Analysis of an M/G/1 queue with vacations and multiple phases of operation," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 87(1), pages 51-72, February.
    20. Zsolt Saffer & Sergey Andreev & Yevgeni Koucheryavy, 2016. "$$M/D^{[y]}/1$$ M / D [ y ] / 1 Periodically gated vacation model and its application to IEEE 802.16 network," Annals of Operations Research, Springer, vol. 239(2), pages 497-520, April.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:orijoc:v:31:y:2019:i:3:p:515-526. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.