Document Open Access Logo

Robust Appointment Scheduling with Heterogeneous Costs

Authors Andreas S. Schulz, Rajan Udwani

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2019.25.pdf
  • Filesize: 0.48 MB
  • 17 pages

Document Identifiers

Author Details

Andreas S. Schulz
  • Technische Universität München, Germany
Rajan Udwani
  • Columbia University, New York, NY, USA

Funding

  • Schulz, Andreas S.: Alexander von Humboldt Foundation (with funds from BMBF)
  • Udwani, Rajan: ONR Grant N00014-17-1-2194, NSF Grant CMMI 1636046

Acknowledgements

The authors would like to thank James B. Orlin for helpful discussions.

Cite As Get BibTex

Andreas S. Schulz and Rajan Udwani. Robust Appointment Scheduling with Heterogeneous Costs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 25:1-25:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2019.25

Abstract

Designing simple appointment systems that under uncertainty in service times, try to achieve both high utilization of expensive medical equipment and personnel as well as short waiting time for patients, has long been an interesting and challenging problem in health care. We consider a robust version of the appointment scheduling problem, introduced by Mittal et al. (2014), with the goal of finding simple and easy-to-use algorithms. Previous work focused on the special case where per-unit costs due to under-utilization of equipment/personnel are homogeneous i.e., costs are linear and identical. We consider the heterogeneous case and devise an LP that has a simple closed-form solution. This solution yields the first constant-factor approximation for the problem. We also find special cases beyond homogeneous costs where the LP leads to closed form optimal schedules. Our approach and results extend more generally to convex piece-wise linear costs.
For the case where the order of patients is changeable, we focus on linear costs and show that the problem is strongly NP-hard when the under-utilization costs are heterogeneous. For changeable order with homogeneous under-utilization costs, it was previously shown that an EPTAS exists. We instead find an extremely simple, ratio-based ordering that is 1.0604 approximate.

Subject Classification

ACM Subject Classification
  • Theory of computation → Approximation algorithms analysis
  • Theory of computation → Discrete optimization
  • Theory of computation → Scheduling algorithms
Keywords
  • Appointment scheduling
  • approximation algorithms
  • robust optimization

Metrics

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

References

  1. M. A Begen, R. Levi, and M. Queyranne. A sampling-based approach to appointment scheduling. Operations Research, 60(3):675-681, 2012. Google Scholar
  2. M. A Begen and M. Queyranne. Appointment scheduling with discrete random durations. Mathematics of Operations Research, 36(2):240-257, 2011. Google Scholar
  3. A. Ben-Tal and A. Nemirovski. Robust optimization-methodology and applications. Mathematical Programming, 92(3):453-480, 2002. Google Scholar
  4. D. Bertsimas, D. Brown, and C. Caramanis. Theory and applications of robust optimization. SIAM Review, 53(3):464-501, 2011. Google Scholar
  5. D. Bertsimas and M. Sim. The price of robustness. Operations Research, 52(1):35-53, 2004. Google Scholar
  6. T. Cayirli and E. Veral. Outpatient scheduling in health care: a review of literature. Production and Operations Management, 12(4):519-549, 2003. Google Scholar
  7. M. Cheung, J. Mestre, D. B. Shmoys, and J. Verschae. A Primal-Dual Approximation Algorithm for Min-Sum Single-Machine Scheduling Problems. SIAM Journal on Discrete Mathematics, 31(2):825-838, 2017. Google Scholar
  8. B. Denton and D. Gupta. A sequential bounding approach for optimal appointment scheduling. IIE Transactions, 35(11):1003-1016, 2003. Google Scholar
  9. M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., 1979. Google Scholar
  10. D. Ge, G. Wan, Z. Wang, and J. Zhang. A note on appointment scheduling with piecewise linear cost functions. Mathematics of Operations Research, 39(4):1244-1251, 2013. Google Scholar
  11. L. V. Green, S. Savin, and B. Wang. Managing patient service in a diagnostic medical facility. Operations Research, 54(1):11-25, 2006. Google Scholar
  12. W. Höhn and T. Jacobs. On the performance of Smith’s rule in single-machine scheduling with nonlinear cost. ACM Transactions on Algorithms, 11(4):25, 2015. Google Scholar
  13. IBM and Carnegie Mellon University. Couenne, an exact solver for nonconvex MINLPs. https://projects.coin-or.org/Couenne/, 2006.
  14. R. Jiang, S. Shen, and Y. Zhang. Integer programming approaches for appointment scheduling with random no-shows and service durations. Operations Research, 65(6):1638-1656, 2017. Google Scholar
  15. G. C. Kaandorp and G. Koole. Optimal outpatient appointment scheduling. Health Care Management Science, 10(3):217-229, 2007. Google Scholar
  16. Q. Kong, C. Lee, C. Teo, and Z. Zheng. Scheduling arrivals to a stochastic service delivery system using copositive cones. Operations Research, 61(3):711-726, 2013. Google Scholar
  17. A. Macario. Is it possible to predict how long a surgery will last? Medscape Anesthesiology, 108(3):681-685, 2010. Google Scholar
  18. H. Mak, Y. Rong, and J. Zhang. Appointment scheduling with limited distributional information. Management Science, 61(2):316-334, 2014. Google Scholar
  19. N. Megow and J. Verschae. Dual techniques for scheduling on a machine with varying speed. In Automata, Languages, and Programming - 40th International Colloquium (ICALP), pages 745-756, 2013. Google Scholar
  20. S. Mittal, A. S. Schulz, and S. Stiller. Robust appointment scheduling. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2014. Google Scholar
  21. J. Orlin. Personal communication, 2018. Google Scholar
  22. Y. Pinto and R. Shamir. Efficient algorithms for minimum-cost flow problems with piecewise-linear convex costs. Algorithmica, 11(3):256-277, 1994. Google Scholar
  23. L. W. Robinson and R. R. Chen. Scheduling doctors' appointments: optimal and empirically-based heuristic policies. IIE Transactions, 35(3):295-307, 2003. Google Scholar
  24. W. E. Smith. Various optimizers for single-stage production. Naval Research Logistics, 3(1-2):59-66, 1956. Google Scholar
  25. S. Stiller and A. Wiese. Increasing Speed Scheduling and Flow Scheduling. In Algorithms and Computation - 21st International Symposium (ISAAC), pages 279-290, 2010. Google Scholar
  26. P. P. Wang. Static and dynamic scheduling of customer arrivals to a single-server system. Naval Research Logistics, 40(3):345-360, 1993. Google Scholar
  27. P. P. Wang. Sequencing and scheduling n customers for a stochastic server. European Journal of Operational Research, 119(3):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