IDEAS home Printed from https://ideas.repec.org/a/inm/ormnsc/v65y2019i1p152-187.html
   My bibliography  Save this article

Robust Multiclass Queuing Theory for Wait Time Estimation in Resource Allocation Systems

Author

Listed:
  • Chaithanya Bandi

    (Kellogg School of Management, Northwestern University, Evanston, Illinois 60208)

  • Nikolaos Trichakis

    (MIT Sloan School of Management and Operations Research Center, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139)

  • Phebe Vayanos

    (Departments of Industrial and Systems Engineering and Computer Science and Center for Artificial Intelligence in Society, Viterbi School of Engineering, University of Southern California, Los Angeles, California 90089)

Abstract

In this paper, we study systems that allocate different types of scarce resources to heterogeneous allocatees based on predetermined priority rules—the U.S. deceased-donor kidney allocation system or the public housing program. We tackle the problem of estimating the wait time of an allocatee who possesses incomplete system information with regard, for example, to his relative priority, other allocatees’ preferences, and resource availability. We model such systems as multiclass, multiserver queuing systems that are potentially unstable or in transient regime. We propose a novel robust optimization solution methodology that builds on the assignment problem. For first-come, first-served systems, our approach yields a mixed-integer programming formulation. For the important case where there is a hierarchy in the resource types, we strengthen our formulation through a drastic variable reduction and also propose a highly scalable heuristic, involving only the solution of a convex optimization problem (usually a second-order cone problem). We back the heuristic with an approximation guarantee that becomes tighter for larger problem sizes. We illustrate the generalizability of our approach by studying systems that operate under different priority rules, such as class priority. Numerical studies demonstrate that our approach outperforms simulation. We showcase how our methodology can be applied to assist patients in the U.S. deceased-donor kidney waitlist. We calibrate our model using historical data to estimate patients’ wait times based on their kidney quality preferences, blood type, location, and rank in the waitlist.

