Appointment scheduling in surgery pre-admission testing clinics

Pre-admission testing clinics are care units serving outpatients prior to surgical operation and performing procedure-specific tests to prepare them. Patients may need multiple tests, each performed by a specialized operator and delivered in any order. Exam rooms act as renewable resources: rooms are limited, tests are administered to patients inside the rooms, individually, and patients occupy the room until all the required tests are completed. Careful scheduling of patient appointments is essential in clinic management for both the patient and the provider: on the one hand, minimizing patient waiting time improves service quality, on the other hand, minimizing completion time (makespan) improves system efficiency. In this paper, we propose offline policies for the daily scheduling of pre-admission test appointments. As a benchmark, we consider two online scheduling policies widely used in common practice. Each of these offers a different compromise between complexity and resource exploitation. The proposed optimization-based offline booking policy is identified as a new problem in the machine scheduling literature, for which we propose a network-flow model representation. A family of matheuristics based on different variable fixing criteria is provided to circumvent the high computational effort required to solve the mathematical model to optimality on real-size instances. The performance, advantages and disadvantages of each of the online and offline policies are compared in a variety of scenarios based on realistic data. Through this work, decision-makers have a new set of tools they can choose from according to their priorities.