期刊
MANAGEMENT SCIENCE
卷 66, 期 2, 页码 744-763出版社
INFORMS
DOI: 10.1287/mnsc.2018.3242
关键词
transient queues; discrete optimization; multimodularity; appointment scheduling
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据