Local search and lower bounds for the patient admission scheduling problem.

*(English)*Zbl 1208.90110Summary: We propose a multi-neighborhood local search procedure to solve a healthcare problem, known as the Patient Admission Scheduling problem. We design and experiment with different combinations of neighborhoods, showing that they have diverse effectiveness for different sets of weights of the cost components that constitute the objective function. We also compute many lower bounds based on the relaxation of some constraints. The outcome is that our results compare favorably with the previous work on the problem, improving all available instances, and in some cases are also quite close to the lower bounds. Finally, we propose the application of the technique to the dynamic case, in which admission and discharge dates are not predictable in advance.

##### MSC:

90B90 | Case-oriented studies in operations research |

90C59 | Approximation methods and heuristics in mathematical programming |

PDF
BibTeX
XML
Cite

\textit{S. Ceschia} and \textit{A. Schaerf}, Comput. Oper. Res. 38, No. 10, 1452--1463 (2011; Zbl 1208.90110)

Full Text:
DOI

##### References:

[1] | Burke, E.K.; De Causmaeker, P.; Vanden Berghe, G.; Van Landeghem, H., The state of the art of nurse rostering, Journal of scheduling, 7, 441-499, (2004) · Zbl 1154.90422 |

[2] | Rousseau, L.-M.; Gendreau, M.; Pesant, G., A general approach to the Physician rostering problems, Annals of operations research, 115, 193-205, (2002) · Zbl 1013.90135 |

[3] | Hans, E.; Wullink, G.; van Houdenhoven, M.; Kazemier, G., Robust surgery loading, European journal of operational research, 185, 3, 1038-1050, (2008) · Zbl 1178.90229 |

[4] | Demeester P, De Causmaecker P, Vanden Berghe G. Applying a local search algorithm to automatically assign patients to beds. In: Proceedings of the 22nd conference on quantitative methods for decision making (Orbel 22); 2008. p. 35-36. |

[5] | Bilgin B, Demeester P, Vanden Berghe G. A hyperheuristic approach to the patient admission scheduling problem. Techical Report, KaHo Sint-Lieven, Gent; 2008. |

[6] | Demeester, P.; Souffriau, W.; De Causmaecker, P.; Vanden Berghe, G., A hybrid tabu search algorithm for automatically assigning patients to beds, Artificial intelligence in medicine, 48, 1, 61-70, (2010) |

[7] | Demeester P. Patient admission scheduling website, 2009 \(\langle\)http://allserv.kahosl.be/∼peter/pas/〉; viewed July 2, 2010. |

[8] | Gemmel, P.; Van Dierdonck, R., Admission scheduling in acute care hospitals: does the practice fit with the theory?, International journal of operations and production management, 19, 9, 863-878, (1999) |

[9] | Worthington, D.J., Queueing models for hospital waiting lists, The journal of the operational research society, 38, 5, 413-422, (1987) |

[10] | Worthington, D., Hospital waiting List management models, The journal of the operational research society, 42, 10, 833-843, (1991) · Zbl 0729.90764 |

[11] | Mullen, P.M., Waiting lists in the post-review NHS, Health services management research: an official journal of the association of university programs in health administration/HSMC, AUPHA, 7, 2, 131-145, (1994) |

[12] | Smith-Daniels, V.L.; Schweikhart, S.B.; Smith-Daniels, D.E., Capacity management in health care services: review and future research directions, Decision sciences, 19, 4, 889-919, (1988) |

[13] | Vissers, J.; Adan, I.; Dellaert, N., Developing a platform for comparison of hospital admission systems: an illustration, European journal of operational research, 180, 3, 1290-1301, (2007) · Zbl 1121.90395 |

[14] | Williams, P.; Tai, G.; Lei, Y., Simulation based analysis of patient arrival to health care systems and evaluation of an operations improvement scheme, Annals of operations research, 178, 1, 263-279, (2009) |

[15] | Brandeau, M.L.; Sainfort, F.; Pierskalla, W.P., Operations research and health care: a handbook of methods and applications, (2004), Springer · Zbl 1050.90001 |

[16] | Harper, P.R.; Shahani, A.K., Modelling for the planning and management of bed capacities in hospitals, The journal of the operational research society, 53, 1, 11-18, (2002) · Zbl 1138.90415 |

[17] | Goldman, J.; Knappenberger, H.A.; Eller, J.C., Evaluating bed allocation policy with computer simulation, Health services research, 3, 2, 119-129, (1968) |

[18] | Kao, E.P.C.; Tung, G.G., Bed allocation in a public health care delivery system, Management science, 27, 5, 507-520, (1981) |

[19] | Dumas, M.B., Simulation modeling for hospital bed planning, Simulation, 43, 2, 69-78, (1984) |

[20] | Dumas, M.B., Hospital bed utilization: an implemented simulation approach to adjusting and maintaining appropriate levels, Health services research, 20, 1, 43-61, (1985) |

[21] | Vassilacopoulos, G., A simulation model for bed allocation to hospital inpatient departments, Simulation, 45, 5, 233-241, (1985) |

