License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2014.356
URN: urn:nbn:de:0030-drops-47089
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2014/4708/
Go to the corresponding LIPIcs Volume Portal

Mittal, Shashi ; Schulz, Andreas S. ; Stiller, Sebastian

Robust Appointment Scheduling

pdf-format:
25.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{mittal_et_al:LIPIcs:2014:4708,
  author =	{Shashi Mittal and Andreas S. Schulz and Sebastian Stiller},
  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 =	{Klaus Jansen and Jos{\'e} D. P. Rolim and Nikhil R. Devanur and Cristopher Moore},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2014/4708},
  URN =		{urn:nbn:de:0030-drops-47089},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.356},
  annote =	{Keywords: Robust Optimization, Health Care Scheduling, Approximation Algorithms}
}

Keywords: Robust Optimization, Health Care Scheduling, Approximation Algorithms
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)
Issue Date: 2014
Date of publication: 04.09.2014

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI