title: An adaptive large neighborhood search procedure applied to the dynamic patient admission scheduling problem.
abstract: The aim of this paper is to provide an improved method for solving the so-called dynamic patient admission scheduling (DPAS) problem. This is a complex scheduling problem that involves assigning a set of patients to hospital beds over a given time horizon in such a way that several quality measures reflecting patient comfort and treatment efficiency are maximized. Consideration must be given to uncertainty in the length of stays of patients as well as the possibility of emergency patients.
  
  
  
  We develop an adaptive large neighborhood search (ALNS) procedure to solve the problem. This procedure utilizes a Simulated Annealing framework.
  
  
  
  We thoroughly test the performance of the proposed ALNS approach on a set of 450 publicly available problem instances. A comparison with the current state-of-the-art indicates that the proposed methodology provides solutions that are of comparable quality for small and medium sized instances (up to 1000 patients); the two approaches provide solutions that differ in quality by approximately 1% on average. The ALNS procedure does, however, provide solutions in a much shorter time frame. On larger instances (between 1000-4000 patients) the improvement in solution quality by the ALNS procedure is substantial, approximately 3-14% on average, and as much as 22% on a single instance. The time taken to find such results is, however, in the worst case, a factor 12 longer on average than the time limit which is granted to the current state-of-the-art.
  
  
  
  The proposed ALNS procedure is an efficient and flexible method for solving the DPAS problem.
authors.affiliation: Department of Engineering Management, Produktionstorvet, Technical University of Denmark, Kongens Lyngby 2800, Denmark. Electronic address: rmlu@dtu.dk.
authors.forename: Richard Martin
authors.initials: RM
authors.lastname: Lusby
authors.affiliation: AMCS Denmark A/S, Hejrevej 34D, Copenhagen 2400, Denmark.
authors.forename: Martin
authors.initials: M
authors.lastname: Schwierz
authors.affiliation: Hospital of South West Jutland, Finsensgade 35, 6700 Esbjerg, Denmark.
authors.forename: Troels Martin
authors.initials: TM
authors.lastname: Range
authors.affiliation: Department of Engineering Management, Produktionstorvet, Technical University of Denmark, Kongens Lyngby 2800, Denmark.
authors.forename: Jesper
authors.initials: J
authors.lastname: Larsen
mesh_terms: D000465:Algorithms; D006801:Humans; D010343:Patient Admission; D013997:Time Factors; D035501:Uncertainty
keywords: Adaptive large neighborhood search; Metaheuristic; Patient admission scheduling