Asymptotically optimal appointment schedules with customer no-shows
Asymptotically optimal appointment schedules with customer no-shows
复制标题
客户缺席情况下的渐进最优预约安排
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Harsha Honnappa
中科院分区：
文献类型：
--
作者：
Mor Armony;R. Atar;Harsha Honnappa
我们考虑有限的客户人口的预约安排与客户不显示服务设施的问题，以最小化客户等待时间和服务器超时成本的总和。由于预约需要提前安排，我们把这个问题作为一个优化问题，而不是一个动态控制。我们研究这个优化问题的流体和扩散尺度，并确定在这两个尺度的渐近最优调度。在流体规模，我们表明，这是最佳的安排约会，使系统处于临界负载，因此，交通繁忙的条件下获得的优化结果，而不是作为一个假设。在扩散尺度下，我们在大的时域极限下解决了这个优化问题。我们的显式固定的解决方案，相应的布朗优化问题的客户延迟与服务器超时的权衡之间的权衡反射布朗运动的状态在半行和其本地时间为零。出于对竞争比的研究，我们还考虑了一个参考模型，其中预言机为决策者提供了完全的随机信息。两个模型的调度问题的值之间的差异，我们称之为随机性间隙（SG），量化了在不确定性下设计调度比随机原语（即，未出现和服务时间）是预先已知的。在流体尺度中，SG收敛到零，但在扩散尺度中，它收敛到我们计算的正常数。
We consider the problem of scheduling appointments for a finite customer population to a service facility with customer no-shows, to minimize the sum of customer waiting time and server overtime costs. Since appointments need to be scheduled ahead of time we refer to this problem as an optimization problem rather than a dynamic control one. We study this optimization problem in fluid and diffusion scales and identify asymptotically optimal schedules in both scales. In fluid scale, we show that it is optimal to schedule appointments so that the system is in critical load; thus heavy-traffic conditions are obtained as a result of optimization rather than as an assumption. In diffusion scale, we solve this optimization problem in the large horizon limit. Our explicit stationary solution of the corresponding Brownian Optimization Problem translates the customer-delay versus server-overtime tradeoff to a tradeoff between the state of a reflected Brownian motion in the half-line and its local time at zero. Motivated by work on competitive ratios, we also consider a reference model in which an oracle provides the decision maker with the complete randomness information. The difference between the values of the scheduling problem for the two models, to which we refer as the stochasticity gap (SG), quantifies the degree to which it is harder to design a schedule under uncertainty than when the stochastic primitives (i.e., the no-shows and service times) are known in advance. In the fluid scale, the SG converges to zero, but in the diffusion scale it converges to a positive constant that we compute.
DOI：
10.1287/ijoc.2017.0773
发表时间：
2018-02
期刊：
INFORMS J. Comput.
影响因子：
--
作者：
Song-Hee Kim;W. Whitt;W. Cha
通讯作者：
Song-Hee Kim;W. Whitt;W. Cha