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

Scheduling with Testing

Author

Listed:
  • Retsef Levi

    (Sloan School of Management, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139)

  • Thomas Magnanti

    (Sloan School of Management, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139; and Singapore University of Technology and Design, Singapore 138682)

  • Yaron Shaposhnik

    (Simon Business School, University of Rochester, Rochester, New York 14627)

Abstract

We study a new class of scheduling problems that capture common settings in service environments, in which one has to serve a collection of jobs that have a priori uncertain attributes (e.g., processing times and priorities) and the service provider has to decide how to dynamically allocate resources (e.g., people, equipment, and time) between testing (diagnosing) jobs to learn more about their respective uncertain attributes and processing jobs. The former could inform future decisions, but could delay the service time for other jobs, while the latter directly advances the processing of the jobs but requires making decisions under uncertainty. Through novel analysis we obtain surprising structural results of optimal policies that provide operational managerial insights, efficient optimal and near-optimal algorithms, and quantification of the value of testing. We believe that our approach will lead to further research to explore this important practical trade-off.

Suggested Citation

  • Retsef Levi & Thomas Magnanti & Yaron Shaposhnik, 2019. "Scheduling with Testing," Management Science, INFORMS, vol. 65(2), pages 776-793, February.
    • Handle: RePEc:inm:ormnsc:v:65:y:2019:i:2:p:776-793
    DOI: 10.1287/mnsc.2017.2973
    as

    Download full text from publisher

    File URL: https://doi.org/10.1287/mnsc.2017.2973
    Download Restriction: no
    File URL: https://libkey.io/10.1287/mnsc.2017.2973?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. Ciriaco Valdez‐Flores & Richard M. Feldman, 1989. "A survey of preventive maintenance models for stochastically deteriorating single‐unit systems," Naval Research Logistics (NRL), John Wiley & Sons, vol. 36(4), pages 419-446, August.
    2. John J. McCall, 1965. "Maintenance Policies for Stochastically Failing Equipment: A Survey," Management Science, INFORMS, vol. 11(5), pages 493-524, March.
    3. Evin Uzun Jacobson & Nilay Tanık Argon & Serhan Ziya, 2012. "Priority Assignment in Emergency Response," Operations Research, INFORMS, vol. 60(4), pages 813-832, August.
    4. Saed Alizamir & Francis de Véricourt & Peng Sun, 2013. "Diagnostic Accuracy Under Congestion," Management Science, INFORMS, vol. 59(1), pages 157-171, December.
    5. Omar Besbes & Alp Muharremoglu, 2013. "On Implications of Demand Censoring in the Newsvendor Problem," Management Science, INFORMS, vol. 59(6), pages 1407-1424, June.
    6. Robin P. Nicolai & Rommert Dekker, 2008. "Optimal Maintenance of Multi-component Systems: A Review," Springer Series in Reliability Engineering, in: Complex System Maintenance Handbook, chapter 11, pages 263-286, Springer.
    7. Wang, Hongzhou, 2002. "A survey of maintenance policies of deteriorating systems," European Journal of Operational Research, Elsevier, vol. 139(3), pages 469-489, June.
    8. Rommert Dekker & Ralph Wildeman & Frank Duyn Schouten, 1997. "A review of multi-component maintenance models with economic dependence," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 45(3), pages 411-435, October.
    9. van Noortwijk, J.M., 2009. "A survey of the application of gamma processes in maintenance," Reliability Engineering and System Safety, Elsevier, vol. 94(1), pages 2-21.
    10. William P. Pierskalla & John A. Voelker, 1976. "A survey of maintenance models: The control and surveillance of deteriorating systems," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 23(3), pages 353-388, September.
    11. Wayne E. Smith, 1956. "Various optimizers for single‐stage production," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 3(1‐2), pages 59-66, March.
    12. 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.
    13. Zhankun Sun & Nilay Tan?k Argon & Serhan Ziya, 2018. "Patient Triage and Prioritization Under Austere Conditions," Management Science, INFORMS, vol. 64(10), pages 4471-4489, October.
    14. Y. S. Sherif & M. L. Smith, 1981. "Optimal maintenance models for systems subject to failure–A Review," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 28(1), pages 47-74, March.
    15. Alex F. Mills & Nilay Tanık Argon & Serhan Ziya, 2013. "Resource-Based Patient Prioritization in Mass-Casualty Incidents," Manufacturing & Service Operations Management, INFORMS, vol. 15(3), pages 361-377, July.
    16. Cho, Danny I. & Parlar, Mahmut, 1991. "A survey of maintenance models for multi-unit systems," European Journal of Operational Research, Elsevier, vol. 51(1), pages 1-23, March.
    17. Omar Besbes & Assaf Zeevi, 2009. "Dynamic Pricing Without Knowing the Demand Function: Risk Bounds and Near-Optimal Algorithms," Operations Research, INFORMS, vol. 57(6), pages 1407-1420, 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. Zhankun Sun & Nilay Tanık Argon & Serhan Ziya, 2022. "When to Triage in Service Systems with Hidden Customer Class Identities?," Production and Operations Management, Production and Operations Management Society, vol. 31(1), pages 172-193, January.
    2. Sanjay Jain & Jónas Oddur Jónasson & Jean Pauphilet & Kamalini Ramdas, 2023. "Robust combination testing: methods and application to COVID-19 detection," Economics Series Working Papers 1009, University of Oxford, Department of Economics.
    3. Wu, Wei & Hayashi, Takito & Haruyasu, Kato & Tang, Liang, 2023. "Exact algorithms based on a constrained shortest path model for robust serial-batch and parallel-batch scheduling problems," European Journal of Operational Research, Elsevier, vol. 307(1), pages 82-102.

    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. Lisa M. Maillart & Xiang Fang, 2006. "Optimal maintenance policies for serial, multi‐machine systems with non‐instantaneous repairs," Naval Research Logistics (NRL), John Wiley & Sons, vol. 53(8), pages 804-813, December.
    2. de Jonge, Bram & Scarf, Philip A., 2020. "A review on maintenance optimization," European Journal of Operational Research, Elsevier, vol. 285(3), pages 805-824.
    3. Lu, Biao & Zhou, Xiaojun, 2017. "Opportunistic preventive maintenance scheduling for serial-parallel multistage manufacturing systems with multiple streams of deterioration," Reliability Engineering and System Safety, Elsevier, vol. 168(C), pages 116-127.
    4. David T. Abdul‐Malak & Jeffrey P. Kharoufeh & Lisa M. Maillart, 2019. "Maintaining systems with heterogeneous spare parts," Naval Research Logistics (NRL), John Wiley & Sons, vol. 66(6), pages 485-501, September.
    5. Pinciroli, Luca & Baraldi, Piero & Zio, Enrico, 2023. "Maintenance optimization in industry 4.0," Reliability Engineering and System Safety, Elsevier, vol. 234(C).
    6. Wang, Wei & Wu, Zhiying & Xiong, Junlin & Xu, Yaofeng, 2018. "Redundancy optimization of cold-standby systems under periodic inspection and maintenance," Reliability Engineering and System Safety, Elsevier, vol. 180(C), pages 394-402.
    7. Olde Keizer, Minou C.A. & Flapper, Simme Douwe P. & Teunter, Ruud H., 2017. "Condition-based maintenance policies for systems with multiple dependent components: A review," European Journal of Operational Research, Elsevier, vol. 261(2), pages 405-420.
    8. Olde Keizer, Minou C.A. & Teunter, Ruud H. & Veldman, Jasper, 2016. "Clustering condition-based maintenance for systems with redundancy and economic dependencies," European Journal of Operational Research, Elsevier, vol. 251(2), pages 531-540.
    9. V Zille & C Bérenguer & A Grall & A Despujols, 2011. "Modelling multicomponent systems to quantify reliability centred maintenance strategies," Journal of Risk and Reliability, , vol. 225(2), pages 141-160, June.
    10. Alireza Sabouri & Woonghee Tim Huh & Steven M. Shechter, 2017. "Screening Strategies for Patients on the Kidney Transplant Waiting List," Operations Research, INFORMS, vol. 65(5), pages 1131-1146, October.
    11. Yeek-Hyun Kim & Lyn Thomas, 2013. "Training and repair policies for stand-by systems," Annals of Operations Research, Springer, vol. 208(1), pages 469-487, September.
    12. Zhang, Xiaohong & Zeng, Jianchao, 2015. "A general modeling method for opportunistic maintenance modeling of multi-unit systems," Reliability Engineering and System Safety, Elsevier, vol. 140(C), pages 176-190.
    13. Steven M. Shechter & Matthew D. Bailey & Andrew J. Schaefer, 2008. "Replacing nonidentical vital components to extend system life," Naval Research Logistics (NRL), John Wiley & Sons, vol. 55(7), pages 700-703, October.
    14. Briš, Radim & Byczanski, Petr & Goňo, Radomír & Rusek, Stanislav, 2017. "Discrete maintenance optimization of complex multi-component systems," Reliability Engineering and System Safety, Elsevier, vol. 168(C), pages 80-89.
    15. Jyrki Savolainen & Michele Urbani, 2021. "Maintenance optimization for a multi-unit system with digital twin simulation," Journal of Intelligent Manufacturing, Springer, vol. 32(7), pages 1953-1973, October.
    16. Alaswad, Suzan & Xiang, Yisha, 2017. "A review on condition-based maintenance optimization models for stochastically deteriorating system," Reliability Engineering and System Safety, Elsevier, vol. 157(C), pages 54-63.
    17. Shen, Zuo-Jun Max & Xie, Jingui & Zheng, Zhichao & Zhou, Han, 2023. "Dynamic scheduling with uncertain job types," European Journal of Operational Research, Elsevier, vol. 309(3), pages 1047-1060.
    18. Bouvard, K. & Artus, S. & Bérenguer, C. & Cocquempot, V., 2011. "Condition-based dynamic maintenance operations planning & grouping. Application to commercial heavy vehicles," Reliability Engineering and System Safety, Elsevier, vol. 96(6), pages 601-610.
    19. Olde Keizer, Minou C.A. & Teunter, Ruud H. & Veldman, Jasper, 2017. "Joint condition-based maintenance and inventory optimization for systems with multiple components," European Journal of Operational Research, Elsevier, vol. 257(1), pages 209-222.
    20. Wang, Wenbin, 2012. "An overview of the recent advances in delay-time-based maintenance modelling," Reliability Engineering and System Safety, Elsevier, vol. 106(C), pages 165-178.

    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:2:p:776-793. 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.