Integer Programming Approaches for Appointment Scheduling with Random No-shows and Service Durations

We consider a single-server scheduling problem given a fixed sequence of appointment arrivals with random no-shows and service durations. The probability distribution of the uncertain parameters is assumed to be ambiguous and only the support and first moments are known. We formulate a class of distributionally robust (DR) optimization models that incorporate the worst-case expectation/conditional Value-at-Risk (CVaR) penalty cost of appointment waiting, server idleness, and overtime as the objective or constraints. Our models flexibly adapt to different prior beliefs of no-show uncertainty. We obtain exact mixed-integer nonlinear programming reformulations, and derive valid inequalities to strengthen the reformulations that are solved by decomposition algorithms. In particular, we derive convex hulls for special cases of no-show beliefs, yielding polynomial-sized linear programming models for the least and the most conservative supports of no shows. We test various instances to demonstrate the computational efficacy of our approaches, the results and solution performance of various DR models given perfect or ambiguous distributional information.

Article

Download

View PDF