The Appointment Scheduling Problem (ASP) involves scheduling a finite number of customers with uncertain service times, served consecutively by a single server, aiming to minimize the weighted costs of waiting time, idle time, and overtime. Previous studies using stochastic programming were limited to small instances. We introduce a Robust Optimization (RO) approach that considers service times within a specified uncertainty set and aims to minimize the worst-case costs, which requires maximizing a convex function. Combining advanced methods from Robust Convex Optimization, such as the Reformulation-Perspectification Technique (RPT) and the cutting-set approach, leads to an exact solution procedure for determining optimal schedules. Our robust framework for ASP is designed to manage large instances and accommodates general convex uncertainty sets. Based on extensive numerical experiments for polyhedral and ellipsoidal uncertainty sets, and problem instances with over 50 customers, we reveal intricate interactions between the uncertainty of service times, the cost function, and the structural characteristics of optimal schedules.
Article
View Robust Appointment Scheduling for General Convex Uncertainty Sets