Data-Driven Distributionally Robust Appointment Scheduling over Wasserstein Balls
Pith reviewed 2026-05-25 01:51 UTC · model grok-4.3
The pith
A data-driven distributionally robust model for appointment scheduling converges to the true optimum as the number of historical samples grows.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
For two stochastic appointment models—one with random service times and one that also includes random no-shows—the authors formulate data-driven DRO problems over Wasserstein balls. They prove that the optimal value and the set of optimal schedules converge to those of the true probability distribution as the number of samples tends to infinity. The resulting infinite-dimensional problems are recast as copositive programs, which are then approximated by tractable semidefinite programs, and under additional conditions reduced exactly to finite linear programs of polynomial size.
What carries the argument
The Wasserstein-ball ambiguity set in the distributionally robust formulation, which simultaneously encodes robustness to distributional uncertainty and guarantees asymptotic consistency with the true distribution.
If this is right
- Optimal appointment schedules obtained from the model become arbitrarily close to the true optimum for sufficiently large data sets.
- The models can be solved to high accuracy via standard semidefinite programming solvers.
- Under mild conditions the same models reduce to ordinary linear programs whose size grows only polynomially with the number of appointments.
- The schedules produced by the approach exhibit improved performance on new, unseen realizations compared with two existing methods.
Where Pith is reading between the lines
- The same Wasserstein DRO construction could be applied to multi-server or networked appointment systems while preserving the convergence property.
- If data arrive from a process that is not i.i.d., the convergence guarantee would no longer apply and a different ambiguity set might be needed.
- The copositive reformulation technique may transfer to other appointment or queueing problems that admit similar cost structures.
Load-bearing premise
The historical data consist of independent samples drawn from the unknown true distribution.
What would settle it
An experiment in which the gap between the DRO optimal cost and the true-model optimal cost fails to shrink toward zero as the number of historical samples is increased while keeping the true distribution fixed.
Figures
read the original abstract
We study a single-server appointment scheduling problem with a fixed sequence of appointments, for which we must determine the arrival time for each appointment. We specifically examine two stochastic models. In the first model, we assume that all appointees show up at the scheduled arrival times yet their service durations are random. In the second model, we assume that appointees have random no-show behaviors and their service durations are random given that they show up at the appointments. In both models, we assume that the probability distribution of the uncertain parameters is unknown but can be partially observed via a set of historical data, which we view as independent samples drawn from the unknown distribution. In view of the distributional ambiguity, we propose a data-driven distributionally robust optimization (DRO) approach to determine an appointment schedule such that the worst-case (i.e., maximum) expectation of the system total cost is minimized. A key feature of this approach is that the optimal value and the set of optimal schedules thus obtained provably converge to those of the true model, i.e., the stochastic appointment scheduling model with regard to the true probability distribution of the uncertain parameters. While our DRO models are computationally intractable in general, we reformulate them to copositive programs, which are amenable to tractable semidefinite programming problems with high-quality approximations. Furthermore, under some mild conditions, we recast these models as polynomial-sized linear programs. Through an extensive numerical study, we demonstrate that our approach yields better out-of-sample performance than two state-of-the-art methods.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript proposes a data-driven distributionally robust optimization (DRO) approach for single-server appointment scheduling under two stochastic models: (i) random service durations with all appointees showing up, and (ii) random no-shows combined with conditional random service durations. Historical data are treated as i.i.d. samples from an unknown distribution; Wasserstein balls centered at the empirical distribution are used to minimize the worst-case expected total cost. The paper proves that both the optimal value and the set of optimal schedules converge to those of the true distribution as the sample size grows. The resulting DRO models are reformulated as copositive programs (approximable by SDPs) and, under mild conditions, as polynomial-sized linear programs. Numerical experiments claim superior out-of-sample performance relative to two benchmark methods.
Significance. If the convergence results and reformulations are correct, the work supplies a theoretically grounded, asymptotically consistent method for robust scheduling that directly addresses distributional ambiguity via Wasserstein distance. The explicit consistency guarantee and the reduction to tractable LPs under stated conditions are strengths that distinguish the contribution within data-driven DRO literature for stochastic programming. The numerical validation, if reproducible, supports practical relevance in healthcare operations research.
major comments (2)
- [§4] §4 (convergence analysis): The proof that optimal schedules converge to the true-model optimum is conditioned on the i.i.d. sampling assumption stated in the abstract and §2; while this is standard, the argument does not address whether the Wasserstein radius selection (which must shrink with n) remains valid or how the rate degrades under mild dependence, making the load-bearing asymptotic claim sensitive to this modeling choice.
- [§5.2, Theorem 5.3] §5.2, Theorem 5.3 (LP reformulation): The 'mild conditions' under which the copositive program reduces to a polynomial-sized LP are not explicitly verified against the piecewise-linear or indicator-based cost functions arising from the no-show model; without this check the claim that the LP is available for both stochastic models is not fully supported.
minor comments (2)
- [§2] Notation for the total cost function (waiting, idle, and overtime components) is introduced in §2 but the precise functional form used in the numerical instances should be restated in the caption of Table 1 or Figure 2 for clarity.
- [§6] The description of how the Wasserstein radius is chosen in the numerical study (§6) is brief; adding the explicit functional form (e.g., scaling with n^{-1/2}) would improve reproducibility.
Simulated Author's Rebuttal
We thank the referee for the constructive comments and the recommendation for minor revision. We address each major comment point by point below.
read point-by-point responses
-
Referee: [§4] §4 (convergence analysis): The proof that optimal schedules converge to the true-model optimum is conditioned on the i.i.d. sampling assumption stated in the abstract and §2; while this is standard, the argument does not address whether the Wasserstein radius selection (which must shrink with n) remains valid or how the rate degrades under mild dependence, making the load-bearing asymptotic claim sensitive to this modeling choice.
Authors: The convergence analysis in §4 is explicitly conditioned on the i.i.d. sampling assumption stated in the abstract and §2, which is the standard setting for such consistency results in data-driven DRO. The Wasserstein radius is chosen to shrink with n (e.g., on the order of n^{-1/2} via concentration inequalities) to ensure the optimal value and solutions converge to the true stochastic optimum. The proof relies on this i.i.d. structure and does not claim validity under dependence. Extending the analysis to dependent samples would require different concentration tools and is beyond the paper's scope. We will add a remark in §4 noting the i.i.d. assumption and the corresponding radius selection. revision: partial
-
Referee: [§5.2, Theorem 5.3] §5.2, Theorem 5.3 (LP reformulation): The 'mild conditions' under which the copositive program reduces to a polynomial-sized LP are not explicitly verified against the piecewise-linear or indicator-based cost functions arising from the no-show model; without this check the claim that the LP is available for both stochastic models is not fully supported.
Authors: We thank the referee for this observation. The cost functions in the no-show model are piecewise linear (waiting, idle, and overtime costs) combined with indicators for no-shows, which admit a finite piecewise-linear representation. These satisfy the mild conditions of Theorem 5.3. We will add an explicit verification in the revised §5.2 confirming that the conditions hold for both models, supporting the availability of the polynomial-sized LP reformulation. revision: yes
- Analysis of convergence results and radius selection under mild dependence in the sampling process
Circularity Check
No circularity; convergence claim rests on standard i.i.d. assumption and external DRO duality
full rationale
The paper states the i.i.d. sampling assumption explicitly as the basis for both the Wasserstein ball construction and the asymptotic convergence of optimal values/schedules to the true model. Reformulations to copositive programs and polynomial LPs are presented as consequences of standard DRO duality arguments (no equations reduce a prediction to a fitted input by construction). No self-citation is invoked as the sole justification for a uniqueness theorem or ansatz that would force the result. The derivation chain remains independent of the paper's own fitted quantities and is self-contained against external DRO theory.
Axiom & Free-Parameter Ledger
axioms (1)
- domain assumption Historical data consist of independent samples drawn from the unknown distribution
Lean theorems connected to this paper
-
IndisputableMonolith/Foundation/RealityFromDistinction.leanreality_from_one_distinction unclear?
unclearRelation between the paper passage and the cited Recognition theorem.
We assume that the probability distribution of the uncertain parameters is unknown but can be partially observed via a set of historical data, which we view as independent samples drawn from the unknown distribution... provably converge to those of the true model
-
IndisputableMonolith/Cost/FunctionalEquation.leanwashburn_uniqueness_aczel unclear?
unclearRelation between the paper passage and the cited Recognition theorem.
Wasserstein distance... ambiguity set Dp(ˆPNu,ϵ)
What do these tags mean?
- matches
- The paper's claim is directly supported by a theorem in the formal canon.
- supports
- The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
- extends
- The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
- uses
- The paper appears to rely on the theorem as machinery.
- contradicts
- The paper's claim conflicts with a theorem or certificate in the canon.
- unclear
- Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.
Reference graph
Works this paper leans on
-
[1]
Outpatient appointment systems in healthcare: A review of optimization studies
Amir Ahmadi-Javid, Zahra Jalali, and Kenneth J Klassen. Outpatient appointment systems in healthcare: A review of optimization studies. European Journal of Operational Research , 258(1):3–34, 2017
work page 2017
-
[2]
The MOSEK optimization toolbox for MATLAB manual
MOSEK ApS. The MOSEK optimization toolbox for MATLAB manual. Version 8.0. , 2016
work page 2016
-
[3]
Norman TJ Bailey. A study of queues and appointment systems in hospital out-patient de- partments, with special reference to waiting-times. Journal of the Royal Statistical Society. Series B (Methodological), pages 185–199, 1952
work page 1952
-
[4]
A sampling-based approach to ap- pointment scheduling
Mehmet A Begen, Retsef Levi, and Maurice Queyranne. A sampling-based approach to ap- pointment scheduling. Operations Research, 60(3):675–681, 2012
work page 2012
-
[5]
Appointment scheduling with discrete random durations
Mehmet A Begen and Maurice Queyranne. Appointment scheduling with discrete random durations. Mathematics of Operations Research, 36(2):240–257, 2011
work page 2011
-
[6]
Ahron Ben-Tal and Arkadi Nemirovski. Lectures on Modern Convex Optimization: analysis, algorithms, and engineering applications , volume 2. SIAM, 2001
work page 2001
-
[7]
Optimal booking and scheduling in outpatient procedure centers
Bjorn P Berg, Brian T Denton, S Ayca Erdogan, Thomas Rohleder, and Todd Huschka. Optimal booking and scheduling in outpatient procedure centers. Computers & Operations Research, 50:24–37, 2014
work page 2014
-
[8]
Dimitris Bertsimas, Xuan Vinh Doan, Karthik Natarajan, and Chung-Piaw Teo. Models for minimax stochastic linear optimization problems with risk aversion.Mathematics of Operations Research, 35(3):580–602, 2010
work page 2010
-
[9]
Robust sample average approximation
Dimitris Bertsimas, Vishal Gupta, and Nathan Kallus. Robust sample average approximation. Mathematical Programming, pages 1–66, 2017
work page 2017
-
[10]
Optimal inequalities in probability theory: A convex optimization approach
Dimitris Bertsimas and Ioana Popescu. Optimal inequalities in probability theory: A convex optimization approach. SIAM Journal on Optimization , 15(3):780–804, 2005
work page 2005
-
[11]
Immanuel M Bomze and Etienne De Klerk. Solving standard quadratic optimization prob- lems via linear, semidefinite and copositive programming. Journal of Global Optimization , 24(2):163–185, 2002
work page 2002
-
[12]
Queueing models for out-patient appointment systemsa case study
M Brahimi and DJ Worthington. Queueing models for out-patient appointment systemsa case study. Journal of the Operational Research Society , 42(9):733–746, 1991
work page 1991
-
[13]
S. Burer. On the copositive representation of binary and continuous nonconvex quadratic programs. Mathematical Programming Series A, 120(2):479–495, September 2009. 52
work page 2009
-
[14]
Samuel Burer. Copositive programming. In M.F. Anjos and J.B. Lasserre, editors, Handbook of Semidefinite, Cone and Polynomial Optimization: Theory, Algorithms, Software and Appli- cations, International Series in Operational Research and Management Science, pages 201–218. Springer, 2011
work page 2011
-
[15]
Samuel Burer. Copositive programming. In Handbook on semidefinite, conic and polynomial optimization, pages 201–218. Springer, 2012
work page 2012
-
[16]
A gentle, geometric introduction to copositive optimization
Samuel Burer. A gentle, geometric introduction to copositive optimization. Mathematical Programming, 151(1):89–116, 2015
work page 2015
-
[17]
Operating room planning and scheduling: A literature review
Brecht Cardoen, Erik Demeulemeester, and Jeroen Beli¨ en. Operating room planning and scheduling: A literature review. European journal of operational research , 201(3):921–932, 2010
work page 2010
-
[18]
Opatient scheduling in health care: a review of literature
Tugba Cayirli and Emre Veral. Opatient scheduling in health care: a review of literature. Production and operations management, 12(4):519–549, 2003
work page 2003
-
[19]
Sequencing and scheduling appointments with potential call-in patients
Rachel R Chen and Lawrence W Robinson. Sequencing and scheduling appointments with potential call-in patients. Production and Operations Management, 23(9):1522–1538, 2014
work page 2014
-
[20]
Approximation of the stability number of a graph via copositive programming
Etienne De Klerk and Dmitrii V Pasechnik. Approximation of the stability number of a graph via copositive programming. SIAM Journal on Optimization , 12(4):875–892, 2002
work page 2002
-
[21]
Erick Delage and Yinyu Ye. Distributionally robust optimization under moment uncertainty with application to data-driven problems. Operations research, 58(3):595–612, 2010
work page 2010
-
[22]
A sequential bounding approach for optimal appointment scheduling
Brian Denton and Diwakar Gupta. A sequential bounding approach for optimal appointment scheduling. IIE transactions, 35(11):1003–1016, 2003
work page 2003
-
[23]
Optimization of surgery sequencing and scheduling decisions under uncertainty
Brian Denton, James Viapiano, and Andrea Vogl. Optimization of surgery sequencing and scheduling decisions under uncertainty. Health care management science, 10(1):13–24, 2007
work page 2007
-
[24]
Copositive programminga survey
Mirjam D¨ ur. Copositive programminga survey. Recent advances in optimization and its ap- plications in engineering, 320, 2010
work page 2010
-
[25]
Dynamic appointment scheduling of a stochastic server with uncertain demand
S Ayca Erdogan and Brian Denton. Dynamic appointment scheduling of a stochastic server with uncertain demand. INFORMS Journal on Computing , 25(1):116–132, 2013
work page 2013
-
[26]
Peyman Mohajerin Esfahani and Daniel Kuhn. Data-driven distributionally robust optimiza- tion using the wasserstein metric: Performance guarantees and tractable reformulations. Math- ematical Programming, 171(1-2):115–166, 2018
work page 2018
-
[27]
On the core of ordered submodular cost games
Ulrich Faigle and Walter Kern. On the core of ordered submodular cost games. Mathematical Programming, 87(3):483–499, 2000. 53
work page 2000
-
[28]
Patients’ waiting time and doctors’ idle time in the outpatient setting
Robert B Fetter and John D Thompson. Patients’ waiting time and doctors’ idle time in the outpatient setting. Health services research, 1(1):66, 1966
work page 1966
-
[29]
On the rate of convergence in wasserstein distance of the empirical measure
Nicolas Fournier and Arnaud Guillin. On the rate of convergence in wasserstein distance of the empirical measure. Probability Theory and Related Fields , 162(3-4):707–738, 2015
work page 2015
-
[30]
A note on appointment schedul- ing with piecewise linear cost functions
Dongdong Ge, Guohua Wan, Zizhuo Wang, and Jiawei Zhang. A note on appointment schedul- ing with piecewise linear cost functions. Mathematics of Operations Research, 39(4):1244–1251, 2013
work page 2013
-
[31]
Distributionally robust optimization and its tractable approxima- tions
Joel Goh and Melvyn Sim. Distributionally robust optimization and its tractable approxima- tions. Operations research, 58(4-part-1):902–917, 2010
work page 2010
-
[32]
The ellipsoid method and its consequences in combinatorial optimization
Martin Gr¨ otschel, L´ aszl´ o Lov´ asz, and Alexander Schrijver. The ellipsoid method and its consequences in combinatorial optimization. Combinatorica, 1(2):169–197, 1981
work page 1981
-
[33]
Appointment scheduling in health care: Challenges and opportunities
Diwakar Gupta and Brian Denton. Appointment scheduling in health care: Challenges and opportunities. IIE transactions, 40(9):800–819, 2008
work page 2008
-
[34]
Staffing call centers with uncertain demand forecasts: A chance-constrained optimization approach
Itai Gurvich, James Luedtke, and Tolga Tezcan. Staffing call centers with uncertain demand forecasts: A chance-constrained optimization approach. Management Science , 56(7):1093– 1115, 2010
work page 2010
-
[35]
Grani A Hanasusanto and Daniel Kuhn. Conic programming reformulations of two-stage dis- tributionally robust linear programs over wasserstein balls. Operations Research, Forthcoming, 2018
work page 2018
-
[36]
Ambiguous joint chance constraints under mean and dispersion information
Grani A Hanasusanto, Vladimir Roitch, Daniel Kuhn, and Wolfram Wiesemann. Ambiguous joint chance constraints under mean and dispersion information. Operations Research, 2017
work page 2017
-
[37]
Scheduling arrivals to queues: A single-server model with no-shows
Refael Hassin and Sharon Mendel. Scheduling arrivals to queues: A single-server model with no-shows. Management science, 54(3):565–572, 2008
work page 2008
-
[38]
Data-driven patient scheduling in emer- gency departments: A hybrid robust-stochastic approach
Shuangchi He, Melvyn Sim, and Meilin Zhang. Data-driven patient scheduling in emer- gency departments: A hybrid robust-stochastic approach. Available at Optimization-Online http://www. optimization-online. org/DB HTML/2015/11/5213. html, 2015
work page 2015
-
[39]
Minimizing total cost in scheduling outpatient appoint- ments
Chrwan-Jyh Ho and Hon-Shiang Lau. Minimizing total cost in scheduling outpatient appoint- ments. Management science, 38(12):1750–1764, 1992
work page 1992
-
[40]
Ruiwei Jiang, Siqian Shen, and Yiling Zhang. Integer programming approaches for ap- pointment scheduling with random no-shows and service durations. Operations Research, 65(6):1638–1656, 2017
work page 2017
-
[41]
Optimal outpatient appointment scheduling
Guido C Kaandorp and Ger Koole. Optimal outpatient appointment scheduling. Health Care Management Science, 10(3):217–229, 2007. 54
work page 2007
-
[42]
Peter Kall and Stein W Wallace. Stochastic programming. Springer, 1994
work page 1994
-
[43]
Scheduling arrivals to a stochastic service delivery system using copositive cones
Qingxia Kong, Chung-Yee Lee, Chung-Piaw Teo, and Zhichao Zheng. Scheduling arrivals to a stochastic service delivery system using copositive cones. Operations research, 61(3):711–726, 2013
work page 2013
-
[44]
Appointment schedul- ing under schedule-dependent patient no-show behavior, 2015
Qingxia Kong, Shan Li, Nan Liu, Chung-Piaw Teo, and Zhenzhen Yan. Appointment schedul- ing under schedule-dependent patient no-show behavior, 2015
work page 2015
-
[45]
Clinic overbooking to improve patient access and increase provider productivity
Linda R LaGanga and Stephen R Lawrence. Clinic overbooking to improve patient access and increase provider productivity. Decision Sciences, 38(2):251–276, 2007
work page 2007
-
[46]
Appointment overbooking in health care clinics to improve patient service and clinic performance
Linda R LaGanga and Stephen R Lawrence. Appointment overbooking in health care clinics to improve patient service and clinic performance. Production and Operations Management , 21(5):874–888, 2012
work page 2012
-
[47]
Convexity in semialgebraic geometry and polynomial optimization
Jean B Lasserre. Convexity in semialgebraic geometry and polynomial optimization. SIAM Journal on Optimization , 19(4):1995–2014, 2009
work page 1995
-
[48]
Panel size and overbooking decisions for appointment-based services under patient no-shows
Nan Liu and Serhan Ziya. Panel size and overbooking decisions for appointment-based services under patient no-shows. Production and Operations Management, 23(12):2209–2223, 2014
work page 2014
-
[49]
Truth in scheduling: is it possible to accurately predict how long a surgical case will last?, 2009
Alex Macario. Truth in scheduling: is it possible to accurately predict how long a surgical case will last?, 2009
work page 2009
-
[50]
Sequencing appointments for service systems using inventory approximations
Ho-Yin Mak, Ying Rong, and Jiawei Zhang. Sequencing appointments for service systems using inventory approximations. Manufacturing & Service Operations Management , 16(2):251–262, 2014
work page 2014
-
[51]
Appointment scheduling with limited distribu- tional information
Ho-Yin Mak, Ying Rong, and Jiawei Zhang. Appointment scheduling with limited distribu- tional information. Management Science, 61(2):316–334, 2015
work page 2015
-
[52]
Shashi Mittal, Andreas S Schulz, and Sebastian Stiller. Robust appointment scheduling. In LIPIcs-Leibniz International Proceedings in Informatics, volume 28. Schloss Dagstuhl-Leibniz- Zentrum fuer Informatik, 2014
work page 2014
-
[53]
Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization
Pablo A Parrilo. Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization . PhD thesis, California Institute of Technology, 2000
work page 2000
-
[54]
Ambiguity in portfolio selection
Georg Pflug and David Wozabal. Ambiguity in portfolio selection. Quantitative Finance , 7(4):435–442, 2007
work page 2007
-
[55]
Robust optimisation of operating theatre schedules
Elizabeth Louise Rowse. Robust optimisation of operating theatre schedules . PhD thesis, Cardiff University, 2015
work page 2015
-
[56]
A min-max solution of an inventory problem
Herbert Scarf. A min-max solution of an inventory problem. Studies in the mathematical theory of inventory and production , 1958. 55
work page 1958
-
[57]
On duality theory of conic linear problems
Alexander Shapiro. On duality theory of conic linear problems. In Semi-infinite programming, pages 135–165. Springer, 2001
work page 2001
-
[58]
Lectures on stochastic pro- gramming: modeling and theory , volume 16
Alexander Shapiro, Darinka Dentcheva, and Andrzej Ruszczynski. Lectures on stochastic pro- gramming: modeling and theory , volume 16. SIAM, 2014
work page 2014
-
[59]
Stochastic modeling and approaches for managing energy footprints in cloud computing service
Siqian Shen and Jue Wang. Stochastic modeling and approaches for managing energy footprints in cloud computing service. Service Science, 6(1):15–33, 2014
work page 2014
-
[60]
Sdpt3a matlab software package for semidefinite programming, version 1.3
Kim-Chuan Toh, Michael J Todd, and Reha H T¨ ut¨ unc¨ u. Sdpt3a matlab software package for semidefinite programming, version 1.3. Optimization methods and software , 11(1-4):545–581, 1999
work page 1999
-
[61]
A framework for optimization under ambiguity
David Wozabal. A framework for optimization under ambiguity. Annals of Operations Re- search, 193(1):21–47, 2012
work page 2012
-
[62]
Improved decision rule approximations for multi-stage robust optimization via copositive programming
Guanglin Xu and Grani A Hanasusanto. Improved decision rule approximations for multi-stage robust optimization via copositive programming. arXiv preprint arXiv:1808.06231 , 2018
-
[63]
Appointment scheduling with no-shows and overbook- ing
Christos Zacharias and Michael Pinedo. Appointment scheduling with no-shows and overbook- ing. Production and Operations Management, 23(5):788–801, 2014
work page 2014
-
[64]
Managing customer arrivals in service systems with multiple identical servers
Christos Zacharias and Michael Pinedo. Managing customer arrivals in service systems with multiple identical servers. Manufacturing & Service Operations Management , 19(4):639–656, 2017
work page 2017
-
[65]
A deterministic multi-period production scheduling model with backlog- ging
Willard I Zangwill. A deterministic multi-period production scheduling model with backlog- ging. Management Science, 13(1):105–119, 1966
work page 1966
-
[66]
Willard I Zangwill. A backlogging model and a multi-echelon model of a dynamic economic lot size production systema network approach. Management Science, 15(9):506–527, 1969. 56
work page 1969
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.