  A classical problem in appointment scheduling, with applications in health
care, concerns the determination of the patients' arrival times that minimize a
cost function that is a weighted sum of mean waiting times and mean idle times.
One aspect of this problem is the sequencing problem, which focuses on ordering
the patients. We assess the performance of the smallest-variance-first (SVF)
rule, which sequences patients in order of increasing variance of their service
durations. While it was known that SVF is not always optimal, it has been
widely observed that it performs well in practice and simulation. We provide a
theoretical justification for this observation by proving, in various settings,
quantitative worst-case bounds on the ratio between the cost incurred by the
SVF rule and the minimum attainable cost. We also show that, in great
generality, SVF is asymptotically optimal, i.e., the ratio approaches 1 as the
number of patients grows large. While evaluating policies by considering an
approximation ratio is a standard approach in many algorithmic settings, our
results appear to be the first of this type in the appointment scheduling
literature.
