IDEAS home Printed from https://ideas.repec.org/a/wly/navres/v57y2010i3p225-236.html
   My bibliography  Save this article

An approximate dynamic programing approach to the development of heuristics for the scheduling of impatient jobs in a clearing system

Author

Listed:
  • Dong Li
  • Kevin D. Glazebrook

Abstract

A single server is faced with a collection of jobs of varying duration and urgency. Each job has a random lifetime during which it is available for nonpreemptive service. Should a job's lifetime expire before its service begins then it is lost from the system unserved. The goal is to schedule the jobs for service to maximize the expected number served to completion. Two heuristics have been proposed in the literature. One (labeled πS) operates a static priority among the job classes and works well in a “no premature job loss” limit, whereas the second (πM) is a myopic heuristic which works well when lifetimes are short. Both can exhibit poor performance for problems at some distance from the regimes for which they were designed. We develop a robustly good heuristic by an approximative approach to the application of a policy improvement step to the asymptotically optimal heuristic πS, in which we use a fluid model to obtain an approximation for the value function of πS. The performance of the proposed heuristic is investigated in an extensive numerical study. © 2010 Wiley Periodicals, Inc. Naval Research Logistics 2010

Suggested Citation

  • Dong Li & Kevin D. Glazebrook, 2010. "An approximate dynamic programing approach to the development of heuristics for the scheduling of impatient jobs in a clearing system," Naval Research Logistics (NRL), John Wiley & Sons, vol. 57(3), pages 225-236, April.
    • Handle: RePEc:wly:navres:v:57:y:2010:i:3:p:225-236
    DOI: 10.1002/nav.20395
    as

    Download full text from publisher

    File URL: https://doi.org/10.1002/nav.20395
    Download Restriction: no
    File URL: https://libkey.io/10.1002/nav.20395?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. K. D. Glazebrook & C. Kirkbride & J. Ouenniche, 2009. "Index Policies for the Admission Control and Routing of Impatient Customers to Heterogeneous Service Stations," Operations Research, INFORMS, vol. 57(4), pages 975-989, August.
    2. Jan A. Van Mieghem, 2003. "Due-Date Scheduling: Asymptotic Optimality of Generalized Longest Queue and Generalized Largest Delay Rules," Operations Research, INFORMS, vol. 51(1), pages 113-122, February.
    3. Ger Koole, 2008. "Introduction to the Special Issue on Call Center Management," Management Science, INFORMS, vol. 54(2), pages 237-237, February.
    4. Michelle Opp & Kevin Glazebrook & Vidyadhar G. Kulkarni, 2005. "Outsourcing warranty repairs: Dynamic allocation," Naval Research Logistics (NRL), John Wiley & Sons, vol. 52(5), pages 381-398, August.
    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. Farahani, Reza Zanjirani & Lotfi, M.M. & Baghaian, Atefe & Ruiz, Rubén & Rezapour, Shabnam, 2020. "Mass casualty management in disaster scene: A systematic review of OR&MS research in humanitarian operations," European Journal of Operational Research, Elsevier, vol. 287(3), pages 787-819.
    2. Lee, Hyun-Rok & Lee, Taesik, 2021. "Multi-agent reinforcement learning algorithm to solve a partially-observable multi-agent problem in disaster response," European Journal of Operational Research, Elsevier, vol. 291(1), pages 296-308.
    3. Atefe Baghaian & M. M. Lotfi & Shabnam Rezapour, 2022. "Integrated deployment of local urban relief teams in the first hours after mass casualty incidents," Operational Research, Springer, vol. 22(4), pages 4517-4555, September.
    4. Yisha Xiang & Jun Zhuang, 2016. "A medical resource allocation model for serving emergency victims with deteriorating health conditions," Annals of Operations Research, Springer, vol. 236(1), pages 177-196, January.
    5. Retsef Levi & Thomas Magnanti & Yaron Shaposhnik, 2019. "Scheduling with Testing," Management Science, INFORMS, vol. 65(2), pages 776-793, February.
    6. Dong Li & Li Ding & Stephen Connor, 2020. "When to Switch? Index Policies for Resource Scheduling in Emergency Response," Production and Operations Management, Production and Operations Management Society, vol. 29(2), pages 241-262, February.
    7. Terry James & Kevin Glazebrook & Kyle Lin, 2016. "Developing Effective Service Policies for Multiclass Queues with Abandonment: Asymptotic Optimality and Approximate Policy Improvement," INFORMS Journal on Computing, INFORMS, vol. 28(2), pages 251-264, May.
    8. Liu, Yang & Cui, Na & Zhang, Jianghua, 2019. "Integrated temporary facility location and casualty allocation planning for post-disaster humanitarian medical service," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 128(C), pages 1-16.
    9. Rezapour, Shabnam & Naderi, Nazanin & Morshedlou, Nazanin & Rezapourbehnagh, Shaghayegh, 2018. "Optimal deployment of emergency resources in sudden onset disasters," International Journal of Production Economics, Elsevier, vol. 204(C), pages 365-382.
    10. Michael N. Katehakis & Benjamin Melamed & Jim Junmin Shi, 2022. "Optimal replenishment rate for inventory systems with compound Poisson demands and lost sales: a direct treatment of time-average cost," Annals of Operations Research, Springer, vol. 317(2), pages 665-691, October.
    11. Hyun-Rok Lee & Taesik Lee, 2018. "Markov decision process model for patient admission decision at an emergency department under a surge demand," Flexible Services and Manufacturing Journal, Springer, vol. 30(1), pages 98-122, June.

    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. Avishai Mandelbaum & Petar Momčilović, 2017. "Personalized queues: the customer view, via a fluid model of serving least-patient first," Queueing Systems: Theory and Applications, Springer, vol. 87(1), pages 23-53, October.
    2. 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.
    3. I. Adan & O. Boxma, 2007. "Comments on: Dynamic priority allocation via restless bandit marginal productivity indices," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 15(2), pages 199-201, December.
    4. Ford, Stephen & Atkinson, Michael P. & Glazebrook, Kevin & Jacko, Peter, 2020. "On the dynamic allocation of assets subject to failure," European Journal of Operational Research, Elsevier, vol. 284(1), pages 227-239.
    5. Nicolas Gast & Bruno Gaujal & Kimang Khun, 2023. "Testing indexability and computing Whittle and Gittins index in subcubic time," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 97(3), pages 391-436, June.
    6. S. Duran & U. Ayesta & I. M. Verloop, 2022. "On the Whittle index of Markov modulated restless bandits," Queueing Systems: Theory and Applications, Springer, vol. 102(3), pages 373-430, December.
    7. Feng Chen & Vidyadhar G. Kulkarni, 2008. "Dynamic routing of prioritized warranty repairs," Naval Research Logistics (NRL), John Wiley & Sons, vol. 55(1), pages 16-26, February.
    8. Maglaras, Constantinos & Van Mieghem, Jan A., 2005. "Queueing systems with leadtime constraints: A fluid-model approach for admission and sequencing control," European Journal of Operational Research, Elsevier, vol. 167(1), pages 179-207, November.
    9. Romero-Silva, Rodrigo & Shaaban, Sabry & Marsillac, Erika & Hurtado, Margarita, 2018. "Exploiting the characteristics of serial queues to reduce the mean and variance of flow time using combined priority rules," International Journal of Production Economics, Elsevier, vol. 196(C), pages 211-225.
    10. Ece Zeliha Demirci & Joachim Arts & Geert-Jan Van Houtum, 2022. "A restless bandit approach for capacitated condition based maintenance scheduling," DEM Discussion Paper Series 22-01, Department of Economics at the University of Luxembourg.
    11. Junfei Huang & Boaz Carmeli & Avishai Mandelbaum, 2015. "Control of Patient Flow in Emergency Departments, or Multiclass Queues with Deadlines and Feedback," Operations Research, INFORMS, vol. 63(4), pages 892-908, August.
    12. Achal Bassamboo & Ramandeep S. Randhawa & Jan A. Van Mieghem, 2012. "A Little Flexibility Is All You Need: On the Asymptotic Value of Flexible Capacity in Parallel Queuing Systems," Operations Research, INFORMS, vol. 60(6), pages 1423-1435, December.
    13. Urtzi Ayesta & Manu K. Gupta & Ina Maria Verloop, 2021. "On the computation of Whittle’s index for Markovian restless bandits," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 93(1), pages 179-208, February.
    14. Seyed M. Iravani & Mark P. Van Oyen & Katharine T. Sims, 2005. "Structural Flexibility: A New Perspective on the Design of Manufacturing and Service Operations," Management Science, INFORMS, vol. 51(2), pages 151-166, February.
    15. Vivek S. Borkar & Sarath Pattathil, 2022. "Whittle indexability in egalitarian processor sharing systems," Annals of Operations Research, Springer, vol. 317(2), pages 417-437, October.
    16. D Worthington, 2009. "Reflections on queue modelling from the last 50 years," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(1), pages 83-92, May.
    17. Rami Atar & Chanit Giat & Nahum Shimkin, 2010. "The c(mu)/(theta) Rule for Many-Server Queues with Abandonment," Operations Research, INFORMS, vol. 58(5), pages 1427-1439, October.
    18. Rob Shone & Vincent A. Knight & Paul R. Harper, 2020. "A conservative index heuristic for routing problems with multiple heterogeneous service facilities," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 92(3), pages 511-543, December.
    19. Itai Gurvich & Ward Whitt, 2010. "Service-Level Differentiation in Many-Server Service Systems via Queue-Ratio Routing," Operations Research, INFORMS, vol. 58(2), pages 316-328, April.
    20. 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.

    More about this item

    Statistics

    Access and download statistics

    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:wly:navres:v:57:y:2010:i:3:p:225-236. 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: Wiley Content Delivery (email available below). General contact details of provider: https://doi.org/10.1002/(ISSN)1520-6750 .

    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.