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 (mini–max) 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 a 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.