IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v63y2015i5p1213-1226.html
   My bibliography  Save this article

Necessity of Future Information in Admission Control

Author

Listed:
  • Kuang Xu

    (Graduate School of Business, Stanford University, Stanford, California 94305)

Abstract

We study the necessity of predictive information in a class of queueing admission control problems, where a system manager is allowed to divert incoming jobs up to a fixed rate, in order to minimize the queueing delay experienced by the admitted jobs.Spencer et al. (2014) [Spencer J, Sudan M, Xu K (2014) Queuing with future information. Ann. Appl. Probab. 24(5):2091–2142.] show that the system’s delay performance can be significantly improved by having access to future information in the form of a lookahead window, during which the times of future arrivals and services are revealed. They prove that, while delay under an optimal online policy diverges to infinity in the heavy-traffic regime, it can stay bounded by making use of future information. However, the diversion polices of Spencer et al. (2014) require the length of the lookahead window to grow to infinity at a nontrivial rate in the heavy-traffic regime, and it remained open whether substantial performance improvement could still be achieved with less future information.We resolve this question to a large extent by establishing an asymptotically tight lower bound on how much future information is necessary to achieve superior performance, which matches the upper bound of Spencer et al. (2014) up to a constant multiplicative factor. Our result hence demonstrates that the system’s heavy-traffic delay performance is highly sensitive to the amount of future information available. Our proof is based on analyzing certain excursion probabilities of the input sample paths, and exploiting a connection between a policy’s diversion decisions and subsequent server idling, which may be of independent interest for related dynamic resource allocation problems.

