Nonsequential Appointment Scheduling With a Random Number of Requests

• 成果类型: Article
• 署名作者: Zhu, Yan; Liu, Zhixin; Qi, Xiangtong
• 署名单位: Chinese Academy of Sciences; University of Science & Technology of China, CAS; University of Michigan System; University of Michigan Dearborn; Hong Kong University of Science & Technology
• 刊物名称: PRODUCTION AND OPERATIONS MANAGEMENT
• ISSN/ISSBN: 1059-1478
• DOI: 10.1177/10591478231224926
• 发表日期: 2024
• 页码: 184-204
• 关键词: Appointment Scheduling; dynamic; nonsequential; branch and bound; shortest path

摘要

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.