Advance Service Reservations with Heterogeneous Customers
Advance Service Reservations with Heterogeneous Customers
复制标题
DOI：
10.1287/mnsc.2019.3364
复制
发表时间：
2018-05
期刊：
影响因子：
--
通讯作者：
C. Stein;Van-Anh Truong;Xinshang Wang
中科院分区：
文献类型：
--
作者：
C. Stein;Van-Anh Truong;Xinshang Wang
我们研究了资源分配的基本模型，其中必须以在线方式将有限数量的资源分配给异构客户流。根据已知的随机过程，客户随时间随机到达。每个客户都需要特定数量的容量，并且对每种资源都有特定的偏好，其中一些资源对于客户来说是可行的，而另一些资源则不可行。系统必须找到每个客户对资源的可行分配，否则必须拒绝该客户。目的是最大限度地提高未来资源的预期总产能利用率。该模型可应用于服务、货运和在线广告。我们提出了相对于知道所有随机信息的最佳离线算法具有有限竞争比的在线算法。与常见的启发式算法相比，我们的算法表现得非常好，纽约市一家大型医院系统的真实数据集证明了这一点。该论文被叶银宇接收，优化。
We study a fundamental model of resource allocation in which a finite number of resources must be assigned in an online manner to a heterogeneous stream of customers. The customers arrive randomly over time according to known stochastic processes. Each customer requires a specific amount of capacity and has a specific preference for each of the resources with some resources being feasible for the customer and some not. The system must find a feasible assignment of each customer to a resource or must reject the customer. The aim is to maximize the total expected capacity utilization of the resources over the horizon. This model has application in services, freight transportation, and online advertising. We present online algorithms with bounded competitive ratios relative to an optimal off-line algorithm that knows all stochastic information. Our algorithms perform extremely well compared with common heuristics as demonstrated on a real data set from a large hospital system in New York City. This paper was accepted by Yinyu Ye, optimization.