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
• 财政年份: 2015
• 资助国家: 加拿大
• 起止时间: 2015-01-01 至 2016-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=569099
• 关键词: 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中一直被承担。本文研究的是代理为获得效率所能承担的合作成本（带合作成本的对称转运博弈）。同样，在具有主要干扰约束的无线网络中，链路在同时传输时不能共享同一节点。因此，需要确定匹配以跟上链接队列的增长。最大的权重匹配导致最大的吞吐量，但是，它们需要集中计算。然而，去中心化贪心最大权匹配算法只能在一类特殊的图上保证100%的吞吐量。在我们的研究（无线网络中的稳定性和调度）中，我们研究了该类的稳定性和最短匹配序列。图分解技术是一种通过识别和有效地解决大类问题实例来处理np困难问题的前沿技术。传统的分解技术的重点是寻找给定宽度的分解，而在我们的研究中，我们将这个重点改变为寻找给定宽度的最短路径分解。这些在调度和伙伴单元问题（最短路径分解）中有重要的应用。理想的调度最大化了调度中两个最重要的目标：完工时间和平均流程时间。对任何实例都存在理想调度的调度问题称为理想调度问题。本文确定了一些理想调度问题，其中包括调度理论中最著名的一些问题，并展示了如何为这些理想问题设计更有效的优化算法（理想调度）。