| Popis: |
The simultaneous consideration of appointment day (inter-day scheduling) and time of day (intra-day scheduling) in dynamic scheduling decisions is an important theoretical and practical problem that has remained open due to its stochastic nature, complex structure, and large dimensionality. This article provides the first analytical model and associated theoretical results to address this joint problem within a tractable optimization framework. We build upon two recent studies: one from dynamic inter-day scheduling (Truong 2015), and one from static intra-day scheduling (Zacharias and Yunes 2020). We prove connections between these two studies based on new theoretical results in discrete convex analysis regarding constrained multimodular function minimization. We leverage these novel results and dynamic programming tools to characterize an optimal policy. We derive theoretical upper and lower bounds for the joint problem, based on which we develop a heuristic solution with a theoretically guaranteed optimality gap. Numerical experiments indicate that the optimality gap is less than 1% for practical instances of the problem. |
