2026-07-23T10:26:45Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4708 2024-03-06T10:35:17Z ddc:004 open_access

Robust Appointment Scheduling Mittal, Shashi Schulz, Andreas S. Stiller, Sebastian Robust Optimization Health Care Scheduling Approximation Algorithms Health care providers are under tremendous pressure to reduce costs and increase quality of their services. It has long been recognized that well-designed appointment systems have the potential to improve utilization of expensive personnel and medical equipment and to reduce waiting times for patients. In a widely influential survey on outpatient scheduling, Cayirli and Veral (2003) concluded that the "biggest challenge for future research will be to develop easy-to-use heuristics." We analyze the appointment scheduling problem from a robust-optimization perspective, and we establish the existence of a closed-form optimal solution--arguably the simplest and best `heuristic' possible. In case the order of patients is changeable, the robust optimization approach yields a novel formulation of the appointment scheduling problem as that of minimizing a concave function over a supermodular polyhedron. We devise the first constant-factor approximation algorithm for this case. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Shashi Mittal and Andreas S. Schulz and Sebastian Stiller 2014 Is Part Of LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2014.356 urn:nbn:de:0030-drops-47089 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.356 eng https://creativecommons.org/licenses/by/3.0/legalcode