Models and algorithms for operation of selected decentralized and centralized systems

点击翻译按钮获取中文摘要

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