×

Surgical case scheduling as a generalized job shop scheduling problem. (English) Zbl 1146.90420

Summary: Surgical case scheduling allocates hospital resources to individual surgical cases and decides on the time to perform the surgeries. This task plays a decisive role in utilizing hospital resources efficiently while ensuring quality of care for patients. This paper proposes a new surgical case scheduling approach which uses a novel extension of the Job Shop scheduling problem called multi-mode blocking job shop (MMBJS). It formulates the MMBJS as a mixed integer linear programming problem and discusses the use of the MMBJS model for scheduling elective and add-on cases. The model is illustrated by a detailed example, and preliminary computational experiments with the CPLEX solver on practical-sized instances are reported.

MSC:

90B35 Deterministic scheduling theory in operations research

Software:

CPLEX
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Baker, K. A., Introduction to Sequencing and Scheduling (1974), Wiley: Wiley New York
[2] Blake, J. T.; Carter, M. W., Surgical process scheduling: A conceptual literature review, Journal of Health Systems, 5, 3, 17-30 (1997)
[3] Blake, J. T.; Donald, J., Mount Sinai hospital uses integer programming to allocate OR time, Interfaces, 32, 2, 63-73 (2002)
[4] Bruker, P.; Kramer, A., Shop scheduling problem with multiprocessor tasks on dedicated processors, Annals of Operations Research, 57, 13-27 (1995) · Zbl 0831.90071
[5] Bruker, P.; Neyer, J., Tabu-search for the multi-mode job-shop problem, OR Spektrum, 20, 21-28 (1998) · Zbl 0897.90122
[6] Caraffa, V., Minimizing makespan in a blocking flowshop using genetic algorithms, International Journal of Production Economics, 70, 101-115 (2001)
[7] Cayirli, T.; Veral, E., Outpatient scheduling in health care: A review of literature, Production and Operations Management, 12, 4, 519-549 (2003)
[8] Credit Suisse Economic Research & Consulting. Le système de santé suisse – diagnostique pour un patient. Economic Briefing, 30, 2001.; Credit Suisse Economic Research & Consulting. Le système de santé suisse – diagnostique pour un patient. Economic Briefing, 30, 2001.
[9] E. Danna, E. Rothberg, C. Le Pape. Integrating mixed integer programming and local search - A case study on job shop scheduling problem. Proceedings CPAIOR, 2003.; E. Danna, E. Rothberg, C. Le Pape. Integrating mixed integer programming and local search - A case study on job shop scheduling problem. Proceedings CPAIOR, 2003.
[10] Dauzère-Pérès, S.; Paulli, J., An integrated approach for modeling and solving the general multiprocessor jobshop scheduling problem using Tabu search, Annals of Operations Research, 70, 281-306 (1997) · Zbl 0890.90097
[11] Dauzère-Pérès, S.; Pavageau, C., Multiresource shop scheduling with resource flexibility, European Journal of Operational Research, 107, 289-305 (1998) · Zbl 0943.90028
[12] Dexter, F.; Macario, A.; Rodney, D., Which algorithm for scheduling add-on elective cases maximizes OR utilization? Use of bin packing algorithms and fuzzy constraints in OR management, Anesthesiology, 91, 5, 1491-1501 (1999)
[13] Dexter, F.; Macario, F.; Traub, R. D., Optimal sequencing of urgent surgical cases, Journal of Clinical Monitoring and Computing, 15, 153-162 (1999)
[14] Dexter, F.; Traub, R. D., How to schedule elective surgical cases into specific Operating Room to maximize efficiency of use of OR time?, Anesthesiology, 94, 933-942 (2002)
[15] Dexter, F., Strategies to reduce delays in admission into a PACU from Operating Rooms, Journal of PeriAnesthesia Nursing, 20, 2, 92-102 (2005)
[16] Gable, R. A., Operating Room Management (1999), Butterworth-Heinemann: Butterworth-Heinemann London
[17] H. Gröflin, A. Klinkert. Feasible insertions in job shop scheduling, short cycles and stable sets. Internal working paper, Department of Informatics, University of Fribourg, 04-09, 2004.; H. Gröflin, A. Klinkert. Feasible insertions in job shop scheduling, short cycles and stable sets. Internal working paper, Department of Informatics, University of Fribourg, 04-09, 2004.
[18] H. Gröflin, A. Klinkert. Local search in job shop scheduling with synchronization and blocking constraints. Internal working paper, Department of Informatics, University of Fribourg, 04-06, 2004.; H. Gröflin, A. Klinkert. Local search in job shop scheduling with synchronization and blocking constraints. Internal working paper, Department of Informatics, University of Fribourg, 04-06, 2004.
[19] Guinet, A.; Chaabane, S., Operating theatre planning, International Journal of Production Economics, 85, 69-81 (2003)
[20] Harris, A. P.; Zitzmann, G. W., Operating Room Management (1998), Mosby: Mosby St. Louis, MO
[21] T. Hürlimann. LPL: A mathematical modeling language. Available from: <http://www.virtual-optima.com/download/docs/intro.pdf>; T. Hürlimann. LPL: A mathematical modeling language. Available from: <http://www.virtual-optima.com/download/docs/intro.pdf>
[22] Jackson, R., The business of surgery, Health Management Technology, 23, 7, 20-22 (2002)
[23] Jain, A. S.; Meeeran, S., Deterministic job-shop scheduling: Past, present, and future, European Journal of Operational Research, 113, 390-434 (1999) · Zbl 0938.90028
[24] Kim, S. C., Flexible bed allocation and performance in the intensive care unit, Journal of Operations Management, 18, 427-443 (2000)
[25] Kwak, N. K.; Kuzdrall, P. J.; Schmitz, H. H., The GPSS simulation of scheduling policies for surgical patients, Management Science, 22, 9, 982-989 (1976)
[26] Lee, C. Y.; Matta, R.; Hsu, V. N., Scheduling patients in an ambulatory surgical center, Naval Research Logistics, 50, 3, 218-238 (2002) · Zbl 1030.90034
[27] Macario, A., Where are costs in perioperative? Analysis of hospital costs and charges for inpatient surgical care, Anesthesiology, 83, 6, 1138-1144 (1995)
[28] Magerlein, J. M.; Martin, J. B., Surgical demand scheduling: A review, Health Service Research, 13, 418-433 (1978)
[29] Manager, O. R., Efficient scheduling of OR cases, OR Manager, 16, 27-28 (2000)
[30] Mascis, A.; Pacciarelli, D., Job-shop scheduling with blocking and no-wait constraints, European Journal of Operational Research, 143, 498-517 (2002) · Zbl 1082.90528
[31] Mastrollili, M.; Gamberdella, L. M., Effective neighborhood functions for the flexible job shop problem, Journal of Scheduling, 3, 1, 3-20 (2000)
[32] OECD. OECD annual report. Available from: <http://www.oecd.org>; OECD. OECD annual report. Available from: <http://www.oecd.org>
[33] Ozkarahan, I., Allocation of surgical procedures to Operating Rooms, Journal of Medical Systems, 19, 4, 333-352 (1995)
[34] Ozkarahan, I., Allocation of surgeries to Operating Rooms by goal programming, Journal of Medical Systems, 24, 6, 339-378 (2000)
[35] Raaymakers, W. H.M.; Hoogeveen, J. A., Scheduling multipurpose batch process industries with no-wait restrictions by simulated annealing, European Journal of Operational Research, 126, 131-151 (2000) · Zbl 0970.90034
[36] Ronconi, D. P., A branch-and-bound algorithm to minimize the makespan in a flowshop with blocking, Annals of Operations Research, 138, 53-65 (2005) · Zbl 1091.90075
[37] Schutten, J. M.J., Practical job shop, Annals of Operations Research, 83, 161-177 (1998) · Zbl 0911.90221
[38] Sieber, T. J.; Leibundgut, D. L., Operating Room management and strategies in Switzerland: Results of a survey, European Journal of Anesthesiology, 19, 415-423 (2002)
[39] Sier, D.; Tobin, P.; Mcgurk, C., Scheduling surgical procedures, Journal of the Operational Research Society, 48, 884-891 (1997) · Zbl 0892.90133
[40] Weinbroum, A. A.; Ekstein, P.; Ezri, T., Efficiency of the operating room suite, The American Journal of Surgery, 185, 244-250 (2003)
[41] Weiss, N. E., Model for determining estimated start times and case orderings in hospitals ORs, IIE Transaction, 22, 143-150 (1988)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.