Models and algorithms for operation of selected decentralized and centralized systems

传统的运筹学模型侧重于在集中决策的默许假设下进行优化。这一假设现在正受到挑战，因为今天的复杂系统要求以分散的方式作出决定。然而，这可能会导致次优解决方案。为了消除这种低效率，供应链可以求助于转运，这样独立代理就有动力选择他们的订货水平，从而最终获得最优解决方案。然而，这种合作产生了合作成本，这些成本一直被认为是在OR中扣除的。本研究旨在研究代理人为获得效率所能负担的合作成本(对称转运博弈与合作成本)。类似地，在具有主要干扰约束的无线网络中，链路在同时传输时不能共享同一节点。因此，需要确定匹配以跟上链路队列的增长。最大权重匹配会产生最大吞吐量，但它们需要集中计算。然而，在一类特殊的图上，分散的贪婪最大权匹配算法只能保证100%的吞吐量。在我们的研究(无线网络中的稳定性和调度)中，我们研究了这类匹配的稳定性和最短序列。图分解技术是一种通过识别和有效地解决大类问题实例来处理NP-Hard问题的前沿技术。虽然传统的分解技术的重点是寻找给定宽度的分解，但在我们的研究中，我们将这一重点改变为寻找给定宽度的最短路径分解。它们在调度和伙伴单元问题(最短路径分解)中有重要的应用。理想的调度最大限度地实现了调度中的两个最重要的目标：完工时间和平均流水时间。对任何实例都存在理想调度的调度问题称为理想调度问题。本研究找出了一些理想的调度问题，其中包括一些调度理论中最著名的问题，并展示了如何为这些理想问题(理想调度)设计更有效的优化算法。

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).