Models and algorithms for operation of selected decentralized and centralized systems

用于选定分散式和集中式系统操作的模型和算法

• 批准号: 105675-2012
• 负责人: Kubiak, Wieslaw
• 金额: $ 1.53万
• 依托单位: Memorial University of Newfoundland
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2012
• 资助国家: 加拿大
• 起止时间: 2012-01-01 至 2013-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=509016
• 关键词: Models; algorithms; operation; selected; decentralized

Traditional models of operations research (OR) have focused on optimization under a tacit assumption of centralized decision making. This assumption is now being challenged as today's complex systems require decisions being made in a decentralized manner. This, however, may lead to suboptimal solutions. To remove this inefficiency supply chains may resort to transshipment so that independent agents have incentives to select their order levels so that optimal solution is attained after all. This cooperation, however, incurs cooperation costs that have been always assumed away in OR. This research is to study the cooperation costs that agents can afford to gain the efficiency (Symmetric Transshipment Games With Cooperation Costs). Similarly, in wireless networks with primary interference constraints links must not share the same node when transmitting simultaneously. Thus matchings need to be determined to keep up with link queues growth. The maximum weight matchings result in maximum throughput, however, they require centralized computing. The decentralized greedy maximal weight matching however can only ensure 100% throughput on a special class of graphs. We study the stability and shortest sequences of matchings for this class in our research (Stability And Scheduling In Wireless Networks). The graph decomposition technique is a cutting edge technique for dealing with NP-hard problems by recognizing and efficiently solving large classes of problem instances. While a traditional focus of decomposition techniques is on finding a decomposition of a given width, in our research, we change this focus to finding the shortest path decompositions of a given width. These have important applications in scheduling and the partner unit problem (Shortest Path Decomposition). The ideal schedules maximize two most important objectives in scheduling: the makespan and the mean flow time. The scheduling problems for which the ideal schedules exist for any instance are called ideal. This research identifies some ideal scheduling problem, among them some of the most celebrated problems in the theory of scheduling, and show how to design more efficient optimization algorithms for these ideal problems (Ideal Schedules).

传统的运筹学（OR）模型都集中在集中决策的默认假设下的优化。这一假设现在正受到挑战，因为今天的复杂系统需要以分散的方式做出决策。然而，这可能导致次优的解决方案。为了消除这种低效率的供应链可能会采取转运，使独立的代理人有动机选择他们的订单水平，使最优的解决方案，毕竟是达到。然而，这种合作会产生合作成本，而这些成本总是在OR中假设的。本研究旨在探讨代理人为获得效率所能负担的合作成本（有合作成本的对称转运对策）。类似地，在具有主要干扰约束的无线网络中，当同时发送时，链路必须不共享相同的节点。因此，需要确定匹配以跟上链路队列的增长。最大权重匹配导致最大吞吐量，然而，它们需要集中计算。然而，分散的贪婪最大权重匹配只能确保100%的吞吐量在一类特殊的图。我们研究的稳定性和最短序列的匹配，这类在我们的研究（稳定性和调度在无线网络）。图分解技术是通过识别和有效地解决大类问题实例来处理NP难问题的前沿技术。虽然传统的分解技术的重点是找到一个给定宽度的分解，在我们的研究中，我们改变了这个重点，找到一个给定宽度的最短路径分解。这些在调度和伙伴单元问题（最短路径分解）中有重要的应用。理想的调度计划最大化两个最重要的目标：最大完工时间和平均流时间。对于任何实例都存在理想调度的调度问题称为理想调度。本研究确定了一些理想的调度问题，其中一些最著名的问题在调度理论，并显示如何设计更有效的优化算法，这些理想的问题（理想的时间表）。