Robust Appointment Scheduling with Heterogeneous Costs
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.
Related
- Stochastic Appointment Scheduling with Patient-and-Time-Dependent Probability Distributions
- Whittle index approach to multi-server scheduling with convex delay costs and impatient customers
- Capacity Costs of Probability Ambiguity and Support Rectangularization in Edge–Cloud Scheduling
- Model-free and Distributionally Robust Feature Screening with False Discovery Control for High-Dimensional Heterogeneous Data
- Robust Heterogeneous Vehicle Routing Optimization for Hazmat Transportation Under Time-Varying Risk
BibTeX
@misc{schulz2026robust,
title = {{Robust Appointment Scheduling with Heterogeneous Costs}},
author = {Andreas S. Schulz and Rajan Udwani},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.01478},
eprint = {2611.01478},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.01478},
}
RIS
TY - UNPB
TI - Robust Appointment Scheduling with Heterogeneous Costs
AU - Andreas S. Schulz
AU - Rajan Udwani
PY - 2026
DA - 2026/11/01
PB - arXiv
DO - 10.48550/arxiv.2611.01478
UR - https://arxiv.org/abs/2611.01478
AB - 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.
ER -