DROPS

Document

DOI: 10.4230/LIPIcs.APPROX-RANDOM.2014.356

Robust Appointment Scheduling

Authors: Shashi Mittal, Andreas S. Schulz, and Sebastian Stiller

Published in: LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)

Abstract

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.

Cite as

Shashi Mittal, Andreas S. Schulz, and Sebastian Stiller. Robust Appointment Scheduling. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 356-370, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{mittal_et_al:LIPIcs.APPROX-RANDOM.2014.356,
  author =	{Mittal, Shashi and Schulz, Andreas S. and Stiller, Sebastian},
  title =	{{Robust Appointment Scheduling}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{356--370},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.356},
  URN =		{urn:nbn:de:0030-drops-47089},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.356},
  annote =	{Keywords: Robust Optimization, Health Care Scheduling, Approximation Algorithms}
}

Search Results

Documents authored by Mittal, Shashi

Robust Appointment Scheduling

Abstract

Cite as

Thanks for your feedback!

Could not send message