The Appointment Scheduling Problem (ASP) involves scheduling a finite number of customers with uncertain service times, served consecutively by a single server, with the goal of minimizing the weighted costs of waiting time, idle time, and overtime. Previous studies employing stochastic programming were limited to small instances or constrained by restrictive assumptions. We introduce a novel Robust Optimization (RO) approach that considers service times within a specified uncertainty set and minimizes the worst-case costs, necessitating the minimization of a convex function. By integrating advanced methods from Robust Convex Optimization, such as the Reformulation-Perspectification Technique (RPT) and a cutting-set approach, we are the first to establish an exact solution procedure for determining optimal schedules. Our robust framework for ASP is designed to handle large instances and accommodates general convex uncertainty sets. Based on extensive numerical experiments with both polyhedral and ellipsoidal uncertainty sets, and synthetic problem instances involving up to 100 customers, we reveal intricate interactions between the uncertainty of service times, the cost function, and the structural characteristics of optimal schedules.
Article