Distributionally robust appointment scheduling that can deal with independent service times

Consider a single server that should serve a given number of customers during a fixed period. The Appointment Scheduling Problem (ASP) determines the schedule of planned appointments that minimizes some cost function that accounts for both the cost of idle times and the cost of waiting. When service time distributions are fully specified, the ASP presents a much investigated computationally challenging stochastic program. When service time distributions are only partially specified, one can apply distributionally robust optimization (DRO) to find the schedule that minimizes costs in worst-case circumstances. We assume that only the mean, mean absolute deviation and range of the service times are known, and develop a DRO method that finds the optimal (minimax) schedule. For independent service times, the min-max problem becomes nonlinear and difficult, if not impossible, to solve exactly. Existing DRO methods for ASP with partial information (such as mean and variance) therefore consider relaxations that allow correlations between service times. Such relaxations have major repercussions, as the worst-case scenario will then be highly correlated. Our method thus deals with independent service times and finds the robust schedule as the solution to a linear program. We identify several new structural features of optimal robust schedules. We also apply the method to model extensions including sequencing and alternative objective functions.