[22] | Blake, J.T.; Dexter, F.; Donald, J., Operating room managers’ use of integer programming for assigning block time to surgical groups: a case study, Anesthesia and analgesia, 94, 1, 143-148, (2002) |

[23] | Dexter, F.; Macario, A., Changing allocations of operating room time from a system based on historical utilization to one where the aim is to schedule as many surgical cases as possible, Anesthesia and analgesia, 94, 5, 1272-1279, (2002) |

[24] | Jebali, A.; Hadjalouane, A.; Ladet, P., Operating rooms scheduling, International journal of production economics, 99, 1-2, 52-62, (2006) |

[25] | Tànfani, E.; Testi, A., A pre-assignment heuristic algorithm for the master surgical schedule problem (MSSP), Annals of operations research, 178, 1, 105-119, (2010) · Zbl 1197.90230 |

[26] | Oostrum, J.M.; Bredenhoff, E.; Hans, E.W., Suitability and managerial implications of a master surgical scheduling approach, Annals of operations research, 178, 1, 91-104, (2010) |

[27] | Kirkpatrick, S.; Gelatt, C.D.; Vecchi, M.P., Optimization by simulated annealing, Science, 220, 671-680, (1983) · Zbl 1225.90162 |

[28] | Černý, V., Thermodynamical approach to the traveling salesman problem: an efficient simulation algorithm, Journal of optimization theory and applications, 45, l, 41-51, (1985) · Zbl 0534.90091 |

[29] | Aarts, E.; Lenstra, J.K., Local search in combinatorial optimization, (1997), John Wiley & Sons Chichester · Zbl 0869.00019 |

[30] | Hoos, H.H.; Stützle, T., Stochastic local search – foundations and applications, (2005), Morgan Kaufmann Publishers San Francisco, CA, USA · Zbl 1126.68032 |

[31] | van Laarhoven, P.J.M.; Aarts, E.H.L., Simulated annealing: theory and applications, (1987), D. Reidel Publishing Company, Kluwer Academic Publishers Group · Zbl 0643.65028 |

[32] | Johnson, D.S.; Aragon, C.R.; McGeoch, L.A.; Schevon, C., Optimization by simulated annealing: an experimental evaluation; part I, graph partitioning, Operations research, 37, 6, 865-892, (1989) · Zbl 0698.90065 |

[33] | Johnson, D.S.; Aragon, C.R.; McGeoch, L.A.; Schevon, C., Optimization by simulated annealing: an experimental evaluation; part II, graph coloring and number partitioning, Operations research, 39, 3, 378-406, (1991) · Zbl 0739.90055 |

[34] | Triki, E.; Collette, Y.; Siarry, P., A theoretical study on the behavior of simulated annealing leading to a new cooling schedule, European journal of operational research, 166, 1, 77-92, (2005) · Zbl 1066.90043 |

[35] | Thomson J, Dowsland K. General cooling schedules for simulated annealing-based timetabling system. In: Proceedings of the 1st international conference on the practice and theory of automated timetabling (ICPTAT-95); 1995. p. 345-63. |

[36] | Di Gaspero, L.; Schaerf, A., Neighborhood portfolio approach for local search applied to timetabling problems, Journal of mathematical modeling and algorithms, 5, 1, 65-89, (2006) · Zbl 1103.90102 |

[37] | Johnson DS. A theoretician’s guide to the experimental analysis of algorithms. In: Goldwasser MH, Johnson DS, McGeoch CC., editors, Data structures, near neighbor searches, and methodology: fifth and sixth DIMACS Implementation Challenges. American Mathematical Society, 2002, p. 215-50, available from \(\langle\)http://www.research.att.com/dsj/papers.html〉. |

[38] | Di Gaspero, L.; Schaerf, A., \sceasylocal++: an object-oriented framework for flexible design of local search algorithms, Software – practice and experience, 33, 8, 733-765, (2003) |

[39] | IBM ILOG, 2009. CPLEX Optimizer \(\langle\)http://www-01.ibm.com/software/integration/optimization/cplex-optimizer/〉, v. 12.1. |

[40] | Cioppa, T.M.; Lucas, T.W., Efficient nearly orthogonal and space-filling Latin hypercubes, Technometrics, 49, 1, 45-55, (2007) |

[41] | Sanchez SM. NOLH designs spreadsheet, 2005 \(\langle\)http://diana.cs.nps.navy.mil/SeedLab/〉; visited on October 6, 2010. |

[42] | Birattari M. The RACE package, available from \(\langle\)http://cran.r-project.org/doc/packages/race.pdf〉, April 2005. |

[43] | Venables, W.N.; Ripley, B.D., Modern applied statistics with S, () · Zbl 1006.62003 |

[44] | McCollum, B.; Schaerf, A.; Paechter, B.; McMullan, P.; Lewis, R.; Parkes, A.J.; Di Gaspero, L.; Qu, R.; Burke, E.K., Setting the research agenda in automated timetabling: the second international timetabling competition, INFORMS journal on computing, 22, 1, 120-130, (2010) · Zbl 1243.90007 |

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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.