Nonsequential Appointment Scheduling With a Random Number of Requests

This article studies an appointment scheduling problem where a service provider dynamically receives appointment requests from a random number of customers. By leveraging the randomness of the number of potential customers, we develop a nonsequential appointment scheduling policy as an alternative to the conventional first-come-first-served (FCFS) policy. This allows for more flexibility in managing appointment scheduling. To calculate the optimal policy, we develop a branch-and-bound algorithm in which the lower bound is estimated using multiple approaches, such as optimality conditions, dynamic programming for calculating FCFS policy, and the shortest path reformulation. Through numerical studies, we observe that nonsequential appointment scheduling is particularly advantageous in systems characterized by highly fluctuating customer numbers or low congestion. In such cases, leaving gaps between appointments for potential future arrivals proves to be a more appropriate strategy. We also evaluate the performance of heuristics proposed in prior literature and provide insights into situations where these heuristics can be effectively applied.