The Stochastic Sequential Assignment Problem With Random Deadlines
The Stochastic Sequential Assignment Problem With Random Deadlines
复制标题
具有随机期限的随机顺序分配问题
DOI：
10.1017/s0269964800000395
复制
发表时间：
1987
影响因子：
1.1
通讯作者：
Rhonda Righter
中科院分区：
文献类型：
--
作者：
Rhonda Righter
资源将按顺序分配给活动，以最大化总预期回报，其中分配的回报是资源价值和活动价值的乘积。活动集及其值是提前给出的，但资源根据泊松过程到达，并且它们的值是在到达时观察到的独立随机变量。假设所有活动都有一个随机截止日期（与贴现回报相同），或者活动具有独立的随机截止日期。该模型具有机器调度、数据包交换和移植肾分配等应用。众所周知，折扣情况下的最优策略具有非常简单的形式，不依赖于活动值。我们证明，当截止日期独立时也是如此，在这种情况下，解决方案可以用单一活动模型的解决方案来表示。当资源批量到达时，这些结果也成立。对于这两个模型，研究了将具有单一活动的单独的相同系统汇集到组合系统中的效果。当活动具有独立的最后期限时，当且仅当在单个活动系统中拒绝资源是最佳时，拒绝组合系统中的资源才是最佳的。然而，当回报打折时，有时最好在组合系统中接受在单一活动系统中会被拒绝的资源。
Resources are to be allocated sequentially to activities to maximize the total expected return, where the return from an allocation is the product of the value of the resource and the value of the activity. The set of activities and their values are given ahead of time, but the resources arrive according to a Poisson process and their values are independent random variables that are observed upon arrival. It is assumed that either there is a single random deadline for all activities, which is the same as discounting the returns, or the activities have independent random deadlines. The model has applications machine scheduling, packet switching, and kidney allocation for transplant. It is known that the optimal policy in the discounted case has a very simple form that does not depend on the activity values. We show that this is also true when the deadlines are independent and in this case the solution can expressed in terms of solutions to single activity models. These results also hold when there are batch arrivals of resources. The effects of pooling separate identical systems with a single activity into a combined system is investigated for both models. When activities have independent deadlines it is optimal to reject a resource in the combined system if and only if it is optimal to reject it in the single activity system. However, when returns are discounted, it is sometimes optimal to accept a resource in the combined system that would be rejected in the single activity system.