论文标题
可重复使用资源的在线资源分配
Online Resource Allocation for Reusable Resources
论文作者
论文摘要
我们研究了模型不确定性下可重复使用的资源分配的一般模型。依次依次到达决策者（DM的）平台。在观察客户的类型后，DM选择了分配决策，这会带来奖励和资源所占据的资源。每个资源单元都被占据随机持续时间，并且在使用持续时间后，该单元可用于另一个分配。我们的模型捕获了许多涉及录取控制和分类计划的申请。 DM的目标是同时最大程度地提高多种类型的奖励，同时满足资源约束并不确定客户的到达过程。我们开发了一种近乎最佳的算法，该算法可实现最佳预期奖励的$（1-ε）$分数，其中误差参数$ε$随着资源容量单位和地平线的增长而衰减为零。该算法迭代以一种新颖的方式应用了乘法重量更新算法，该算法可以平衡所获得的奖励，资源和使用持续时间之间的权衡。
We study a general model on reusable resource allocation under model uncertainty. A heterogeneous population of customers arrive at the decision maker's (DM's) platform sequentially. Upon observing a customer's type, the DM selects an allocation decision, which leads to rewards earned and resources occupied. Each resource unit is occupied for a random duration, and the unit is available for another allocation after the usage duration. Our model captures numerous applications involving admission control and assortment planning. The DM aims to simultaneously maximize multiple types of rewards, while satisfying the resource constraints and being uncertain about the customers' arrival process. We develop a near-optimal algorithm that achieves $(1-ε)$ fraction of the optimal expected rewards, where the error parameter $ε$ decays to zero as the resource capacity units and the length of the horizon grow. The algorithm iteratively applies the Multiplicative Weight Update algorithm in a novel manner, which balances the trade-off among the amounts of rewards earned, resources occupied and usage durations.
