文件名称：重新审视随机背包：服务水平视角-研究论文
文件大小：745KB
文件格式：PDF
更新时间：2024-06-30 03:08:22
Stochastic Knapsack; Resource Allocation;
资源分配问题中的一个关键挑战是找到接近最优的策略，使用固定的容量池（正确配置）为具有随机需求/收入的不同客户提供服务。 在本文中，我们研究了三类分配策略的特性——响应性（具有完美的事后观察）、自适应性（具有信息更新）和预期性（具有预测信息）策略。 这些政策的不同之处在于，每个客户的实际需求和收入信息如何被揭示和整合到分配决策中。 我们表明，可以通过“持久性”（或服务水平）值的概念来统一对这些策略的分析，即在最佳响应策略中（完全）为客户提供服务的概率。 我们针对容量最小化（具有给定的持久性目标）和收入最大化（具有给定的容量）模型分析和比较了这些策略的性能。 在这两个模型中，当每个项目的需求和收入独立产生时，最优预期策略和自适应策略之间的性能差距显示为有界。 相比之下，最优适应政策和响应政策之间的差距可以任意大。 更重要的是，我们表明所开发的技术以及从最佳响应策略中获得的持久性值可用于为资源分配问题的其他两种变体设计良好的自适应和预期策略。 这为设计和分析这些问题的算法提供了统一的方法。