Multimodularity in the Stochastic Appointment Scheduling Problem with Discrete Arrival Epochs
研究了考虑患者爽约、不准时、随机服务时间和急诊插队情况下的门诊预约调度问题，通过离散时间排队模型分析系统工作量，证明了目标函数的超模性和分量凸性，并首次提出一种多项式时间算法来最小化多模函数。
We address the problem of designing appointment scheduling strategies in a stochastic environment accounting for patient no-shows, nonpunctuality, general stochastic service times, and unscheduled emergency walk-ins. A good appointment schedule seeks to help outpatient clinics to utilize their resources efficiently while containing patients’ waiting times. The task of identifying an optimal schedule is modeled as a nonlinear integer program, where the objective function is the outcome of stochastic analysis in transient state. We maintain the discrete nature of the appointment scheduling problem by considering arrival epochs with discrete supports. By looking at discrete-time snapshots of the random evolution of a single-server queueing model, we characterize probabilistically the system’s workload over time as a function of an appointment schedule, and we derive recursive expressions for the performance measures of interest. Subsequently, we unfold discrete convexity properties of the optimization problem. We prove that under general conditions the objective function is supermodular and componentwise convex. Under assumptions on patient punctuality, we prove that the optimal scheduling strategy minimizes a multimodular function, a property which guarantees that a locally optimal schedule is also globally optimal. The size of the local neighborhood, however, grows exponentially with the dimension of the problem. To the best of our knowledge, this study is the first to develop and implement an algorithm for minimizing locally a multimodular function over nonnegative integer vectors via submodular set-function minimization over ring families, a task that can be performed in polynomial time. This paper was accepted by David Simchi-Levi, operations management.