IDEAS home Printed from https://ideas.repec.org/a/spr/jcomop/v37y2019i1d10.1007_s10878-017-0211-4.html
   My bibliography  Save this article

The medical laboratory scheduling for weighted flow-time

Author

Listed:
  • Wenhua Li

    (Zhengzhou University)

  • Xing Chai

    (Zhengzhou University)

Abstract

This paper studies an on-line scheduling in medical laboratory. The sample of a patient is regarded as a job waiting to be scheduled, and each analyzer as a machine that may analyze several samples simultaneously as a batch. The samples arrive over time, and the information of each sample is not released until the sample arrives. Each sample is given a weight in a known range to represent its importance or urgency. Thus the medical laboratory scheduling can be described as a parallel-batch on-line scheduling problem. The objective is to minimize the maximum weighted flow-time. For the unbounded batch capacity model, a best possible on-line algorithm is established for any given range of weights. Moreover, for the bounded batch capacity model, a best possible on-line algorithm is presented for the range of weights 1 to 2.

Suggested Citation

  • Wenhua Li & Xing Chai, 2019. "The medical laboratory scheduling for weighted flow-time," Journal of Combinatorial Optimization, Springer, vol. 37(1), pages 83-94, January.
    • Handle: RePEc:spr:jcomop:v:37:y:2019:i:1:d:10.1007_s10878-017-0211-4
    DOI: 10.1007/s10878-017-0211-4
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10878-017-0211-4
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10878-017-0211-4?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Liwei Zhong & Shoucheng Luo & Lidong Wu & Lin Xu & Jinghui Yang & Guochun Tang, 2014. "A two-stage approach for surgery scheduling," Journal of Combinatorial Optimization, Springer, vol. 27(3), pages 545-556, April.
    2. Edward J. Anderson & Chris N. Potts, 2004. "Online Scheduling of a Single Machine to Minimize Total Weighted Completion Time," Mathematics of Operations Research, INFORMS, vol. 29(3), pages 686-697, August.
    3. Lili Liu & Guochun Tang & Baoqiang Fan & Xingpeng Wang, 2015. "Two-person cooperative games on scheduling problems in outpatient pharmacy dispensing process," Journal of Combinatorial Optimization, Springer, vol. 30(4), pages 938-948, November.
    4. Xingong Zhang & Hui Wang & Xingpeng Wang, 2015. "Patients scheduling problems with deferred deteriorated functions," Journal of Combinatorial Optimization, Springer, vol. 30(4), pages 1027-1041, November.
    5. D. Michael Warner, 1976. "Scheduling Nursing Personnel According to Nursing Preference: A Mathematical Programming Approach," Operations Research, INFORMS, vol. 24(5), pages 842-856, October.
    6. Holmes E. Miller & William P. Pierskalla & Gustave J. Rath, 1976. "Nurse Scheduling Using Mathematical Programming," Operations Research, INFORMS, vol. 24(5), pages 857-870, October.
    7. Jianfa Cao & Jinjiang Yuan & Wenjie Li & Hailin Bu, 2011. "Online scheduling on batching machines to minimise the total weighted completion time of jobs with precedence constraints and identical processing times," International Journal of Systems Science, Taylor & Francis Journals, vol. 42(1), pages 51-55.
    8. Xiangyong Li & N. Rafaliya & M. Fazle Baki & Ben A. Chaouch, 2017. "Scheduling elective surgeries: the tradeoff among bed capacity, waiting patients and operating room utilization using goal programming," Health Care Management Science, Springer, vol. 20(1), pages 33-54, March.
    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. Jing Fan & Hui Shi, 2022. "Non-resumable scheduling on a single bounded parallel-batch machine with periodic maintenance," Journal of Combinatorial Optimization, Springer, vol. 43(5), pages 1645-1654, July.
    2. Jing Fan & Hui Shi, 0. "A three-stage supply chain scheduling problem based on the nursing assistants’ daily work in a hospital," Journal of Combinatorial Optimization, Springer, vol. 0, pages 1-13.
    3. Jing Fan & Hui Shi, 2021. "A three-stage supply chain scheduling problem based on the nursing assistants’ daily work in a hospital," Journal of Combinatorial Optimization, Springer, vol. 42(4), pages 896-908, November.
    4. Wenhua Li & Weina Zhai & Xing Chai, 2019. "Online Bi-Criteria Scheduling on Batch Machines with Machine Costs," Mathematics, MDPI, vol. 7(10), pages 1-11, October.

    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. Scott E. Sampson, 2008. "OR PRACTICE---Optimization of Vacation Timeshare Scheduling," Operations Research, INFORMS, vol. 56(5), pages 1079-1088, October.
    2. Yadong Wang & Baoqiang Fan & Jingang Zhai & Wei Xiong, 2019. "Two-machine flowshop scheduling in a physical examination center," Journal of Combinatorial Optimization, Springer, vol. 37(1), pages 363-374, January.
    3. Berrada, Ilham & Ferland, Jacques A. & Michelon, Philippe, 1996. "A multi-objective approach to nurse scheduling with both hard and soft constraints," Socio-Economic Planning Sciences, Elsevier, vol. 30(3), pages 183-193, September.
    4. Wolbeck, Lena Antonia, 2019. "Fairness aspects in personnel scheduling," Discussion Papers 2019/16, Free University Berlin, School of Business & Economics.
    5. Duma, Davide & Aringhieri, Roberto, 2019. "The management of non-elective patients: shared vs. dedicated policies," Omega, Elsevier, vol. 83(C), pages 199-212.
    6. Wright, P. Daniel & Mahar, Stephen, 2013. "Centralized nurse scheduling to simultaneously improve schedule cost and nurse satisfaction," Omega, Elsevier, vol. 41(6), pages 1042-1052.
    7. Belií«n, Jeroen & Demeulemeester, Erik, 2008. "A branch-and-price approach for integrating nurse and surgery scheduling," European Journal of Operational Research, Elsevier, vol. 189(3), pages 652-668, September.
    8. Giovanni Felici & Claudio Gentile, 2004. "A Polyhedral Approach for the Staff Rostering Problem," Management Science, INFORMS, vol. 50(3), pages 381-393, March.
    9. Zhenyuan Liu & Jiongbing Lu & Zaisheng Liu & Guangrui Liao & Hao Howard Zhang & Junwu Dong, 2019. "Patient scheduling in hemodialysis service," Journal of Combinatorial Optimization, Springer, vol. 37(1), pages 337-362, January.
    10. Venkataraman, R. & Brusco, M. J., 1996. "An integrated analysis of nurse staffing and scheduling policies," Omega, Elsevier, vol. 24(1), pages 57-71, February.
    11. Cheang, B. & Li, H. & Lim, A. & Rodrigues, B., 2003. "Nurse rostering problems--a bibliographic survey," European Journal of Operational Research, Elsevier, vol. 151(3), pages 447-460, December.
    12. Millar, Harvey H. & Kiragu, Mona, 1998. "Cyclic and non-cyclic scheduling of 12 h shift nurses by network programming," European Journal of Operational Research, Elsevier, vol. 104(3), pages 582-592, February.
    13. Hadi W. Purnomo & Jonathan F. Bard, 2007. "Cyclic preference scheduling for nurses using branch and price," Naval Research Logistics (NRL), John Wiley & Sons, vol. 54(2), pages 200-220, March.
    14. Gang Du & Luyao Zheng & Xiaoling Ouyang, 2019. "Real-time scheduling optimization considering the unexpected events in home health care," Journal of Combinatorial Optimization, Springer, vol. 37(1), pages 196-220, January.
    15. Jaumard, Brigitte & Semet, Frederic & Vovor, Tsevi, 1998. "A generalized linear programming model for nurse scheduling," European Journal of Operational Research, Elsevier, vol. 107(1), pages 1-18, May.
    16. Li, L. X. & Benton, W. C., 1996. "Performance measurement criteria in health care organizations: Review and future research directions," European Journal of Operational Research, Elsevier, vol. 93(3), pages 449-468, September.
    17. Edmund K. Burke & Timothy Curtois & Rong Qu & Greet Vanden Berghe, 2013. "A Time Predefined Variable Depth Search for Nurse Rostering," INFORMS Journal on Computing, INFORMS, vol. 25(3), pages 411-419, August.
    18. Federico Della Croce & Fabio Salassa, 2014. "A variable neighborhood search based matheuristic for nurse rostering problems," Annals of Operations Research, Springer, vol. 218(1), pages 185-199, July.
    19. Lu Liu & Chun Wang & Jianjun Wang, 2019. "A combinatorial auction mechanism for surgical scheduling considering surgeon’s private availability information," Journal of Combinatorial Optimization, Springer, vol. 37(1), pages 405-417, January.
    20. G Beddoe & S Petrovic, 2007. "Enhancing case-based reasoning for personnel rostering with selected tabu search concepts," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 58(12), pages 1586-1598, December.

    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:spr:jcomop:v:37:y:2019:i:1:d:10.1007_s10878-017-0211-4. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.