Performance of the smallestvariancefirst rule in appointment sequencing
Abstract
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 smallestvariancefirst (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 worstcase 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.
 Publication:

arXiv eprints
 Pub Date:
 December 2018
 arXiv:
 arXiv:1812.01467
 Bibcode:
 2018arXiv181201467D
 Keywords:

 Mathematics  Probability;
 Computer Science  Data Structures and Algorithms;
 Mathematics  Optimization and Control;
 90B36 (Primary);
 68M20;
 60K30;
 68W25 (Secondary)
 EPrint:
 54 pages, 2 figures