Dynamic Interday and Intraday Scheduling

• 成果类型: Article
• 署名作者: Zacharias, Christos; Liu, Nan; Begen, Mehmet A.
• 署名单位: University of Miami; Boston College; Western University (University of Western Ontario)
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2022.2342
• 发表日期: 2024
• 关键词: finite-state approximations; markov decision-processes; health-care; no-shows; service; Multimodularity; APPOINTMENTS; allocation; ARRIVALS

摘要

The simultaneous consideration of appointment day (interday scheduling) and time of day (intraday scheduling) in dynamic scheduling decisions is a theoretical and practical problem that has remained open. We introduce a novel dynamic programming framework that incorporates jointly these scheduling decisions in two timescales. Our model is designed with the intention of bridging the two streams of literature on interday and intraday scheduling and to leverage their latest theoretical developments in tackling the joint problem. We establish theoretical connections between two recent studies by proving novel theoretical results in discrete convex analysis regarding constrained multimodular function minimization. Grounded on our theory, we develop a practically implementable and computationally tractable scheduling paradigm with performance guarantees. Numerical experiments demonstrate that the optimality gap is less than 1% for practical instances of the problem.