Performance of the smallest-variance-first rule in appointment sequencing

DOI10.1287/OPRE.2020.2025MaRDI QIDQ5031672zbMATH OpenOpenAlexFDO

Authors Madelon A. de Kemp, Neil Olver, M. R. H. Mandjes

Publication date 16 February 2022

Published in Operations Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1812.01467, http://eprints.lse.ac.uk/104585/1/Performance_of_the_smallest_.pdf

zbMATH Keywords

approximation algorithmsappointment scheduling and sequencing

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Deterministic scheduling theory in operations research (90B35)

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 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.

Recommendations

• Appointment sequencing: why the smallest-variance-first rule may not be optimal
• Sequencing in an appointment system with deterministic arrivals and non-identical exponential service times
• Optimized appointment scheduling
• A computational approach to optimized appointment scheduling
• Appointment scheduling with discrete random durations

Cites work

• scientific article; zbMATH DE number 994723 (Why is no real title available?)
• scientific article; zbMATH DE number 3072483 (Why is no real title available?)
• A computational approach to optimized appointment scheduling
• Appointment scheduling with discrete random durations
• Appointment sequencing: why the smallest-variance-first rule may not be optimal
• On the Departure from Normality of a Certain Class of Martingales
• Optimal booking and scheduling in outpatient procedure centers
• Optimized appointment scheduling
• Outpatient appointment systems in healthcare: a review of optimization studies
• Robust appointment scheduling
• Scheduling arrivals to a stochastic service delivery system using copositive cones
• Scheduling. Theory, algorithms, and systems.
• Some inequalities for the queue GI/G/1
• Stochastic load balancing on unrelated machines
• Stochastic online scheduling on unrelated machines
• Stochastic orders
• Unrelated machine scheduling with stochastic processing times

Cited in

(4)

• Optimal sequencing using a scheduling heuristic
• Adaptive scheduling in service systems: a dynamic programming approach
• Sequencing in an appointment system with deterministic arrivals and non-identical exponential service times
• Appointment sequencing: why the smallest-variance-first rule may not be optimal

This page was built for publication: Performance of the smallest-variance-first rule in appointment sequencing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5031672)