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

Information and Memory in Dynamic Resource Allocation

Author

Listed:
  • Kuang Xu

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

  • Yuan Zhong

    (Booth School of Business, University of Chicago, Chicago, Illinois 60637)

Abstract

We propose a general framework, dubbed stochastic processing under imperfect information , to study the impact of information constraints and memories on dynamic resource allocation. The framework involves a stochastic processing network (SPN) scheduling problem in which the scheduler may access the system state only through a noisy channel, and resource allocation decisions must be carried out through the interaction between an encoding policy (that observes the state) and allocation policy (that chooses the allocation). Applications in the management of large-scale data centers and human-in-the-loop service systems are among our chief motivations. We quantify the degree to which information constraints reduce the size of the capacity region in general SPNs and how such reduction depends on the amount of memories available to the encoding and allocation policies. Using a novel metric, capacity factor , our main theorem characterizes the reduction in capacity region (under “optimal” policies) for all nondegenerate channels and across almost all combinations of memory sizes. Notably, the theorem demonstrates, in substantial generality, that (1) the presence of a noisy channel always reduces capacity, (2) more memory for the allocation policy always improves capacity, and (3) more memory for the encoding policy has little to no effect on capacity. Finally, all of our positive (achievability) results are established through constructive, implementable policies. Our proof program involves the development of a host of new techniques, largely from first principles, by combining ideas from information theory, learning and queuing theory. As a submodule of one of the policies proposed, we create a simple yet powerful generalization of the maximum-weight (max-weight) policy, in which individual Markov chains are selected dynamically, in a manner analogous to how schedules are used in a conventional max-weight policy.