Suggested Citation

  • Kuang Xu, 2015. "Necessity of Future Information in Admission Control," Operations Research, INFORMS, vol. 63(5), pages 1213-1226, October.
  • Handle: RePEc:inm:oropre:v:63:y:2015:i:5:p:1213-1226
    DOI: 10.1287/opre.2015.1406
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.2015.1406
    Download Restriction: no

    File URL: https://libkey.io/10.1287/opre.2015.1406?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. Uri Yechiali, 1971. "On Optimal Balking Rules and Toll Charges in the GI / M /1 Queuing Process," Operations Research, INFORMS, vol. 19(2), pages 349-370, April.
    2. Vijay V. Desai & Vivek F. Farias & Ciamac C. Moallemi, 2012. "Pathwise Optimization for Optimal Stopping Problems," Management Science, INFORMS, vol. 58(12), pages 2292-2308, December.
    3. Kim, Seung-Chul & Horowitz, Ira, 2002. "Scheduling hospital services: the efficacy of elective-surgery quotas," Omega, Elsevier, vol. 30(5), pages 335-346, October.
    4. David B. Brown & James E. Smith & Peng Sun, 2010. "Information Relaxations and Duality in Stochastic Dynamic Programs," Operations Research, INFORMS, vol. 58(4-part-1), pages 785-801, August.
    5. Juan González-Hernández & César Villarreal, 2011. "Optimal policies for constrained average-cost Markov decision processes," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 19(1), pages 107-120, July.
    6. Marshall Fisher & Ananth Raman, 1996. "Reducing the Cost of Demand Uncertainty Through Accurate Response to Early Sales," Operations Research, INFORMS, vol. 44(1), pages 87-99, 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. Legros, Benjamin, 2021. "Routing analyses for call centers with human and automated services," International Journal of Production Economics, Elsevier, vol. 240(C).
    2. Kuang Xu & Carri W. Chan, 2016. "Using Future Information to Reduce Waiting Times in the Emergency Department via Diversion," Manufacturing & Service Operations Management, INFORMS, vol. 18(3), pages 314-331, July.
    3. Benjamin Legros, 2021. "Routing analyses for call centers with human and automated services," Post-Print hal-03605426, HAL.
    4. Abhishek Abhishek & Benjamin Legros & Jan Fransoo, 2021. "Performance Evaluation of Stochastic Systems with Dedicated Delivery Bays and General On-Street Parking," Post-Print hal-03605434, HAL.
    5. Abhishek, & Legros, Benjamin & Fransoo, Jan C., 2021. "Performance evaluation of stochastic systems with dedicated delivery bays and general on-street parking," Other publications TiSEM 09ed9572-d59c-4f28-a9c4-b, Tilburg University, School of Economics and Management.
    6. Kuang Xu & Yuan Zhong, 2020. "Information and Memory in Dynamic Resource Allocation," Operations Research, INFORMS, vol. 68(6), pages 1698-1715, November.
    7. Kraig Delana & Nicos Savva & Tolga Tezcan, 2021. "Proactive Customer Service: Operational Benefits and Economic Frictions," Manufacturing & Service Operations Management, INFORMS, vol. 23(1), pages 70-87, 1-2.

    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. Helin Zhu & Fan Ye & Enlu Zhou, 2013. "Fast Estimation of True Bounds on Bermudan Option Prices under Jump-diffusion Processes," Papers 1305.4321, arXiv.org.
    2. Helin Zhu & Fan Ye & Enlu Zhou, 2015. "Fast estimation of true bounds on Bermudan option prices under jump-diffusion processes," Quantitative Finance, Taylor & Francis Journals, vol. 15(11), pages 1885-1900, November.
    3. Nadarajah, Selvaprabu & Margot, François & Secomandi, Nicola, 2017. "Comparison of least squares Monte Carlo methods with applications to energy real options," European Journal of Operational Research, Elsevier, vol. 256(1), pages 196-204.
    4. Alessio Trivella & Danial Mohseni-Taheri & Selvaprabu Nadarajah, 2023. "Meeting Corporate Renewable Power Targets," Management Science, INFORMS, vol. 69(1), pages 491-512, January.
    5. Christian Bender & Christian Gaertner & Nikolaus Schweizer, 2016. "Pathwise Iteration for Backward SDEs," Papers 1605.07500, arXiv.org, revised Jun 2016.
    6. Santiago R. Balseiro & David B. Brown, 2019. "Approximations to Stochastic Dynamic Programs via Information Relaxation Duality," Operations Research, INFORMS, vol. 67(2), pages 577-597, March.
    7. Daniel R. Jiang & Lina Al-Kanj & Warren B. Powell, 2020. "Optimistic Monte Carlo Tree Search with Sampled Information Relaxation Dual Bounds," Operations Research, INFORMS, vol. 68(6), pages 1678-1697, November.
    8. Qihang Lin & Selvaprabu Nadarajah & Negar Soheili, 2020. "Revisiting Approximate Linear Programming: Constraint-Violation Learning with Applications to Inventory Control and Energy Storage," Management Science, INFORMS, vol. 66(4), pages 1544-1562, April.
    9. David B. Brown & Martin B. Haugh, 2017. "Information Relaxation Bounds for Infinite Horizon Markov Decision Processes," Operations Research, INFORMS, vol. 65(5), pages 1355-1379, October.
    10. Joshi, Mark & Tang, Robert, 2014. "Effective sub-simulation-free upper bounds for the Monte Carlo pricing of callable derivatives and various improvements to existing methodologies," Journal of Economic Dynamics and Control, Elsevier, vol. 40(C), pages 25-45.
    11. Georgia Perakis & Guillaume Roels, 2008. "Regret in the Newsvendor Model with Partial Information," Operations Research, INFORMS, vol. 56(1), pages 188-203, February.
    12. Sohn, So Young & Lim, Michael, 2008. "The effect of forecasting and information sharing in SCM for multi-generation products," European Journal of Operational Research, Elsevier, vol. 186(1), pages 276-287, April.
    13. Piotr Więcek & Eitan Altman & Arnob Ghosh, 2016. "Mean-Field Game Approach to Admission Control of an M/M/ $$\infty $$ ∞ Queue with Shared Service Cost," Dynamic Games and Applications, Springer, vol. 6(4), pages 538-566, December.
    14. Mark E. Ferguson & Gregory A. DeCroix & Paul H. Zipkin, 2005. "Commitment decisions with partial information updating," Naval Research Logistics (NRL), John Wiley & Sons, vol. 52(8), pages 780-795, December.
    15. repec:ipg:wpaper:2013-014 is not listed on IDEAS
    16. Jia Liu & Cuixia Li, 2023. "Dynamic Game Analysis on Cooperative Advertising Strategy in a Manufacturer-Led Supply Chain with Risk Aversion," Mathematics, MDPI, vol. 11(3), pages 1-24, January.
    17. Fajardo, Val Andrei & Drekic, Steve, 2015. "Controlling the workload of M/G/1 queues via the q-policy," European Journal of Operational Research, Elsevier, vol. 243(2), pages 607-617.
    18. He, Haonan & Wang, Shanyong, 2019. "Cost-benefit associations in consumer inventory problem with uncertain benefit," Journal of Retailing and Consumer Services, Elsevier, vol. 51(C), pages 271-284.
    19. Işık Biçer & Florian Lücker & Tamer Boyacı, 2022. "Beyond Retail Stores: Managing Product Proliferation along the Supply Chain," Production and Operations Management, Production and Operations Management Society, vol. 31(3), pages 1135-1156, March.
    20. Weng, Z. Kevin, 2004. "Coordinating order quantities between the manufacturer and the buyer: A generalized newsvendor model," European Journal of Operational Research, Elsevier, vol. 156(1), pages 148-161, July.
    21. Steffen Heider & Jan Schoenfelder & Thomas Koperna & Jens O. Brunner, 2022. "Balancing control and autonomy in master surgery scheduling: Benefits of ICU quotas for recovery units," Health Care Management Science, Springer, vol. 25(2), pages 311-332, June.

    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:oropre:v:63:y:2015:i:5:p:1213-1226. 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.