权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Bandits and beyond: Index heuristics for dynamic resource allocation

Bandits 及其他：动态资源分配的索引启发法

基本信息

批准号：
EP/E049265/1
负责人：
Kevin Glazebrook
金额：
$ 32.78万
依托单位：
Lancaster University
依托单位国家：
英国
项目类别：
Research Grant
财政年份：
2007
资助国家：
英国
起止时间：
2007 至无数据
项目状态：
已结题

来源：
https://gtr.ukri.org/projects?ref=EP%2FE049265%2F1
关键词：
Bandits beyond Index heuristics dynamic

项目摘要

The research programme is concerned with the development of simple, yet effective methods for determining how some key resource should be distributed over time among a collection of entities which require it. To fix some ideas, consider the example described in the following imagined scenario, referred to in the literature as the 'stochastic multiproduct batch dispatch problem' :Different types of products arrive at a holding station according to some random process. They are kept there until dispatched onward (to a retailer, say) by one of a fleet of vehicles. Costs are incurred by the items kept in storage at the station. The nature of these holding costs may differ markedly between product types. Products may also differ with regard to their space requirements for transportation. At the beginning of each time period (the start of each day, say), a decision has to be made regarding how many vehicles should be dispatched and what the composition of their loads should be. Such decisions may be based in part, say, on the number of units of each product type at the station at the time. The goal is to take such decisions in a way that minimises the overall costs incurred in holding the products and in dispatching the vehicles. To use some mathematical jargon, the decision-maker is looking for a dynamic policy for the allocation of her key resource (ie, a rule for the deployment of the fleet of vehicles) among a set of entities (here the product types) in a situation which is both stochastic (evolves randomly) and complex. How to develop such a policy is extremely difficult, not least because decisions must be assessed not only in terms of their immediate impact on costs but also with regard to their influence on the costs which will be incurred in the future. The conventional approach to such problems, called stochastic dynamic programming, is unlikely to be able to cope well with problems of realistic size . What would be invaluable to the decision-maker would be some effective, yet reasonably simple and computationally tractable, way of calibrating the value to the respective product types of (differing amounts of) space on the vehicles. Such calibrations could then be used to inform decision-making. Simple so-called index-based solutions do indeed exist (and are very effective), but mainly for (bandit-type) problems which impose serious limitations on how the key resource may be distributed among the entities. The goal of the research project is to extend the scope of such simple index-based solution approaches to more general allocation problems which are freed of such restrictions . There is a rich variety of practical situations which share the broad features of the above example. The methodologies developed during the research programme will yield simple and effective index-based approaches to resource allocation in many such settings.

研究方案涉及发展简单而有效的方法，以确定某些关键资源应如何随时间在需要它的一组实体之间分配。为了修正一些想法，考虑以下想象场景中描述的例子，在文献中称为“随机多产品批量调度问题”：不同类型的产品根据一些随机过程到达一个持有站。它们被保存在那里，直到被车队中的一辆送去（比如送到零售商那里）。费用是由储存在车站的物品引起的。这些持有成本的性质可能因产品类型而有显著差异。产品的运输空间要求也可能有所不同。在每个时间段的开始（例如，每天的开始），必须决定应该派遣多少车辆以及它们的负载应该是什么组成。这样的决定可能部分地基于，比如说，当时车站上每种产品类型的单位数量。我们的目标是做出这样的决定，使持有产品和调度车辆所产生的总成本降到最低。用一些数学术语来说，决策者正在寻找一种动态策略，用于在一组实体（这里是产品类型）中分配她的关键资源（即车队部署的规则），这种情况既随机（随机发展）又复杂。如何制定这样一项政策是极其困难的，尤其是因为必须不仅根据其对费用的直接影响，而且根据其对将来将产生的费用的影响来评估各项决定。处理这类问题的传统方法，称为随机动态规划，不太可能很好地处理实际规模的问题。对决策者来说，最有价值的是一些有效的、但相当简单的、计算上容易处理的方法，来校准车辆上不同产品类型（不同数量）空间的价值。这样的校准可以用来为决策提供信息。简单的所谓基于索引的解决方案确实存在（并且非常有效），但主要是针对（强盗类型的）问题，这些问题对如何在实体之间分配密钥资源施加了严重的限制。该研究项目的目标是将这种简单的基于索引的解决方法的范围扩展到不受此类限制的更一般的分配问题。有各种各样的实际情况都具有上述例子的广泛特征。在研究方案期间制定的方法将在许多这种情况下产生简单有效的基于指数的资源分配办法。