Distributed Scheduling Mechanisms

分布式调度机制

• 批准号: 0621416
• 负责人: Bruce Hajek
• 金额: $ 24万
• 依托单位: University of Illinois at Urbana-Champaign
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2006
• 资助国家: 美国
• 起止时间: 2006-09-01 至 2010-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0621416&HistoricalAwards=false
• 关键词: Distributed; Scheduling; Mechanisms

0621416 - HajekDistributed Scheduling MechanismsThe main goal of the project is to explore the design and analysis of distributed market based scheduling algorithms, which enable agents to reserve resources online. Methods for gaining computational feasibility in the face of the difficult combinatorial problems will be investigated, including: (1) trading off optimality in a controlled way, while retaining important properties, (2) focusing on average case, or worst case, performance, and (3) leveraging the fact that future uncertainty often makes online algorithms simpler than their offline counterparts. An intriguing sideline of the study is to identify mechanisms under which distributed intelligent agents can make online choices as effectively as a centralized algorithm. Intellectual Merit: The project will bring together tools from disparate areas of recent research, including those from the theory of auctions and mechanism design from microeconomics, competitive analysis of online algorithms, deterministic and stochastic optimization methods, and both local and global stability analysis. Broader Impact: The work could have broad applications in many social and economic settings. For example, the methods could potentially be used for such diverse applications as the assignment of tasks to individuals in a large organization, or assignment of search and rescue resources to emergency response teams in a disaster recovery mission. Engineering applications would include the reservation of transmission bandwidth in wireless networks.

[06:21416] hajek分布式调度机制该项目的主要目标是探索基于分布式市场的调度算法的设计和分析，使代理能够在线预留资源。将研究在面对困难的组合问题时获得计算可行性的方法，包括：(1)在保留重要属性的同时，以受控的方式权衡最优性，(2)关注平均情况或最坏情况的性能，以及(3)利用未来不确定性通常使在线算法比离线算法更简单的事实。这项研究的一个有趣的副题是确定分布式智能代理可以像集中式算法一样有效地做出在线选择的机制。智力优势：该项目将汇集来自不同领域的最新研究工具，包括拍卖理论和微观经济学的机制设计，在线算法的竞争分析，确定性和随机优化方法，以及局部和全局稳定性分析。更广泛的影响：这项工作可能在许多社会和经济环境中有广泛的应用。例如，这些方法可能用于各种不同的应用，如将任务分配给大型组织中的个人，或将搜索和救援资源分配给灾难恢复任务中的应急响应小组。工程应用将包括无线网络中传输带宽的保留。