Suggested Citation

  • Kuang Xu & Yuan Zhong, 2020. "Information and Memory in Dynamic Resource Allocation," Operations Research, INFORMS, vol. 68(6), pages 1698-1715, November.
  • Handle: RePEc:inm:oropre:v:68:y:2020:i:6:p:1698-1715
    DOI: 10.1287/opre.2019.1940
    as

    Download full text from publisher

    File URL: https://doi.org/10.1287/opre.2019.1940
    Download Restriction: no

    File URL: https://libkey.io/10.1287/opre.2019.1940?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. Avishai Mandelbaum & Alexander L. Stolyar, 2004. "Scheduling Flexible Servers with Convex Delay Costs: Heavy-Traffic Optimality of the Generalized cμ-Rule," Operations Research, INFORMS, vol. 52(6), pages 836-855, December.
    2. Noah Gans & Ger Koole & Avishai Mandelbaum, 2003. "Telephone Call Centers: Tutorial, Review, and Research Prospects," Manufacturing & Service Operations Management, INFORMS, vol. 5(2), pages 79-141, September.
    3. Kuang Xu, 2015. "Necessity of Future Information in Admission Control," Operations Research, INFORMS, vol. 63(5), pages 1213-1226, October.
    4. J. G. Dai & Wuqin Lin, 2005. "Maximum Pressure Policies in Stochastic Processing Networks," Operations Research, INFORMS, vol. 53(2), pages 197-218, April.
    5. Jamol Pender & Richard Rand & Elizabeth Wesson, 2020. "A Stochastic Analysis of Queues with Customer Choice and Delayed Information," Mathematics of Operations Research, INFORMS, vol. 45(3), pages 1104-1126, August.
    6. Hong Chen & J. Michael Harrison & Avi Mandelbaum & Ann Van Ackere & Lawrence M. Wein, 1988. "Empirical Evaluation of a Queueing Network Model for Semiconductor Wafer Fabrication," Operations Research, INFORMS, vol. 36(2), pages 202-215, April.
    7. Alexander L. Stolyar, 2017. "Pull-based load distribution among heterogeneous parallel servers: the case of multiple routers," Queueing Systems: Theory and Applications, Springer, vol. 85(1), pages 31-65, February.
    8. Golshid Baharian & Tolga Tezcan, 2011. "Stability analysis of parallel server systems under longest queue first," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 74(2), pages 257-279, October.
    9. Amy R. Ward & Mor Armony, 2013. "Blind Fair Routing in Large-Scale Service Systems with Heterogeneous Customers and Servers," Operations Research, INFORMS, vol. 61(1), pages 228-243, February.
    10. J. Michael Harrison & Assaf Zeevi, 2005. "A Method for Staffing Large Call Centers Based on Stochastic Fluid Models," Manufacturing & Service Operations Management, INFORMS, vol. 7(1), pages 20-36, September.
    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. Zhong, Zhiheng & Cao, Ping, 2023. "Balanced routing with partial information in a distributed parallel many-server queueing system," European Journal of Operational Research, Elsevier, vol. 304(2), pages 618-633.

    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. Merve Bodur & James R. Luedtke, 2017. "Mixed-Integer Rounding Enhanced Benders Decomposition for Multiclass Service-System Staffing and Scheduling with Arrival Rate Uncertainty," Management Science, INFORMS, vol. 63(7), pages 2073-2091, July.
    2. Jinsheng Chen & Jing Dong & Pengyi Shi, 2020. "A survey on skill-based routing with applications to service operations management," Queueing Systems: Theory and Applications, Springer, vol. 96(1), pages 53-82, October.
    3. Achal Bassamboo & J. Michael Harrison & Assaf Zeevi, 2006. "Design and Control of a Large Call Center: Asymptotic Analysis of an LP-Based Method," Operations Research, INFORMS, vol. 54(3), pages 419-435, June.
    4. J. G. Dai & Tolga Tezcan, 2011. "State Space Collapse in Many-Server Diffusion Limits of Parallel Server Systems," Mathematics of Operations Research, INFORMS, vol. 36(2), pages 271-320, May.
    5. Adan, Ivo J.B.F. & Boon, Marko A.A. & Weiss, Gideon, 2019. "Design heuristic for parallel many server systems," European Journal of Operational Research, Elsevier, vol. 273(1), pages 259-277.
    6. Vijay Mehrotra & Kevin Ross & Geoff Ryder & Yong-Pin Zhou, 2012. "Routing to Manage Resolution and Waiting Time in Call Centers with Heterogeneous Servers," Manufacturing & Service Operations Management, INFORMS, vol. 14(1), pages 66-81, January.
    7. Noa Zychlinski, 2023. "Applications of fluid models in service operations management," Queueing Systems: Theory and Applications, Springer, vol. 103(1), pages 161-185, February.
    8. Wyean Chan & Ger Koole & Pierre L'Ecuyer, 2014. "Dynamic Call Center Routing Policies Using Call Waiting and Agent Idle Times," Manufacturing & Service Operations Management, INFORMS, vol. 16(4), pages 544-560, October.
    9. Tom F. Tan & Bradley R. Staats, 2020. "Behavioral Drivers of Routing Decisions: Evidence from Restaurant Table Assignment," Production and Operations Management, Production and Operations Management Society, vol. 29(4), pages 1050-1070, April.
    10. Tolga Tezcan & Banafsheh Behzad, 2012. "Robust Design and Control of Call Centers with Flexible Interactive Voice Response Systems," Manufacturing & Service Operations Management, INFORMS, vol. 14(3), pages 386-401, July.
    11. Achal Bassamboo & Assaf Zeevi, 2009. "On a Data-Driven Method for Staffing Large Call Centers," Operations Research, INFORMS, vol. 57(3), pages 714-726, June.
    12. Francis de Véricourt & Otis B. Jennings, 2008. "Dimensioning Large-Scale Membership Services," Operations Research, INFORMS, vol. 56(1), pages 173-187, February.
    13. 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.
    14. Gregory Dobson & Tolga Tezcan & Vera Tilson, 2013. "Optimal Workflow Decisions for Investigators in Systems with Interruptions," Management Science, INFORMS, vol. 59(5), pages 1125-1141, May.
    15. Rami Atar & Avi Mandelbaum & Gennady Shaikhet, 2009. "Simplified Control Problems for Multiclass Many-Server Queueing Systems," Mathematics of Operations Research, INFORMS, vol. 34(4), pages 795-812, November.
    16. Sigrún Andradóttir & Hayriye Ayhan & Douglas G. Down, 2007. "Compensating for Failures with Flexible Servers," Operations Research, INFORMS, vol. 55(4), pages 753-768, August.
    17. Alexander L. Stolyar & Tolga Tezcan, 2011. "Shadow-Routing Based Control of Flexible Multiserver Pools in Overload," Operations Research, INFORMS, vol. 59(6), pages 1427-1444, December.
    18. Cho, David D. & Stauffer, Jon M., 2022. "Tele-medicine question response service: Analysis of benefits and costs," Omega, Elsevier, vol. 111(C).
    19. Sunil Kumar & Ramandeep S. Randhawa, 2010. "Exploiting Market Size in Service Systems," Manufacturing & Service Operations Management, INFORMS, vol. 12(3), pages 511-526, September.
    20. Ward Whitt, 2006. "Staffing a Call Center with Uncertain Arrival Rate and Absenteeism," Production and Operations Management, Production and Operations Management Society, vol. 15(1), pages 88-102, March.

    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:68:y:2020:i:6:p:1698-1715. 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.