Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

Memorial University of Newfoundland

$21,000.00

Models and algorithms for operation of selected decentralized and centralized systems

EF 2014-15

Résumé
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).
Programme
Discovery Grants Program - Individual
Emplacement
Newfoundland and Labrador, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
105675-2012
Name nom
Kubiak, Wieslaw
Department département
Business Administration, Faculty of
Organization id
89
Institution établissement
Memorial University of Newfoundland
Province en
Newfoundland and Labrador
Province fr
Terre-Neuve-et-Labrador
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2014
Competition year année de concours
2012
Award amount
21000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
1509
Committee name en
Civil, Industrial and Systems Engineering
Committee name fr
Génie civil, industriel et des systèmes
Area of application code
520
Area of application group en
Manufacturing processes and products
Area of application group fr
Procédés et produits industriels
Area of application en
Production and operations management
Area of application fr
Production et gestion des opérations
Research subject code
1601
Research subject group en
Industrial engineering
Research subject group fr
Génie industriel
Research subject en
Operations research and management science
Research subject fr
Recherche opérationnelle et science de la gestion
Partie
3
Nb partie
5
Application title
Models and algorithms for operation of selected decentralized and centralized systems
Keyword
NSERC
Application summary
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).