Suggested Citation

  • Chaithanya Bandi & Nikolaos Trichakis & Phebe Vayanos, 2019. "Robust Multiclass Queuing Theory for Wait Time Estimation in Resource Allocation Systems," Management Science, INFORMS, vol. 65(1), pages 152-187, January.
  • Handle: RePEc:inm:ormnsc:v:65:y:2019:i:1:p:152-187
    DOI: 10.1287/mnsc.2017.2948
    as

    Download full text from publisher

    File URL: https://doi.org/10.1287/mnsc.2017.2948
    Download Restriction: no

    File URL: https://libkey.io/10.1287/mnsc.2017.2948?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. Ward Whitt & Wei You, 2018. "Using Robust Queueing to Expose the Impact of Dependence in Single-Server Queues," Operations Research, INFORMS, vol. 66(1), pages 184-199, January.
    2. Chaithanya Bandi & Dimitris Bertsimas & Nataly Youssef, 2015. "Robust Queueing Theory," Operations Research, INFORMS, vol. 63(3), pages 676-700, June.
    3. 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.
    4. Hamed Mamani & Shima Nassiri & Michael R. Wagner, 2017. "Closed-Form Solutions for Robust Inventory Management," Management Science, INFORMS, vol. 63(5), pages 1625-1643, May.
    5. Nan Kong & Andrew J. Schaefer & Brady Hunsaker & Mark S. Roberts, 2010. "Maximizing the Efficiency of the U.S. Liver Allocation System Through Region Design," Management Science, INFORMS, vol. 56(12), pages 2111-2122, December.
    6. Sang-Phil Kim & Diwakar Gupta & Ajay Israni & Bertram Kasiske, 2015. "Accept/decline decision module for the liver simulated allocation model," Health Care Management Science, Springer, vol. 18(1), pages 35-57, March.
    7. Mustafa Akan & Oguzhan Alagoz & Baris Ata & Fatih Safa Erenay & Adnan Said, 2012. "A Broader View of Designing the Liver Allocation System," Operations Research, INFORMS, vol. 60(4), pages 757-770, August.
    8. Michael H. Rothkopf & Shmuel S. Oren, 1979. "A Closure Approximation for the Nonstationary M/M/s Queue," Management Science, INFORMS, vol. 25(6), pages 522-534, June.
    9. Burhaneddin Sandıkçı & Lisa M. Maillart & Andrew J. Schaefer & Oguzhan Alagoz & Mark S. Roberts, 2008. "Estimating the Patient's Price of Privacy in Liver Transplantation," Operations Research, INFORMS, vol. 56(6), pages 1393-1410, December.
    10. William H. Kaczynski & Lawrence M. Leemis & John H. Drew, 2012. "Transient Queueing Analysis," INFORMS Journal on Computing, INFORMS, vol. 24(1), pages 10-28, February.
    11. Amedeo R. Odoni & Emily Roth, 1983. "An Empirical Investigation of the Transient Behavior of Stationary Queueing Systems," Operations Research, INFORMS, vol. 31(3), pages 432-455, June.
    12. Rouba Ibrahim & Mor Armony & Achal Bassamboo, 2017. "Does the Past Predict the Future? The Case of Delay Announcements in Service Systems," Management Science, INFORMS, vol. 63(6), pages 1762-1780, June.
    13. Xuanming Su & Stefanos A. Zenios, 2005. "Patient Choice in Kidney Allocation: A Sequential Stochastic Assignment Model," Operations Research, INFORMS, vol. 53(3), pages 443-455, June.
    14. Itai Gurvich & James Luedtke & Tolga Tezcan, 2010. "Staffing Call Centers with Uncertain Demand Forecasts: A Chance-Constrained Optimization Approach," Management Science, INFORMS, vol. 56(7), pages 1093-1115, July.
    15. Oguzhan Alagoz & Lisa M. Maillart & Andrew J. Schaefer & Mark S. Roberts, 2007. "Determining the Acceptance of Cadaveric Livers Using an Implicit Model of the Waiting List," Operations Research, INFORMS, vol. 55(1), pages 24-36, February.
    16. Grassmann, WK, 1980. "Transient and steady state results for two parallel queues," Omega, Elsevier, vol. 8(1), pages 105-112.
    17. Xuanming Su & Stefanos A. Zenios, 2006. "Recipient Choice Can Address the Efficiency-Equity Trade-off in Kidney Transplantation: A Mechanism Design Model," Management Science, INFORMS, vol. 52(11), pages 1647-1660, November.
    18. T. C. T. Kotiah, 1978. "Approximate Transient Analysis of Some Queuing Systems," Operations Research, INFORMS, vol. 26(2), pages 333-346, April.
    19. 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.
    20. Dimitris Bertsimas & Vivek F. Farias & Nikolaos Trichakis, 2013. "Fairness, Efficiency, and Flexibility in Organ Allocation for Kidney Transplantation," Operations Research, INFORMS, vol. 61(1), pages 73-87, February.
    21. S. C. Moore, 1975. "Approximating the Behavior of Nonstationary Single-Server Queues," Operations Research, INFORMS, vol. 23(5), pages 1011-1032, October.
    22. W. David Kelton & Averill M. Law, 1985. "The Transient Behavior of the M / M / s Queue, with Implications for Steady-State Simulation," Operations Research, INFORMS, vol. 33(2), pages 378-396, April.
    23. Chaithanya Bandi & Dimitris Bertsimas & Nataly Youssef, 2018. "Robust transient analysis of multi-server queueing systems and feed-forward networks," Queueing Systems: Theory and Applications, Springer, vol. 89(3), pages 351-413, August.
    24. Burhaneddin Sandıkçı & Lisa M. Maillart & Andrew J. Schaefer & Mark S. Roberts, 2013. "Alleviating the Patient's Price of Privacy Through a Partially Observable Waiting List," Management Science, INFORMS, vol. 59(8), pages 1836-1854, August.
    25. Erica L. Plambeck & Amy R. Ward, 2006. "Optimal Control of a High-Volume Assemble-to-Order System," Mathematics of Operations Research, INFORMS, vol. 31(3), pages 453-477, August.
    26. Chris P. Lee & Glenn M. Chertow & Stefanos A. Zenios, 2008. "Optimal Initiation and Management of Dialysis Therapy," Operations Research, INFORMS, vol. 56(6), pages 1428-1449, December.
    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. Ali Ala & Morteza Yazdani & Mohsen Ahmadi & Aida Poorianasab & Mahdi Yousefi Nejad Attari, 2023. "An efficient healthcare chain design for resolving the patient scheduling problem: queuing theory and MILP-ASA optimization approach," Annals of Operations Research, Springer, vol. 328(1), pages 3-33, September.
    2. Itai Gurvich & John J. Hasenbein, 2022. "Policy robustness in queueing networks," Queueing Systems: Theory and Applications, Springer, vol. 100(3), pages 425-427, April.

    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. Ozge Ceren Ersoy & Diwakar Gupta & Timothy Pruett, 2021. "A critical look at the U.S. deceased‐donor organ procurement and utilization system," Naval Research Logistics (NRL), John Wiley & Sons, vol. 68(1), pages 3-29, February.
    2. Sepehr Nemati & Zeynep G. Icten & Lisa M. Maillart & Andrew J. Schaefer, 2020. "Mitigating Information Asymmetry in Liver Allocation," INFORMS Journal on Computing, INFORMS, vol. 32(2), pages 234-248, April.
    3. Baris Ata & Yichuan Ding & Stefanos Zenios, 2021. "An Achievable-Region-Based Approach for Kidney Allocation Policy Design with Endogenous Patient Choice," Manufacturing & Service Operations Management, INFORMS, vol. 23(1), pages 36-54, 1-2.
    4. Kargar, Bahareh & Pishvaee, Mir Saman & Jahani, Hamed & Sheu, Jiuh-Biing, 2020. "Organ transportation and allocation problem under medical uncertainty: A real case study of liver transplantation," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 134(C).
    5. Barış Ata & Anton Skaro & Sridhar Tayur, 2017. "OrganJet: Overcoming Geographical Disparities in Access to Deceased Donor Kidneys in the United States," Management Science, INFORMS, vol. 63(9), pages 2776-2794, September.
    6. Sait Tunç & Burhaneddin Sandıkçı & Bekir Tanrıöver, 2022. "A Simple Incentive Mechanism to Alleviate the Burden of Organ Wastage in Transplantation," Management Science, INFORMS, vol. 68(8), pages 5980-6002, August.
    7. Sahar Ahmadvand & Mir Saman Pishvaee, 2018. "An efficient method for kidney allocation problem: a credibility-based fuzzy common weights data envelopment analysis approach," Health Care Management Science, Springer, vol. 21(4), pages 587-603, December.
    8. Guihua Wang & Ronghuo Zheng & Tinglong Dai, 2022. "Does Transportation Mean Transplantation? Impact of New Airline Routes on Sharing of Cadaveric Kidneys," Management Science, INFORMS, vol. 68(5), pages 3660-3679, May.
    9. Chaithanya Bandi & Dimitris Bertsimas & Nataly Youssef, 2018. "Robust transient analysis of multi-server queueing systems and feed-forward networks," Queueing Systems: Theory and Applications, Springer, vol. 89(3), pages 351-413, August.
    10. Farhad Hasankhani & Amin Khademi, 2021. "Is it Time to Include Post‐Transplant Survival in Heart Transplantation Allocation Rules?," Production and Operations Management, Production and Operations Management Society, vol. 30(8), pages 2653-2671, August.
    11. Tinglong Dai & Ronghuo Zheng & Katia Sycara, 2020. "Jumping the Line, Charitably: Analysis and Remedy of Donor-Priority Rule," Management Science, INFORMS, vol. 66(2), pages 622-641, February.
    12. Sakine Batun & Andrew J. Schaefer & Atul Bhandari & Mark S. Roberts, 2018. "Optimal Liver Acceptance for Risk-Sensitive Patients," Service Science, INFORMS, vol. 10(3), pages 320-333, September.
    13. Dimitris Bertsimas & Vivek F. Farias & Nikolaos Trichakis, 2013. "Fairness, Efficiency, and Flexibility in Organ Allocation for Kidney Transplantation," Operations Research, INFORMS, vol. 61(1), pages 73-87, February.
    14. Can Zhang & Atalay Atasu & Turgay Ayer & L. Beril Toktay, 2020. "Truthful Mechanisms for Medical Surplus Product Allocation," Manufacturing & Service Operations Management, INFORMS, vol. 22(4), pages 735-753, July.
    15. Misra, Akansha & Saranga, Haritha & Tripathi, Rajeev R, 2022. "Channel choice and incentives in the cadaveric organ supply chain," European Journal of Operational Research, Elsevier, vol. 302(3), pages 1202-1214.
    16. Ting-Yu Ho & Shan Liu & Zelda B. Zabinsky, 2019. "A Multi-Fidelity Rollout Algorithm for Dynamic Resource Allocation in Population Disease Management," Health Care Management Science, Springer, vol. 22(4), pages 727-755, December.
    17. Li, Mengling & Riyanto, Yohanes E. & Xu, Menghan, 2023. "Prioritized organ allocation rules under compatibility constraints," Games and Economic Behavior, Elsevier, vol. 141(C), pages 403-427.
    18. Turgay Ayer & Can Zhang & Anthony Bonifonte & Anne C. Spaulding & Jagpreet Chhatwal, 2019. "Prioritizing Hepatitis C Treatment in U.S. Prisons," Operations Research, INFORMS, vol. 67(3), pages 853-873, May.
    19. Mustafa Akan & Oguzhan Alagoz & Baris Ata & Fatih Safa Erenay & Adnan Said, 2012. "A Broader View of Designing the Liver Allocation System," Operations Research, INFORMS, vol. 60(4), pages 757-770, August.
    20. Zahra Gharibi & Michael Hahsler, 2021. "A Simulation-Based Optimization Model to Study the Impact of Multiple-Region Listing and Information Sharing on Kidney Transplant Outcomes," IJERPH, MDPI, vol. 18(3), pages 1-20, January.

    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:ormnsc:v:65:y:2019:i:1:p:152-187. 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.