文件名称：部分可预测需求下的在线资源分配-研究论文
文件大小：701KB
文件格式：PDF
更新时间：2024-06-29 19:46:08
online resource allocation
对于在线资源分配问题，我们提出了一种新的需求到达模型，其中到达序列包含对抗性分量和随机性分量。 我们的模型不需要需求预测； 然而，由于随机成分的存在，我们可以随着到达顺序的展开部分预测未来的需求。 在所提出的模型下，我们研究了将单一资源在线分配给两类客户的问题，并设计了优于现有算法的在线算法。 我们的算法可以根据随机分量的相对大小进行调整，我们的分析表明，随着随机分量部分的增加，在线决策造成的损失会减少。 这突出了（甚至部分）可预测性在在线资源分配中的价值。 我们没有对资源容量如何随着最大客户数量进行扩展施加任何条件。 但是，我们表明，当容量与客户数量呈线性增长时，使用自适应算法（根据观察到的数据做出在线决策）特别有益。 我们的工作是弥合基于 (1) 对抗模型和 (2) 随机模型设计和分析在线算法的两种经过充分研究的方法之间长期存在的差距的第一步。 使用新颖的算法设计，我们证明即使到达序列包含对抗性组件，我们也可以利用数据显示的有限信息来改进分配决策。 我们还研究了我们提出的到达模型下的经典秘书问题，我们表明随机化多个停止规则可能会增加成功的概率。