Date and Time:
We consider distributionally robust (DR) single-server scheduling problem variants with a fixed sequence of appointments with random no-shows and service durations. The joint probability distribution is ambiguous and only the support and first moments are given. We study
DR models that incorporate the worst-case expected cost and the worst-case CVaR of waiting, idleness, and overtime as the objective or constraints. To solve the DR models, we derive exact mixed-integer nonlinear reformulations that facilitate decomposition algorithms. We also derive valid inequalities to strengthen the reformulations and accelerate the computation. In particular, in terms of no-show supports, our derivation leads to polynomial-size LP reformulations for the least conservative (i.e., no consecutive no-shows) and most conservative (i.e., arbitrary no-shows) cases. We test various instances, and derive the following insights: (i) accounting for no-shows in DR models significantly shortens waiting, (ii) one can improve the DR model's ability of utilizing distributional information by using reasonably conservative supports, and (iii) the DR models produce schedules having a ``plateau-half-dome'' shape.
Siqian Shen is an Assistant Professor of Industrial and Operations Engineering at the University of Michigan. She obtained a B.S. degree from Tsinghua University in 2007 and Ph.D. from the University of Florida in 2011. Her research interests are in mathematical optimization, particularly in stochastic programming, network optimization, and integer programming. Applications of her work include health care operations management, transportation, and cloud computing. She was named one of the two runners-up of the 2010 INFORMS Computing Society Best Student Paper award, was awarded the 1st Place of the 2012 IIE Pritsker Doctoral Dissertation Award, and was a recipient of 2012 IBM Smarter Planet Innovation Faculty Award. Her research is currently supported by the National Science Foundation.