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

DOI10.1287/OPRE.2020.2025zbMATH Open1482.90090arXiv1812.01467OpenAlexW3124064250MaRDI QIDQ5031672FDOQ5031672

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)

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.

Full work available at URL: https://arxiv.org/abs/1812.01467

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

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)

Cites Work

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

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)