Document Open Access Logo

Robust Appointment Scheduling

Authors Shashi Mittal, Andreas S. Schulz, Sebastian Stiller

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2014.356.pdf
  • Filesize: 469 kB
  • 15 pages

Document Identifiers

Author Details

Shashi Mittal
Andreas S. Schulz
Sebastian Stiller

Cite As Get BibTex

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) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.356

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.

Subject Classification

Keywords
  • Robust Optimization
  • Health Care Scheduling
  • Approximation Algorithms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Mehmet A. Begen, Retsef Levi, and M. Queyranne. A sampling-based approach to appointment scheduling. Technical report, Sauder School of Business, University of British Columbia, 2008. Working Paper. Google Scholar
  2. Mehmet A. Begen and Maurice Queyranne. Appointment scheduling with discrete random durations. Mathematics of Operations Research, 36:240-257, 2011. Google Scholar
  3. Aharon Ben-Tal and Arkadi Nemirovski. Robust optimization - methodology and applications. Mathematical Programming, 92:453-480, 2002. Google Scholar
  4. Dimitris Bertsimas and Melvyn Sim. The price of robustness. Operations Research, 52:35-53, 2004. Google Scholar
  5. T. Cayirli and E. Veral. Outpatient scheduling in healthcare: a review of literature. Production and Operations Management, 12:519-549, 2003. Google Scholar
  6. Brian Denton and Diwakar Gupta. A sequential bounding approach for optimal appointment scheduling. IIE Transactions, 35:1003-1016, 2003. Google Scholar
  7. Satoru Fujishige. Submodular Functions and Optimization, volume 58 of Annals of Discrete Mathematics. Elsevier, 2005. 2nd edition. Google Scholar
  8. Linda V. Green, Sergei Savin, and Ben Wang. Managing patient service in a diagnostic medical facility. Operations Research, 54:11-25, 2006. Google Scholar
  9. Diwakar Gupta. Surgical suites' operations management. Productions and Operations Management, 16:689-700, 2007. Google Scholar
  10. Wiebke Höhn and Tobias Jacobs. On the performance of Smith’s rule in single-machine scheduling with nonlinear cost. In LATIN, pages 482-493, 2012. Google Scholar
  11. Oscar H. Ibarra and Chul E. Kim. Fast approximation algorithms for the knapsack and sum of subset problems. Journal of the ACM, 22:463-468, 1975. Google Scholar
  12. Satoru Iwata. Submodular function minimization. Mathematical Programming, 112:45-64, 2008. Google Scholar
  13. Guido C. Kandoorp and Ger Koole. Optimal outpatient appointment scheduling. Health Care Management Science, 10:217-229, 2007. Google Scholar
  14. Nicole Megow and José Verschae. Dual techniques for scheduling on a machine with varying speed. In ICALP, pages 745-756, 2013. Google Scholar
  15. James B. Orlin. A faster strongly polynomial time algorithm for submodular function minimization. Mathematical Programming, 118:237-251, 2009. Google Scholar
  16. Maurice Queyranne. Structure of a simple scheduling polyhedron. Mathematical Programming, 58:263-285, 1993. Google Scholar
  17. Lawrence W. Robinson and Rachel R. Chen. Scheduling doctor’s appointments: Optimal and empirically-based heuristic policies. IIE Transactions, 35:295-307, 2003. Google Scholar
  18. W. E. Smith. Various optimizers for single-stage production. Naval Research Logistics Quarterly, 3:59-66, 1956. Google Scholar
  19. Sebastian Stiller and Andreas Wiese. Increasing speed scheduling and flow scheduling. In ISAAC, pages 279-290, 2010. Google Scholar
  20. P. Patrick Wang. Static and dynamic scheduling of customer arrivals to a single-server system. Naval Research Logistics, 40:345-360, 1993. Google Scholar
  21. P. Patrick Wang. Sequencing and scheduling n customers for a stochastic server. European Journal of Operational Research, 119:729-738, 1999. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact