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

MAD Dispersion Measure Makes Extremal Queue Analysis Simple

Author

Listed:
  • Wouter van Eekelen

    (Department of Econometrics and Operations Research, Tilburg University, 5037 AB Tilburg, Netherlands)

  • Dick den Hertog

    (Amsterdam Business School, University of Amsterdam, 1012 WX Amsterdam, Netherlands)

  • Johan S.H. van Leeuwaarden

    (Department of Econometrics and Operations Research, Tilburg University, 5037 AB Tilburg, Netherlands; Department of Mathematics and Computer Science, Eindhoven University of Technology, 5612 AZ Eindhoven, Netherlands)

Abstract

A notorious problem in queueing theory is to compute the worst possible performance of the GI/G/1 queue under mean-dispersion constraints for the interarrival- and service-time distributions. We address this extremal queue problem by measuring dispersion in terms of mean absolute deviation (MAD) instead of the more conventional variance, making available methods for distribution-free analysis. Combined with random walk theory, we obtain explicit expressions for the extremal interarrival- and service-time distributions and, hence, the best possible upper bounds for all moments of the waiting time. We also obtain tight lower bounds that, together with the upper bounds, provide robust performance intervals. We show that all bounds are computationally tractable and remain sharp also when the mean and MAD are not known precisely but are estimated based on available data instead. Summary of Contribution: Queueing theory is a classic OR topic with a central role for the GI/G/1 queue. Although this queueing system is conceptually simple, it is notoriously hard to determine the worst-case expected waiting time when only knowing the first two moments of the interarrival- and service-time distributions. In this setting, the exact form of the extremal distribution can only be determined numerically as the solution to a nonconvex nonlinear optimization problem. Our paper demonstrates that using mean absolute deviation (MAD) instead of variance alleviates the computational intractability of the extremal GI/G/1 queue problem, enabling us to state the worst-case distributions explicitly.

Suggested Citation

  • Wouter van Eekelen & Dick den Hertog & Johan S.H. van Leeuwaarden, 2022. "MAD Dispersion Measure Makes Extremal Queue Analysis Simple," INFORMS Journal on Computing, INFORMS, vol. 34(3), pages 1681-1692, May.
  • Handle: RePEc:inm:orijoc:v:34:y:2022:i:3:p:1681-1692
    DOI: 10.1287/ijoc.2021.1130
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/ijoc.2021.1130
    Download Restriction: no

    File URL: https://libkey.io/10.1287/ijoc.2021.1130?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. Karthik Natarajan & Melvyn Sim & Joline Uichanco, 2018. "Asymmetry and Ambiguity in Newsvendor Models," Management Science, INFORMS, vol. 64(7), pages 3146-3167, July.
    2. Georgia Perakis & Guillaume Roels, 2008. "Regret in the Newsvendor Model with Partial Information," Operations Research, INFORMS, vol. 56(1), pages 188-203, February.
    3. Paul Glasserman, 1997. "Bounds and Asymptotics for Planning Critical Safety Stocks," Operations Research, INFORMS, vol. 45(2), pages 244-257, April.
    4. James R. Bradley & Peter W. Glynn, 2002. "Managing Capacity and Inventory Jointly in Manufacturing Systems," Management Science, INFORMS, vol. 48(2), pages 273-288, February.
    5. A. E. Eckberg, 1977. "Sharp Bounds on Laplace-Stieltjes Transforms, with Applications to Various Queueing Problems," Mathematics of Operations Research, INFORMS, vol. 2(2), pages 135-142, May.
    6. Xin, Linwei & Goldberg, David A., 2021. "Time (in)consistency of multistage distributionally robust inventory models with moment constraints," European Journal of Operational Research, Elsevier, vol. 289(3), pages 1127-1141.
    7. Yan Chen & Ward Whitt, 2020. "Algorithms for the upper bound mean waiting time in the GI/GI/1 queue," Queueing Systems: Theory and Applications, Springer, vol. 94(3), pages 327-356, April.
    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. van Eekelen, Wouter, 2023. "Distributionally robust views on queues and related stochastic models," Other publications TiSEM 9b99fc05-9d68-48eb-ae8c-9, Tilburg University, School of Economics and Management.

    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. van Eekelen, Wouter, 2023. "Distributionally robust views on queues and related stochastic models," Other publications TiSEM 9b99fc05-9d68-48eb-ae8c-9, Tilburg University, School of Economics and Management.
    2. Roos, Ernst & Brekelmans, Ruud & van Eekelen, Wouter & den Hertog, Dick & van Leeuwaarden, Johan S.H., 2022. "Tight tail probability bounds for distribution-free decision making," European Journal of Operational Research, Elsevier, vol. 299(3), pages 931-944.
    3. Bradley, James R., 2005. "Optimal control of a dual service rate M/M/1 production-inventory model," European Journal of Operational Research, Elsevier, vol. 161(3), pages 812-837, March.
    4. Josh Reed & Bo Zhang, 2017. "Managing capacity and inventory jointly for multi-server make-to-stock queues," Queueing Systems: Theory and Applications, Springer, vol. 86(1), pages 61-94, June.
    5. Anh Ninh & Honggang Hu & David Allen, 2019. "Robust newsvendor problems: effect of discrete demands," Annals of Operations Research, Springer, vol. 275(2), pages 607-621, April.
    6. David A. Goldberg & Martin I. Reiman & Qiong Wang, 2021. "A Survey of Recent Progress in the Asymptotic Analysis of Inventory Systems," Production and Operations Management, Production and Operations Management Society, vol. 30(6), pages 1718-1750, June.
    7. Bai, Qingguo & Xu, Jianteng & Gong, Yeming & Chauhan, Satyaveer S., 2022. "Robust decisions for regulated sustainable manufacturing with partial demand information: Mandatory emission capacity versus emission tax," European Journal of Operational Research, Elsevier, vol. 298(3), pages 874-893.
    8. Rongchuan He & Ye Lu, 2021. "A Robust Price‐Setting Newsvendor Problem," Production and Operations Management, Production and Operations Management Society, vol. 30(1), pages 276-292, January.
    9. Opher Baron, 2008. "Regulated Random Walks and the LCFS Backlog Probability: Analysis and Application," Operations Research, INFORMS, vol. 56(2), pages 471-486, April.
    10. Andrew F. Siegel & Michael R. Wagner, 2021. "Profit Estimation Error in the Newsvendor Model Under a Parametric Demand Distribution," Management Science, INFORMS, vol. 67(8), pages 4863-4879, August.
    11. Rahimian, Hamed & Bayraksan, Güzin & Homem-de-Mello, Tito, 2019. "Controlling risk and demand ambiguity in newsvendor models," European Journal of Operational Research, Elsevier, vol. 279(3), pages 854-868.
    12. Zhi Chen & Weijun Xie, 2021. "Regret in the Newsvendor Model with Demand and Yield Randomness," Production and Operations Management, Production and Operations Management Society, vol. 30(11), pages 4176-4197, November.
    13. Martín Egozcue & Xu Guo & Wing-Keung Wong, 2015. "Optimal output for the regret-averse competitive firm under price uncertainty," Eurasian Economic Review, Springer;Eurasia Business and Economics Society, vol. 5(2), pages 279-295, December.
    14. Dimitris Bertsimas & Ioannis Ch. Paschalidis, 2001. "Probabilistic Service Level Guarantees in Make-to-Stock Manufacturing Systems," Operations Research, INFORMS, vol. 49(1), pages 119-133, February.
    15. Jodlbauer, Herbert & Altendorfer, Klaus, 2010. "Trade-off between capacity invested and inventory needed," European Journal of Operational Research, Elsevier, vol. 203(1), pages 118-133, May.
    16. Serrano, Breno & Minner, Stefan & Schiffer, Maximilian & Vidal, Thibaut, 2024. "Bilevel optimization for feature selection in the data-driven newsvendor problem," European Journal of Operational Research, Elsevier, vol. 315(2), pages 703-714.
    17. Peng Hu & Feng Chu & Yunfei Fang & Peng Wu, 2022. "Novel distribution-free model and method for stochastic disassembly line balancing with limited distributional information," Journal of Combinatorial Optimization, Springer, vol. 43(5), pages 1423-1446, July.
    18. Athanassoglou, Stergios & Brams, Steven J. & Sethuraman, Jay, 2008. "Minimizing regret when dissolving a partnership," MPRA Paper 12776, University Library of Munich, Germany.
    19. Qiu, Ruozhen & Sun, Minghe & Lim, Yun Fong, 2017. "Optimizing (s, S) policies for multi-period inventory models with demand distribution uncertainty: Robust dynamic programing approaches," European Journal of Operational Research, Elsevier, vol. 261(3), pages 880-892.
    20. Woonghee Tim Huh & Ganesh Janakiraman & Mahesh Nagarajan, 2016. "Capacitated Multiechelon Inventory Systems: Policies and Bounds," Manufacturing & Service Operations Management, INFORMS, vol. 18(4), pages 570-584, October.

    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:34:y:2022:i:3:p:1681-1692. 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.