Performance of the Smallest-Variance-First Rule in Appointment Sequencing

Madelon A. de Kemp (), Michel Mandjes () and Neil Olver ()
Additional contact information
Madelon A. de Kemp: Korteweg-de Vries Institute, University of Amsterdam, 1090 GE Amsterdam, Netherlands
Michel Mandjes: Korteweg-de Vries Institute, University of Amsterdam, 1090 GE Amsterdam, Netherlands
Neil Olver: Department of Mathematics, London School of Economics and Political Science, London WC2A 2AE, United Kingdom; Centrum Wiskunde & Informatica, 1098 XG Amsterdam, Netherlands

Operations Research, 2021, vol. 69, issue 6, 1909-1935

Abstract: A classic problem in appointment scheduling with applications in healthcare 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. Although it is 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, that is, the ratio approaches one as the number of patients grows large. Although 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.

Keywords: appointment scheduling and sequencing; approximation algorithms (search for similar items in EconPapers)
Date: 2021
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2020.2025 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:69:y:2021:i:6:p:1909-1935

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().