Dissertations / Theses on the topic 'Resource allocations problems'

Resource allocation in control and communication systems constitutes the distribution of (finite) system resources in a way that achieves maximum system functionality and or cost effectiveness. Specific resource allocation problems in subband coding, Discrete Multi-tone modulation based systems and autonomous multi-agent control are addressed in this thesis. In subband coding, the number of bits used (out of a target bit budget) to code a sub- band signal are allocated in a way that minimizes the coding distortion. In Discrete Multi-tone modulation based systems, high bit rate streams are split into several parallel lower rate streams. These individual data streams are transmitted over different subchannels. Given a target bit rate, the goal of resource allocation is to distribute the bits among the different subchannels such that the total transmitted power is minimized. The last problem is achieving stable control of a fleet of autonomous agents by utilizing the available communication resources (such as transmitted Power and bandwidth) as effectively as possible. We present an efficient bit loading algorithm that applies to both subband coding and single-user multicarrier communication system. The goal is to effect an optimal distribution of B bits among N subchannels (subbands) to achieve a minimum transmitted power (distortion error variance) for multicarrier (subband coding) systems. All the algorithms in literature, except a few (which provides a suboptimal solution), have run times that increase with B. By contrast, we provide an algorithm that solves the aforementioned problems exactly and with a complexity (given by O(N log(N)),) which is dependent only on N. Bit loading in multi-user multicarrier systems not only involves the distribution of bit rates across the subchannels but also the assignment of these subchannels to different users. The motivation for studying suboptimal bit allocation is underscored by implicit and explicit claims made in some of the papers which present suboptimal bit loading algorithms, without a formal proof, that the underlying problem is NP-hard. Consequently, for no other reason than the sake of completeness, we present a proof for NP-hardness of the multiuser multicarrier bit loading problem, thereby formally justifying the search for suboptimal solutions. There has been a growing interest in the area of cooperative control of networks of mobile autonomous agents. Applications for such a set up include organization of large sensor networks, air traffic control, achieving and maintaining formations of unmanned vehicles operating under- water, air traffic control etc. As in Abel et al, our goal is to devise control laws that, require minimal information exchange between the agents and minimal knowledge on the part of each agent of the overall formation objective, are fault tolerant, scalable, and easily reconfigurable in the face of the loss or arrival of an agent, and the loss of a communication link. A major drawback of the control law proposed in Abel et al is that it assumes all agents can exchange information at will. This is fine if agents acquire each others state information through straightforward sensing. If however, state information is exchanged through broadcast commu- nication, this assumption is highly unrealistic. By modifying the control law presented in Abel et al, we devise a scheme that allows for a sharing of the resource, which is the communication channel, but also achieves the desired formation stably. Accordingly we modify the control law presented in [23] to be compatible with networks constrained by MAC protocols.

Cette thèse s’intéresse aux problèmes d’ordonnancement à une machine où les durées opératoires des tâches peuvent dépendre de différents paramètres. Dans les problèmes d’ordonnancement traditionnels, les durées opératoires sont souvent supposées constantes. Cette hypothèse n’est pas toujours valable dans certains problèmes réels d'ordonnancement en production ou en service. La durée opératoire d'une tâche peut en effet varier selon la quantité de ressources consommables allouées, la performance des opérateurs et l’état des ressources matérielles utilisées, etc. L’ordonnancement optimal peut donc être différent. Nous nous intéressons à quatre problèmes d’ordonnancement avec différentes configurations des facteurs suivants : changement de productivité par la maintenance, quantité de ressources consommables utilisées, effet d’apprentissage, technologie de groupe, temps de réglage et fenêtres horaires dues. Le changement de productivité par la maintenance, qui reflète l'état des machines, est un facteur clé de cette thèse. Il est présent dans tous les problèmes étudié, sauf pour le premier. Cette thèse considère globalement les nouvelles caractéristiques telles que les ressources consommables, les ressources humaines et les machines bien qu'elle soit organisée sous l'angle des ressources consommables et l'effet d'apprentissage. Pour chaque problème considéré, nous construisons d’abord un modèle mathématique. Après l’analyse du modèle construit, nous proposons un algorithme exact de résolution. Enfin la complexité de l’algorithme est étudiée<br>This thesis addresses scheduling problems with consumable resource allocation and learning effect. In traditional deterministic scheduling problems, job processing times are assumed to be constant. However, this assumption is not always appropriate in many real life production and service operations since practical issues, including limited consumable resources, human characteristics (learning effect), usually affect job processing times, which change the whole scheduling process and lead to new characteristics to decision-making and scheduling results. It is therefore necessary and reasonable to study scheduling problems with these features. Based on the above two issues, this thesis mainly concerns four scheduling problems including group technology, rate-modifying activity (RMA), past-sequence-dependent setup times, and due-windows. It is worth to note that RMA which reflects the situations of ma-chines is also a key factor considered. It is involved in all studied problems except the first one. This thesis is also a work considering comprehensively new characteristics of consumable resources, human, and machines although we just organize this thesis from the viewpoint of consumable resource allocation and learning effect. For each problem, we propose a scheduling model, design an exact algorithm, and analyze the complexity

In a data streaming system, each component consumes one or several streams of data on the fly and produces one or several streams of data for other components. The entire Internet can be viewed as a giant data streaming system. Other examples include real-time exploratory data mining and high performance transaction processing. In this thesis we study several measurement and resource allocation optimization problems of data streaming systems. Measuring quantities associated with one or several data streams is often challenging because the sheer volume of data makes it impractical to store the streams in memory or ship them across the network. A data streaming algorithm processes a long stream of data in one pass using a small working memory (called a sketch). Estimation queries can then be answered from one or more such sketches. An important task is to analyze the performance guarantee of such algorithms. In this thesis we describe a tail bound problem that often occurs and present a technique for solving it using majorization and convex ordering theories. We present two algorithms that utilize our technique. The first is to store a large array of counters in DRAM while achieving the update speed of SRAM. The second is to detect global icebergs across distributed data streams. Resource allocation decisions are important for the performance of a data streaming system. The processing graph of a data streaming system forms a fork and join network. The underlying data processing tasks consists of a rich set of semantics that include synchronous and asynchronous data fork and data join. The different types of semantics and processing requirements introduce complex interdependence between various data streams within the network. We study the distributed resource allocation problem in such systems with the goal of achieving the maximum total utility of output streams. For networks with only synchronous fork and join semantics, we present several decentralized iterative algorithms using primal and dual based optimization techniques. For general networks with both synchronous and asynchronous fork and join semantics, we present a novel modeling framework to formulate the resource allocation problem, and present a shadow-queue based decentralized iterative algorithm to solve the resource allocation problem. We show that all the algorithms guarantee optimality and demonstrate through simulation that they can adapt quickly to dynamically changing environments.

With the increasing effect of disasters and long term issues on human well-being and economy over the recent years, effective management of humanitarian supply chains has become more important. This thesis work focuses on three problems in humanitarian supply chains where uncertainty is inherent, namely (i) post-disaster debris clearance with uncertain debris amounts, (ii) allocation of a health/humanitarian commodity in a developing country setting with multiple demand types, and (iii) distribution of specialized nutritious foods by a large scale humanitarian organization. In each of the three parts, the problem is formally defined, and a novel optimal solution approach incorporating the inherent uncertainty in the environment and updates is proposed. In cases where optimal models cannot be solved within reasonable time, novel heuristics are developed. Through structural analysis and computational experiments based on real data, the proposed approaches are compared to those that ignore the uncertainty in the environment and/or updates of information as new data becomes available. Using computational experiments, the proposed approaches are compared to those that are applied in practice, and the aspects of the system where performance improvements are more significant are analyzed.

L’endiguement dynamique d’un processus de diffusion indésirable sur réseau, comme une épidémie, exige d’un décideur (DM) qu’il soit capable de répondre à son évolution en prenant les bonnes mesures de con- trôle au bon moment. Cette tâche peut être considérée comme la gestion de l’allocation d’une quantité limitée de ressources aux nœuds du réseau, avec pour objectif de réduire les effets du processus.Dans cette thèse, nous étendons le problème de l’allocation dynamique de ressources (DRA) et pro- posons un cadre de contrôle dynamique à itéra- tions/tours multiples, que nous réalisons grâce à deux modèles dérivés: le DRA restreint et le DRA séquen- tiel (RDRA, SDRA). Contrairement aux considérations standards dans lesquelles l’information et l’accès sont complets, ces nouveaux modèles prennent en compte les éventuelles restrictions d’accès concernant les informa- tions disponibles sur le réseau et/ou la capacité à agir sur ses nœuds. À chaque cycle d’intervention, le DM a un accès limité aux informations relatives à une fraction des nœuds, et obtient également l’accès pour agir sur eux de manière séquentielle.Ce dernier aspect séquentiel dans le processus de décision offre une perspective com- plètement nouvelle au contrôle du processus de diffusion dynamique, ce qui fait de ce travail le premier à présen- ter le problème du contrôle dynamique comme une série de processus de sélection séquentielleDans le cadre du problème de sélection séquentielle (SSP), des décisions immédiates et irrévocables doivent être prises par le décideur, tandis que les candidats ar- rivent dans un ordre aléatoire et sont examinés pour l’un des créneaux de sélection disponible. Pour les besoins du contrôle de la diffusion en réseau, ce que nous pro- posons se traduit par sélectionner les bons nœuds afin deleur allouer les ressources de contrôle dans un processus séquentiel à plusieurs itérations. Cependant, les vari- antes standard du SSP, comme le très connu problème de la secrétaire, commencent par un ensemble de sélec- tion vide (démarrage à froid) et effectuent le processus de sélection une fois sur un seul ensemble de candidats (unique itération). Ces deux limites sont abordées dans la présente thèse. Tout d’abord, nous introduisons un nouveau paramètre de démarrage à chaud qui considère avoir à portée de main un ensemble de référence, c’est-à- dire un ensemble d’éléments préalablement sélectionnés d’une qualité donnée. Le DM tente ensuite de mettre à jour de manière optimale cet ensemble tout en exam- inant la séquence de candidats qui arrivent, contraint par la possibilité de mettre à jour l’affectation à chaque créneau de sélection (ressource) au plus une fois. Le pro- cessus de sélection séquentielle aux multiples itérations, est alors introduit comme une extension naturelle de la sélection de démarrage à chaud.Des fonctions objectif basées sur le rang et le score de la sélection finale sont prises en compte. Une approche basée sur la séparation de la séquence en deux phases est proposée pour la première, tandis que la stratégie optimale basée sur le calcul d’un seuil d’acceptation dy- namique est dérivée pour la seconde en supposant que la distribution des scores est connue. Ces stratégies sont ensuite mises en comparaison pour leur efficacité dans le cadre de la sélection traditionnelle ainsi que pour la résolution des problèmes de contrôle sur réseaux qui ont motivé cette thèse. La généralité des modèles introduits permet leur application à une grande variété de domaines et de problèmes; par exemple, les processus de recrute- ment récurrents, la gestion de ressources (par exemple, lits, personnel) dans les unités de soins de santé, ainsi que la résolution de problèmes combinatoires difficiles sous contraintes, comme le problème de b-diversification que l’on trouve dans les applications de traitement de flux de données (entre autres, en robotique)<br>The dynamic containment of an undesired network diffusion process, such as an epidemic, requires a decision maker (DM) to be able to respond to its evo- lution by taking the right control actions at the right moments. This task can be seen as managing the alloca- tion of a limited amount of resources to the graph nodes, with the objective to reduce the effects of the process.In this thesis we extend the Dynamic Resource Alloca- tion (DRA) problem and propose a multi-round dynamic control framework, which we realize through two derived models: the Restricted and the Sequential DRA (RDRA, SDRA). Contrary to the standard full-information and full-access DRA considerations, these new models take into account possible access restrictions regarding the the available information about the network and/or the ability to act on its nodes. At each intervention round, the DM has limited access to information related to a fraction of the nodes, and is also gaining access to act on them in a sequential fashion. The latter sequential as- pect in the decision process offers a completely new per- spective to the dynamic diffusion process control, making this work the first to cast the dynamic control problem as a series of specially designed sequential selection pro- cesses.In the Sequential Selection Problem (SSP), immediate and irrevocable decisions need to be made by the DM as candidate items arrive randomly and get examined for one of the limited selection slots available. For the needs of network diffusion control, what we propose translatesinto selecting the right nodes to allocate the control re- sources in a multi-round sequential process. However, standard SSP variants, such as the very well-known sec- retary problem, begin with an empty selection set (cold- start) and perform the selection process once over a single candidate set (single-round). These two limita- tions are addressed in this thesis. First, we introduce the novel Warm-starting SSP setting that considers hav- ing at hand a reference set, which is a set of previously selected items of a given quality, and tries to update optimally that set while examining the sequence of ar- riving candidates, constrained by being able to update the assignment to each selection slot (resource) at most once. The Multi-round Sequential Selection Process, the new online-within-online problem, is then introduced as a natural extension of the warm-starting selection.Both rank-based and score-based ob jective functions over the final selection are considered. A cutoff-based approach is proposed for the former, while the optimal strategy based on dynamic thresholding is derived for the latter assuming that the score distribution is known. These strategies are then put in comparison for their efficiency in the traditional selection setting as well as in solving network control problems that motivated this thesis. The generality of the introduced models allow their application to a wide variety of fields and problems; for instance, reoccurring recruiting processes, manage- ment of resources (e.g. beds, staff) in healthcare units, as well as tackling difficult combinatorial problems under constrains, such as the b-diversification problem found in data-stream processing applications (e.g. in robotics)

The Stochastic Diffusion Search (SDS) was developed as a solution to the best-fit search problem. Thus, as a special case it is capable of solving the transform invariant pattern recognition problem. SDS is efficient and, although inherently probabilistic, produces very reliable solutions in widely ranging search conditions. However, to date a systematic formal investigation of its properties has not been carried out. This thesis addresses this problem. The thesis reports results pertaining to the global convergence of SDS as well as characterising its time complexity. However, the main emphasis of the work, reports on the resource allocation aspect of the Stochastic Diffusion Search operations. The thesis introduces a novel model of the algorithm, generalising an Ehrenfest Urn Model from statistical physics. This approach makes it possible to obtain a thorough characterisation of the response of the algorithm in terms of the parameters describing the search conditions in case of a unique best-fit pattern in the search space. This model is further generalised in order to account for different search conditions: two solutions in the search space and search for a unique solution in a noisy search space. Also an approximate solution in the case of two alternative solutions is proposed and compared with predictions of the extended Ehrenfest Urn model. The analysis performed enabled a quantitative characterisation of the Stochastic Diffusion Search in terms of exploration and exploitation of the search space. It appeared that SDS is biased towards the latter mode of operation. This novel perspective on the Stochastic Diffusion Search lead to an investigation of extensions of the standard SDS, which would strike a different balance between these two modes of search space processing. Thus, two novel algorithms were derived from the standard Stochastic Diffusion Search, ‘context-free’ and ‘context-sensitive’ SDS, and their properties were analysed with respect to resource allocation. It appeared that they shared some of the desired features of their predecessor but also possessed some properties not present in the classic SDS. The theory developed in the thesis was illustrated throughout with carefully chosen simulations of a best-fit search for a string pattern, a simple but representative domain, enabling careful control of search conditions.

Resource allocation problems have been widely studied according to various scenarios in literature. In such problems, a set of resources must be allocated to a set of agents, according to their own preferences. Self-organization issues in telecommunication, scheduling problems or supply chain management problems can be modeled using resource allocation problems. Such problems are usually solved by means of centralized techniques, where an omniscient entity determines how to optimally allocate resources. However, these solving methods are not well-adapted for applications where privacy is required. Moreover, several assumptions made are not always plausible, which may prevent their use in practice, especially in the context of agent societies. For instance, dynamic applications require adaptive solving processes, which can handle the evolution of initial data. Such techniques never consider restricted communication possibilities whereas many applications are based on them. For instance, in peer-to-peer networks, a peer can only communicate with a small subset of the systems. In this thesis, we focus on distributed methods to solve resource allocation problems. Initial allocation evolves step by step thanks to local agent negotiations. We seek to provide agent behaviors leading negotiation processes to socially optimal allocations. In this work, resulting resource allocations can be viewed as emergent phenomena. We also identify parameters favoring the negotiation efficiency. We provide the negotiation settings to use when four different social welfare notions are considered. The original method proposed in this thesis is adaptive, anytime and can handle any restriction on agent communication possibilities.

The very nature of space exploration implies "doing that which has never been done before." As such, the resources needed to meet the objectives of such a grand endeavor, if available, are extremely scarce. Every mission since the birth of the space programme has been resource limited. To overcome these scarcity or resource issues, natural laws developed in economics can be used. Such economic systems, which are referred to as market-based systems, are based on the laws of supply and demand. Supply and demand knowledge reveals true information about users needs for resources. This information removes the need to appeal to a higher authority or multiple meetings to resolve over subscription issues. The nature of this research programme was to apply a market-based system to a varied set of planetary exploration resource allocation problems. In the past, resource constrained problems were solved through the use of many engineers and a large number of "working" meetings. The approach was successful but was exceedingly time-consuming, labor-intensive, and very expensive. The questions addressed in this work were, 1. Could a market-based approach solve space exploration allocation problems, and 2. What were the limits of the type of problems that could be solved? Prior to this research, only one attempt had been made to apply a market-based system to a space exploration problem. The work was performed in 1991 to solve the over subscription of mission requests for Deep Space Network (DSN) antennas. [1] The work was never approved to move from the experimental phase into an operational environment. The research described in this overview was based on the DSN attempt and then extended to many different types of problems. This overview will discuss the application of this technique to the following four projects: 1. Development of the instrument payload for the Cassini mission to Saturn; 2. Manifest of Space Shuttle Secondary payloads; 3. Allocation of spacecraft time for RADAR observations during Earth orbital operations; and, 4. Manifest of Space Shuttles, which are destined for the International Space Station. Results from this research prove that market-based systems can solve resource over-subscription issues faced during development and operations of planetary spacecraft missions. In addition, the application of economic principles represents a unique and innovative approach to solving spacecraft resource issues and has been incorporated into the set of management tools available to solve issues in a quicker, cheaper and faster environment.

Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Civil and Environmental Engineering; and, (S.M.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2007.<br>Includes bibliographical references (p. 129-131).<br>We consider large-scale, network-based, resource allocation problems under uncertainty, with specific focus on the class of problems referred to as multi-commodity flow problems with time-windows. These problems are at the core of many network-based resource allocation problems. Inherent data uncertainty in the problem guarantees that deterministic optimal solutions are rarely, if ever, executed. Our work examines methods of proactive planning, that is, robust plan generation to protect against future uncertainty. By modeling uncertainties in data corresponding to service times, resource availability, supplies and demands, we can generate solutions that are more robust operationally, that is, more likely to be executed or easier to repair when disrupted. The challenges are the following: approaches to achieve robustness 1) can be extremely problem-specific and not general; 2) suffer from issues of tractability; or 3) have unrealistic data requirements. We propose in this work a modeling and algorithmic framework that addresses the above challenges.<br>(cont.) Our modeling framework involves a decomposition scheme that separates problems involving multi-commodity flows with time-windows into routing (that is, a routing master problem) and scheduling modules (that is, a scheduling sub-problem), and uses an iterative scheme to provide feedback between the two modules, both of which are more tractable than the integrated model. The master problem has the structure of a multi-commodity flow problem and the sub-problem is a set of network flow problems. This decomposition allows us to capture uncertainty while maintaining tractability. Uncertainty is captured in part by the master problem and in part by the sub-problem. In addition to solving problems under uncertainty, our decomposition scheme can also be used to solve large-scale resource allocation problems without uncertainty. As proof-of-concept, we apply our approach to a vehicle routing and scheduling problem and compare its solutions to those of other robust optimization approaches. Finally, we propose a framework to extend our robust, decomposition approach to the more complex problem of network design.<br>by Lavanya Marla.<br>S.M.

<p>In this work we examine a state constrained resource allocation model a with finite time horizon. Therefore, we use the necessary conditions of the Pontrjagin's Maximum Principle to find candidates for the solution and verify them later on using the sufficient conditions given by the duality concept of Klötzler. Moreover, we proof that the solution of the corresponding infinite horizon model does not fulfill the overtaking criterion of Weizsäcker.</p>

In this report we compare three different assignment algorithms in how they can be used to assign a set of drones to get to a set of goal locations in an as resource efficient way as possible. An experiment is set up to compare how these algorithms perform in a somewhat realistic simulated environment. The Robot Operating system (ROS) is used to create the experimental environment. We found that by introducing a threshold for the Hungarian algorithm we could reduce the total time it takes to complete the problem while only sightly increasing total distance traversed by the drones.

Web service composition is an inevitable aspect of web services technology, which solves complex problems by combining available basic services and ordering them to best suit the problem requirements. Automatic composition gives us flexibility of selecting best candidate services at composition time, this would require the user to define the resource allocation constraints for selecting and composing candidate web services. Resource allocation constraints define restrictions on how to allocate resources, and scheduling under resource allocation constraints to provide proper resource allocation to tasks. In this work, web service composition system named as CWSF (Composite Web Service Framework) constructed for users to define a workflow system in which a rich set of constraints can be defined on web services. On the contrary many technologies and studies, CWSF provides a user-friendly environment for modeling web service composition system. The output of the framework is the scheduling of web service composition in which how and when web services are executed are defined. With this work, a language, CWSL is defined to describe workflow, resource allocation constraints, selection and discovery rules of web services and associated semantic information. An important property of CWSF system is converting web service composition problem into a constraint satisfaction problem to find the best solution that meet the all criteria defined by user. Furthermore, CWSF has ability to display other possible solutions to provides users flexibility. This study also includes semantic matching and mapping facilities for service discovery.

Le domaine avionique a été transformé par l'apparition des architectures modulaires intégrées (IMA). Celles-ci définissent un support d'exécution et de communication standard et mutualisé afin de réduire la complexité de l'architecture physique. Cependant, du fait du partage des ressources, cette démarche introduit une plus grande complexité lors de la conception et de l'intégration des applications ce qui implique d'assister les concepteurs avec des outils dédiés. La présente thèse contribue à cet effort en se focalisant sur deux problèmes d'allocation de ressources : i) le problème de l'ordonnancement multiprocesseur de tâches strictement périodiques et ii) le problème du routage des messages échangés entre les fonctions avioniques. Le premier problème a été formalisé sous la forme d'un programme linéaire en nombres entiers afin de garantir un potentiel maximum d'évolution sur les durées d'exécutions des traitements. L'inefficacité d'une approche exacte pour des instances de grande taille, nous a conduit à développer une heuristique originale s'inspirant de la théorie des jeux couplée avec un algorithme multi-start. Le routage est formalisé sous la forme d'un problème d'optimisation sur la charge maximum des liens. Deux propositions sont faites pour le résoudre, l'une, exacte, est basée sur une formulation nœud-lien, et la seconde est une heuristique à deux niveaux basé sur une formulation lien-chemin. Mots-Clés en français : ordonnancement temps-réel, optimisation, systèmes avioniques, architectures modulaires intégrées, tâches strictement périodique, théorie de jeux, routage des liens virtuels

Le domaine avionique a été transformé par l'apparition des architectures modulaires intégrées (IMA). Celles-ci définissent un support d'exécution et de communication standard et mutualisé afin de réduire la complexité de l'architecture physique. Cependant, du fait du partage des ressources, cette démarche introduit une plus grande complexité lors de la conception et de l'intégration des applications ce qui implique d’assister les concepteurs avec des outils dédiés. La présente thèse contribue à cet effort en se focalisant sur deux problèmes d'allocation de ressources : i) le problème de l'ordonnancement multiprocesseur de tâches strictement périodiques et ii) le problème du routage des messages échangés entre les fonctions avioniques.Le premier problème a été formalisé sous la forme d’un programme linéaire en nombres entiers afin de garantir un potentiel maximum d'évolution sur les durées d'exécutions des traitements. L’inefficacité d’une approche exacte pour des instances de grande taille, nous a conduit à développer une heuristique originale s’inspirant de la théorie des jeux couplée avec un algorithme multi-start.Le routage est formalisé sous la forme d’un problème d’optimisation sur la charge maximum des liens. Deux propositions sont faites pour le résoudre, l’une, exacte, est basée sur une formulation nœud-lien, et la seconde est une heuristique à deux niveaux basé sur une formulation lien-chemin<br>The avionic domain has seen a profound evolution by the introduction of Integrated Modular Avionics (IMA). This defines a standardized execution and communication support in order to reduce the complexity of the physical architecture. Nevertheless, due to the sharing of resources, this reduction of complexity is opposed by an increased difficulty in application conception and integration, which necessitates dedicated tools for assisting system designers. This thesis’ contributions concern two major resource allocation problems: i) the multiprocessor scheduling of strictly periodic tasks and ii) the routing of messages exchanged between the avionic functions. The first problem was formulated using integer linear programming so as to guarantee a maximum evolution potential for the task execution durations. The inefficiency of this exact approach for large problem instances led us to develop an original heuristic, inspired from Game Theory, and further enhance it with a multi-start algorithm. The routing problem was formulated as an optimization one so as to minimize the maximum link loads. Two methods were proposed for this purpose, the first is exact based on node-link formulations, and the other is a two phase heuristic based on link-path formulations

In recent years, evolving technology has provided a wide range of resources for Military forces. However, that wideness also caused resource management difficulties in combat missions. Air Tasking Order (ATO) is prepared for various missions of air combats in order to reach objectives by an optimized resource management. Considering combinatorial military aspects with dynamic objectives and various constraints<br>computer support became inevitable for optimizing the resource management in air force operations. In this thesis, we study different optimization approaches for resource allocation problem of ATO preparation and analyze their performance. We proposed a genetic algorithm formulation with customized encoding, crossover and fitness calculation mechanisms by using the domain knowledge. A linear programming formulation of the problem is developed by integer decision variables and it is used for effectivity and efficiency analysis of genetic algorithm formulations.

In this study, results of a comparison on benchmark test problems are presented to investigate the performance of Primavera V.4.1 with its two resource allocation priority rules and MS Project 2003. Resource allocation capabilities of the packages are measured in terms of deviation from the upper bound of the minimum makespan. Resource constrained project scheduling problem instances are taken from PSPLIB which are generated under a factorial design from ProGen. Statistical tests are applied to the results for investigating the significance effectiveness of the parameters.

This work presents exact, hybrid algorithms for mixed resource Allocation and Scheduling problems; in general terms, those consist into assigning over time finite capacity resources to a set of precedence connected activities. The proposed methods have broad applicability, but are mainly motivated by applications in the field of Embedded System Design. In particular, high-performance embedded computing recently witnessed the shift from single CPU platforms with application-specific accelerators to programmable Multi Processor Systems-on-Chip (MPSoCs). Those allow higher flexibility, real time performance and low energy consumption, but the programmer must be able to effectively exploit the platform parallelism. This raises interest in the development of algorithmic techniques to be embedded in CAD tools; in particular, given a specific application and platform, the objective if to perform optimal allocation of hardware resources and to compute an execution schedule. On this regard, since embedded systems tend to run the same set of applications for their entire lifetime, off-line, exact optimization approaches are particularly appealing. Quite surprisingly, the use of exact algorithms has not been well investigated so far; this is in part motivated by the complexity of integrated allocation and scheduling, setting tough challenges for ``pure'' combinatorial methods. The use of hybrid CP/OR approaches presents the opportunity to exploit mutual advantages of different methods, while compensating for their weaknesses. In this work, we consider in first instance an Allocation and Scheduling problem over the Cell BE processor by Sony, IBM and Toshiba; we propose three different solution methods, leveraging decomposition, cut generation and heuristic guided search. Next, we face Allocation and Scheduling of so-called Conditional Task Graphs, explicitly accounting for branches with outcome not known at design time; we extend the CP scheduling framework to effectively deal with the introduced stochastic elements. Finally, we address Allocation and Scheduling with uncertain, bounded execution times, via conflict based tree search; we introduce a simple and flexible time model to take into account duration variability and provide an efficient conflict detection method. The proposed approaches achieve good results on practical size problem, thus demonstrating the use of exact approaches for system design is feasible. Furthermore, the developed techniques bring significant contributions to combinatorial optimization methods.

This work presents exact, hybrid algorithms for mixed resource Allocation and Scheduling problems; in general terms, those consist into assigning over time finite capacity resources to a set of precedence connected activities. The proposed methods have broad applicability, but are mainly motivated by applications in the field of Embedded System Design. In particular, high-performance embedded computing recently witnessed the shift from single CPU platforms with application-specific accelerators to programmable Multi Processor Systems-on-Chip (MPSoCs). Those allow higher flexibility, real time performance and low energy consumption, but the programmer must be able to effectively exploit the platform parallelism. This raises interest in the development of algorithmic techniques to be embedded in CAD tools; in particular, given a specific application and platform, the objective if to perform optimal allocation of hardware resources and to compute an execution schedule. On this regard, since embedded systems tend to run the same set of applications for their entire lifetime, off-line, exact optimization approaches are particularly appealing. Quite surprisingly, the use of exact algorithms has not been well investigated so far; this is in part motivated by the complexity of integrated allocation and scheduling, setting tough challenges for ``pure'' combinatorial methods. The use of hybrid CP/OR approaches presents the opportunity to exploit mutual advantages of different methods, while compensating for their weaknesses. In this work, we consider in first instance an Allocation and Scheduling problem over the Cell BE processor by Sony, IBM and Toshiba; we propose three different solution methods, leveraging decomposition, cut generation and heuristic guided search. Next, we face Allocation and Scheduling of so-called Conditional Task Graphs, explicitly accounting for branches with outcome not known at design time; we extend the CP scheduling framework to effectively deal with the introduced stochastic elements. Finally, we address Allocation and Scheduling with uncertain, bounded execution times, via conflict based tree search; we introduce a simple and flexible time model to take into account duration variability and provide an efficient conflict detection method. The proposed approaches achieve good results on practical size problem, thus demonstrating the use of exact approaches for system design is feasible. Furthermore, the developed techniques bring significant contributions to combinatorial optimization methods.

Resource constrained project scheduling problem (RCPSP) has been subject of extensive research in project management literature as RCPSP is one of the most challenging problems in the project management and is of great practical importance. In this thesis, resource allocation capabilities of Primavera Enterprise V.6.0-Project Management (P6) and MS Project 2007 (MS) were evaluated for solving overallocated problems in the RCPSP. Fourty-five resource overallocated instance projects were selected from the PSPLIB to evaluate performance of P6 and MS Project 2007. Three resource allocation priority rules of P6 and two resource allocation priority rules of MS were used for comparision. The best solutions of different priority rules for P6 and MS were compared by using t-test. Results of the P6 and MS were compared with the lower bounds and optimum solutions of the previous heuristic methods. The comparisions indicate that both P6 and MS has limited capabilities for solving overallocated problems in RCPSP. Especially for larger projects the widely used project management software packages can not provide optimum or near optimum solutions.

Since the events of September 11, 2001, the federal government is focused on homeland security and the fight against terrorism. This thesis addresses the idea of terrorist groups smuggling nuclear weapons through the borders of the United States. Security screening decisions are analyzed within maritime and aviation domains using discrete optimization models, specifically knapsack problems. The focus of the maritime chapters involves a risk-based approach for prescreening intelligence classifications for primary and secondary screening decisions given limited budget and resources. Results reveal that screening decisions are dependent on prescreening classification and the efficacy of the screening technologies. The screening decisions in the aviation security chapter highlight different performance measures to quantify the effectiveness of covering flights with the intent of covering targets. Results reveal that given scarce resources, such as screening devices capacities and budget, flights and targets can be covered with minimal expense to the system.

In this thesis we deal with two problems of resource allocation solved through a Mixed-Integer Linear Programming approach and a Mixed-Integer Nonlinear Chance Constraint Programming approach. In the first part we propose a framework to model general guillotine restrictions in two dimensional cutting problems formulated as Mixed-Integer Linear Programs (MILP). The modeling framework requires a pseudo-polynomial number of variables and constraints, which can be effectively enumerated for medium-size instances. Our modeling of general guillotine cuts is the first one that, once it is implemented within a state of-the-art MIP solver, can tackle instances of challenging size. Our objective is to propose a way of modeling general guillotine cuts via Mixed Integer Linear Programs (MILP), i.e., we do not limit the number of stages (restriction (ii)), nor impose the cuts to be restricted (restriction (iii)). We only ask the cuts to be guillotine ones (restriction (i)). We mainly concentrate our analysis on the Guillotine Two Dimensional Knapsack Problem (G2KP), for which a model, and an exact procedure able to significantly improve the computational performance, are given. In the second part we present a Branch-and-Cut algorithm for a class of Nonlinear Chance Constrained Mathematical Optimization Problems with a finite number of scenarios. This class corresponds to the problems that can be reformulated as Deterministic Convex Mixed-Integer Nonlinear Programming problems, but the size of the reformulation is large and quickly becomes impractical as the number of scenarios grows. We apply the Branch-and-Cut algorithm to the Mid-Term Hydro Scheduling Problem, for which we propose a chance-constrained formulation. A computational study using data from ten hydro plants in Greece shows that the proposed methodology solves instances orders of magnitude faster than applying a general-purpose solver for Convex Mixed-Integer Nonlinear Problems to the deterministic reformulation, and scales much better with the number of scenarios.

In this thesis we deal with two problems of resource allocation solved through a Mixed-Integer Linear Programming approach and a Mixed-Integer Nonlinear Chance Constraint Programming approach. In the first part we propose a framework to model general guillotine restrictions in two dimensional cutting problems formulated as Mixed-Integer Linear Programs (MILP). The modeling framework requires a pseudo-polynomial number of variables and constraints, which can be effectively enumerated for medium-size instances. Our modeling of general guillotine cuts is the first one that, once it is implemented within a state of-the-art MIP solver, can tackle instances of challenging size. Our objective is to propose a way of modeling general guillotine cuts via Mixed Integer Linear Programs (MILP), i.e., we do not limit the number of stages (restriction (ii)), nor impose the cuts to be restricted (restriction (iii)). We only ask the cuts to be guillotine ones (restriction (i)). We mainly concentrate our analysis on the Guillotine Two Dimensional Knapsack Problem (G2KP), for which a model, and an exact procedure able to significantly improve the computational performance, are given. In the second part we present a Branch-and-Cut algorithm for a class of Nonlinear Chance Constrained Mathematical Optimization Problems with a finite number of scenarios. This class corresponds to the problems that can be reformulated as Deterministic Convex Mixed-Integer Nonlinear Programming problems, but the size of the reformulation is large and quickly becomes impractical as the number of scenarios grows. We apply the Branch-and-Cut algorithm to the Mid-Term Hydro Scheduling Problem, for which we propose a chance-constrained formulation. A computational study using data from ten hydro plants in Greece shows that the proposed methodology solves instances orders of magnitude faster than applying a general-purpose solver for Convex Mixed-Integer Nonlinear Problems to the deterministic reformulation, and scales much better with the number of scenarios.

This thesis is concerned with the development of heuristic algorithms for the popular Quadratic Assignment Problem (QAP) which finds a wide variety of applications in various fields. This discrete optimization problem, which seeks the placement of m facilities on m locations in order to minimize a quadratic interactive cost, is well known to be NP-hard and turns out to be computationally intractable for even moderately sized problems. Hence, problems involving more than 12-15 facilities usually need to be analysed by approximate solution procedures. The more successful heuristic procedures which exist for problem QAP are computationally intensive, some of these resulting from a premature termination of exact solution procedures. The motivation here is to develop a polynomial time heuristic which is effective with respect to the quality of solutions obtained, while at the same time not being computationally very expensive. The method proposed herein is flexible in that one can operate it to suitably trade solution quality against effort as desired, and is portable in that the modules used as building blocks can be employed in conjunction with other heuristics as well. Computational experience on test problems found in the literature is provided to evaluate the worth of this method.<br>M.S.

The term resource is used to refer to a machine, tool-group, piece of equipment or personnel. Optimization models for resource maintenance are obtained in conjunction with other production related decisions like production planning, production scheduling, resource allocation and job inspection. Emphasis is laid on integrating the above inter-dependent decisions into a unified optimization framework. This is accomplished for large stationary resources, small non-stationary resources with high breaking rate and for resources that form a part of a network. Owing to large problem size and high uncertainty, the optimal decisions are determined by formulating and solving the above problems as Markov decision processes (MDPs). Approximate dynamic programming based algorithms are used for solving the large optimization problems at hand. The performance of resulting near optimal policies is compared with that of traditional formulations in all cases. The latter treat the resource maintenance decisions independent of other manufacturing related decisions. In certain formulations, the resource state is not completely observable. This results in a partially observable MDP (POMDP). An alternative algorithm for the solution of POMDP is developed, where several mixed integer linear programs (MILPs) are solved during each ADP iteration. This helps obtain better quality solutions for the POMDPs with very large or continuous action spaces in an efficient manner.

Location-allocation problems can be described generically as follows: Given the location or distribution (perhaps, probabilistic) of a set of customers and their associated demands for a given product or service, determine the optimum location of a number of service facilities and the allocation of products or services from facilities to customers, so as to minimize total (expected) location and transportation costs. This study is concerned with a particular subclass of location-allocation problems involving capacitated facilities and a continuum of demand. Specifically, two minisum, network-based location-allocation problems are analyzed in which facilities having known finite capacities are to be located so as to optimally supply/serve a known continuum of demand. The first problem considered herein, is an absolute p-median problem in which p > l capacitated facilities are to be located on a chain graph having both nodal and link demands, the latter of which are defined by nonnegative, integrable demand functions. In addition, the problem is balanced, in that it is assumed the total demand equals the total supply. An exact solution procedure is developed, wherein the optimality of a certain location-allocation scheme (for any given ordering of the facilities) is used to effect a branch and bound approach by which one can identify an optimal solution to the problem. Results from the chain graph analysis are then used to develop an algorithm with which one can solve a dynamic, sequential location-allocation problem in which a single facility per period is required to be located on the chain. Finally, an exact solution procedure is developed for locating a capacitated, absolute 2-median on a tree graph having both nodal and link demands and for which the total demand is again equal to the total supply. This procedure utilizes an algorithm to construct two subtrees, each of whose ends constitute a set of candidate optimal locations for one of the two elements of an absolute 2-median. Additional localization results are used to further reduce the number of candidate pairs (of ends) that need to be considered, and then a post-localization analysis provides efficient methods of comparing the relative costs of the remaining pairs.<br>Ph. D.

PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO<br>COORDENAÇÃO DE APERFEIÇOAMENTO DO PESSOAL DE ENSINO SUPERIOR<br>PROGRAMA DE SUPORTE À PÓS-GRADUAÇÃO DE INSTS. DE ENSINO<br>Esta dissertação trata sobre o problema de alocação de balcões de check-in em um aeroporto. O processo de check-in é um dos serviços aeroportuários mais problemáticos. Ineficiências neste processo propagam problemas como o efeito chicote, sendo uma das causas dos baixos níveis de serviço. Além disso, em geral, as ilhas de check-in ocupam grandes áreas nos aeroportos afetando possíveis receitas de concessão. Uma alocação eficiente de balcões para o processo de check-in poderia reduzir custos aeroportuários e elevar o nível de serviço oferecido para os passageiros. Visando otimizar o ACCAP a nível diário, este trabalho apresenta uma nova metodologia que combina otimização e simulação. O objetivo é determinar o número ótimo, programação e localização de balcões para check-in, de forma a minimizar custos operacionais e garantir um dado nível de serviço. A metodologia proposta divide-se em três passos. O passo número um faz uso de modelos de otimização para o problema de alocação de balcões de check-in num aeroporto considerando uma política de alocação variável. Dois novos modelos de optimização são apresentados, um para um sistema de check-in comum e outro para um sistema dedicado. Os modelos visam determinar o menor número de balcões por intervalo de tempo e ao mesmo tempo equilibrar os custos operacionais e o nível de serviço oferecido. Estes modelos apresentam dois conjuntos de restrições que levam em consideração aspectos estocásticos do processo de check-in. Um conjunto considera o conceito de fator de utilização da teoria de filas e o outro, a flutuação na taxa de chegada dos passageiros entre intervalos de tempo adjacentes. O passo número dois usa simulação para avaliar se os resultados do passo anterior cumprem um determinado nível de serviço quando são consideradas incertezas na chegada dos passageiros e tempo de atendimento no processo de check-in. Além disso, a simulação terminada ajuda definir a duração adequada do intervalo de tempo e parâmetros chaves relativos aos modelos de otimização. Em geral, o processo de check-in é analisado considerando um padrão de chegada dos passageiros em procura do serviço de registro e como estes passageiros são atendidos nos balcões. A fim de avaliar essas distribuições: tempo entre chegada dos passageiros e tempo de atendimento, um conjunto de cenários é definido. Os principais cenários para ser testados são para um sistema comum e um dedicado. Assim, testando certo número de replicações para cada experimento de simulação, as estatísticas de desempenho do sistema são obtidas. Estatísticas de interesse tem que ver com o tempo de espera e tamanho da fila. O passo número três é aplicado só para sistemas de check-in dedicados. Uma vez que se conhece o número de balcões por intervalo de tempo para cada voo é possível minimizar o total de balcões satisfazendo a restrição de adjacência. Esta restrição estipula que todos os balcões do mesmo voo devem estar juntos. Sem a restrição de adjacência, o número mínimo de balcões poderia ser achado facilmente através de uma alocação fixa de recursos por intervalo de tempo. Este procedimento indicaria o número máximo de balcões requeridos no intervalo de tempo de maior ocupação, mas este resultado não garante uma solução que satisfaz a restrição de adjacência. Assim, os modelos matemáticos relacionados com programação de recursos adjacentes tem que garantir uma alocação ótima de balcões com balcões. A metodologia proposta é testada com um caso de estudo existente na literatura. Primeiro, considerando realidades práticas do planejamento de recursos nos processos aeroportuários, a duração de meia hora identificou-se como o tamanho adequado do intervalo de tempo para a discretização do problema de alocação de balcões de check-in num aeroporto. Depois, comparando os resultados obtidos entre a metodologia e o caso de estudo baseado só em simulação, os resultados demostram a confiabilidade<br>This dissertation deals with the Airport Check-in Counter Allocation Problem (ACCAP). The check-in process is one of the most problematic airport services. Inefficient check-in processes propagate problems as a bullwhip effect being the basis for low quality service levels. Moreover, check-in counters usually occupy a considerable area in airports affecting concession revenues. An efficient check-in process may therefore contribute to reduce airport costs and increase service level. This work presents a new methodology to optimize the ACCAP that combines optimization and simulation. The objective is to determine the optimal number, schedule and location of check-in counters assigned to departing flights, such that operational costs are minimized and a given service level is ensured. The methodology is composed of three steps. Step 1 uses optimization models to determine the optimal number of desks. Step 2 uses simulation to assess if the results obtained in Step 1 meet the service level. Step 3 uses an optimization model to enforce an adjacent constraint for dedicated check-in systems. For Step 1 it is developed two new optimization models for common and dedicated check-in systems that include constraints regarding the utilization factor concept of queue theory, and the fluctuation in the passenger arrival rate. Step 2 uses standard simulation methods and Step 3 uses models existing in literature. The methodology is tested in a real sample to show its reliability and accuracy. Then, it is applied to a case study in a busiest airport. The results demonstrate the positive performance of the process considering the trade-off between operational costs and a given service level. Also, a maximum waiting time of thirty minutes is obtained and it is incorporated to the overall service level.

The recent advances in mobile computing and distributed multimedia systems allow mobile hosts (clients) to access wireless multimedia Data at anywhere and at anytime. In accessing multimedia information on the distributed multimedia servers from wireless personal communication service systems, a channel assignment problem and synchronization problems should be solved efficiently. Recent demand for mobile telephone service have been growing rapidly while the electro-magnetic spectrum of frequencies allocated for this purpose remain limited. Any solution to the channel assignment problem is subject to this limitation, as well as the interference constraint between adjacent channels in the spectrum. Channel allocation schemes provide a flexible and efficient access to bandwidth in wireless and mobile communication systems. In this dissertation, both an efficient distributed algorithm for dynamic channel allocation based upon mutual exclusion model, and an efficient distributed synchronization algorithm using Quasi-sink for wireless and mobile multimedia systems to ensure and facilitate mobile client access to multimedia objects are proposed. Algorithm's performance with several channel systems using different types of call arrival patterns is determined analytically. A set of simulation experiments to evaluate the performance of our scheme using message complexity and buffer usage at each frame arrival time.

This research explores the political factors that affect the allocation of antipoverty funds in Mexican municipalities. Specifically, it analyses whether the adoption of FAISM, a decentralised fiscal fund intended to reduce poverty, did, in fact, help provide better services for the poor or if it was capture by political influence. In this sense, my work addresses a classic question of when and how political institutions can effectively improve the allocation of antipoverty funds. In the last decade, an ambitious decentralisation process was promoted in Mexico as a way to strengthen local governance and hence improve basic service provision. The idea was to limit politician‟s influence on resource allocation and return decision making to the people. By looking at more than 57,000 FAISM projects carried out in 122 municipalities of Estado de Mexico between 1998 and 2006 my work argues that political influence could not be circumvented and clientelism remained as a common political practice to allocate antipoverty funds. My findings demonstrate that the three major political parties relied on FAISM to obtain political benefits through the allocation of private goods. Regarding the effects of democratic institutions, my work demonstrates that greater party competition increases the probability that FAISM was used for public benefit. Similarly, there is a propensity towards greater spending on clientelism during elections. Although these factors influence the allocation of municipal funds, my work does not find concluding evidence to test the impact of fund allocation and poverty reduction. My dissertation makes three important contributions to the literature. Substantively, it qualifies the premise that clientelistic linkages between voters and politicians prevail and shows the conditions under which local politicians strategically allocate antipoverty funds for political gain. A second, methodological, contribution is the use of a more refined measure of social spending at the municipal level by looking at the split between public and private goods. Finally, this dissertation seeks to inform the longstanding debate about the ways in which democratic politics can contribute to effective poverty reduction.

One of the most critical tasks after a natural disaster is to organize and execute humanitarian relief operations effectively and efficiently while reaching an equitable outcome. However, due to limited resources in the initial stage of response, it becomes challenging for logistics planning authorities to target needed individuals. The concerns would be with providing an unbiased platform to make decisions about equitable distribution schedules. Therefore, developing an effective and efficient disaster relief plan that tries to treat individuals as equitable as possible was the main motivation in this research. For this purpose, this dissertation studied a novel last mile distribution plan in the initial response phase where the key focus is the preservation of lives. An integrated vehicle routing and resource allocation problem was investigated and formulated in an routing-allocation model (RAP). The theoretical foundation of RAP is formulated as an egalitarian model where resources are to be distributed so as to maximize the welfare of those in greatest need. The strategic goal is to alleviate human deprivation and suffering by minimizing the response time in regard to each beneficiary?s needs fulfillment and delivery delay on the route. Equity is quantified with a min-max objective on a deprivation cost, which is a non-linear function of deprivation time. The objective function is set to minimize the maximum deprivation cost of the deliveries so that supplies arrive in a cyclical manner while all demand sites are treated equitably.<br>Upper Great Plains Transportation Institute (UGPTI)

Since its inception, cognitive radio (CR) has quickly been accepted as the enabling radio technology for next-generation wireless communications. A CR promises unprecedented flexibility in radio functionalities via programmability at the lowest layer, which was once done in hardware. Due to its spectrum sensing, learning, and adaptation capabilities, CR is able to address the heart of the problem associated with spectrum scarcity (via dynamic spectrum access (DSA)) and interoperability (via channel switching). It is envisioned that CR will be employed as a general radio platform upon which numerous wireless applications can be implemented. For both theoretical and practical purposes, it is important for network researchers to model a cognitive radio ad hoc network (CRN) and optimize its performance. Such efforts are important not only for theoretical understanding, but also in that such results can be used as benchmarks for the design of distributed algorithms and protocols. However, due to some unique characteristics associated with CRNs, existing analytical techniques may not be applied directly. As a result, new theoretical results, along with new mathematical techniques, need to be developed. In this thesis, we focus on modeling and optimization of CRNs. In particular, we will study multicast communications in CRN and MIMO-empowered CRN, which we describe as follows. An important service that must be supported by CRNs is multicast. Although there are a lot of research on multicast in ad hoc networks, those results cannot be applied to a CRN, because of the complexity associated with a CR node (e.g., multiple available frequency bands, difference in available bands from neighboring nodes). In addition, a single-layer approach (e.g., multicast routing) is overly simplistic when resource optimization (i.e., minimizing network resource) is the main objective. For this purpose, a cross-layer approach is usually necessary, which should include joint consideration of multiple lower layers, in addition to network layer. However, such a joint formulation is usually highly complex and difficult. In this thesis, we aim to develop some novel algorithms that provide near-optimal solutions. Our goal is to minimize the required network-wide resource to support a set of multicast sessions, with a certain bit rate for each multicast session. The unique characteristics associated with CR and distinguish this problem from existing multicast research for ad hoc networks. In this work, we formulate this problem via a cross-layer approach with joint consideration of scheduling and routing. Although the problem formulation is in the form of mixed integer linear program (MILP), we are successful in developing a polynomial time algorithm that offers highly competitive solution. The main ideas of the algorithm include identification of key integer variables, fixing these variables via a series of relaxed linear program (LP), and tying up such integer fixing with a bottom-up tree construction. By comparing with a lower bound, we find that the proposed algorithm can provide a solution that is very close to the optimum. In parallel to the development of CR for DSA, multiple-input multiple-output (MIMO) has widely been accepted and now implemented in commercial wireless products to increase capacity. The goal of MIMO and how it operates are largely independent and orthogonal to CR. Instead of exploiting idle channels for wireless communications, MIMO attempts to increase capacity within the same channel via space-time processing. Assuming that CR and MIMO will ultimately marry each other and offer the ultimate flexibility in DSA and spectrum efficiency, we would like to inquire the potential capacity gain in this marriage. In particular, we are interested in how such marriage will affect the capacity of a user communication session in a multi-hop CRN. We explore MIMO-empowered CR network, which we call CRN^MIMO, to achieve ultimate flexibility in DSA and spectrum efficiency. Given that CR and MIMO handle interference at different levels (across channels vs. within a channel), we are interested in how joint optimization of both will maximize user capacity in a multi-hop network. To answer this question, we develop a tractable mathematical model for CRN^MIMO, which captures the essence of channel assignment (for CR) and degree-of-freedom (DoF) allocation (for MIMO). Based on this mathematical model, we use numerical results to show how channel assignment in CRN and DoF allocation in MIMO can be jointly optimized to maximize capacity. More important, for a CRN^MIMO with A_MIMO antennas at each node, we show that joint optimization of CR and MIMO offers more than A_MIMO-fold capacity increase than a CRN with only a single antenna at each node.<br>Master of Science

Thesis (Ph.D. (Statistics)) -- University of Limpopo, 2017<br>Operations Research (OR) is a scientific method for developing quantitatively well-grounded recommendations for decision making. While it is true that it uses a variety of mathematical techniques, OR has a much broader scope. It is in fact a systematic approach to solving problems, which uses one or more analytical tools in the process of analysis. Over the years, OR has evolved through different stages. This study is motivated by new real-world challenges needed for efficiency and innovation in line with the aims and objectives of OR – the science of better, as classified by the OR Society of the United Kingdom. New real-world challenges are encountered on a daily basis from problems arising in the fields of water, energy, agriculture, mining, tourism, IT development, natural phenomena, transport, climate change, economic and other societal requirements. To counter all these challenges, new techniques ought to be developed. The growth of global markets and the resulting increase in competition have highlighted the need for OR techniques to be improved. These developments, among other reasons, are an indication that new techniques are needed to improve the day-to-day running of organisations, regardless of size, type and location. The principal aim of this study is to modify and develop new OR techniques that can be used to solve emerging problems encountered in the areas of linear programming, integer programming, mixed integer programming, network routing and travelling salesman problems. Distribution models, resource allocation models, travelling salesman problem, general linear mixed integer ii programming and other network problems that occur in real life, have been modelled mathematically in this thesis. Most of these models belong to the NP-hard (non-deterministic polynomial) class of difficult problems. In other words, these types of problems cannot be solved in polynomial time (P). No general purpose algorithm for these problems is known. The thesis is divided into two major areas namely: (1) network models and (2) resource allocation and distribution models. Under network models, five new techniques have been developed: the minimum weight algorithm for a non-directed network, maximum reliability route in both non-directed and directed acyclic network, minimum spanning tree with index less than two, routing through 0k0 specified nodes, and a new heuristic to the travelling salesman problem. Under the resource allocation and distribution models section, four new models have been developed, and these are: a unified approach to solve transportation and assignment problems, a transportation branch and bound algorithm for the generalised assignment problem, a new hybrid search method over the extreme points for solving a large-scale LP model with non-negative coefficients, and a heuristic for a mixed integer program using the characteristic equation approach. In most of the nine approaches developed in the thesis, efforts were done to compare the effectiveness of the new approaches to existing techniques. Improvements in the new techniques in solving problems were noted. However, it was difficult to compare some of the new techniques to the existing ones because computational packages of the new techniques need to be developed first. This aspect will be subject matter of future research on developing these techniques further. It was concluded with strong evidence, that development of new OR techniques is a must if we are to encounter the emerging problems faced by the world today. Key words: NP-hard problem, Network models, Reliability, Heuristic, Largescale LP, Characteristic equation, Algorithm.

Aujourd'hui, l'extension des exigences du trafic de données sans fil dépasse le taux de croissance de la capacité des nouvelles technologies d'accès sans fil. Par conséquent, les réseaux sans fil mobiles de la future génération proposent des architectures hétérogènes, généralement appelées réseaux sans fil hétérogènes (HWN). HWN se caractérisent par l'intégration des réseaux cellulaires et des réseaux locaux sans fil (WLAN) pour répondre aux besoins des utilisateurs et améliorer la capacité du système. En fait, l'intégration de différents types de technologies d'accès sans fil dans HWN offre des choix flexibles pour que les utilisateurs soient associés au réseau qui répond le mieux à leurs besoins. Dans ce contexte, cette thèse traite le problème d'association d'utilisateurs et le problème d'allocation de ressources dans un système sans fil hétérogène basé sur des points d'accès Wi-Fi intégrés et des stations de base L TE. Les contributions de cette thèse pourraient être divisées en trois parties principales. Dans la première partie, un nouveau problème d'association d'utilisateurs et d'optimisation de l'allocation des ressources est formulé pour maximiser la satisfaction globale des utilisateurs dans le système. La satisfaction de l'utilisateur est basée sur une fonction de profit pondérée qui vise à améliorer la puissance relative du signal reçu et la diminution de la consommation d'énergie des terminaux mobiles (MT). Étant donné qu'un MT n'est autorisé à être associé qu'à un seul réseau à la fois, le problème d'optimisation formulé est binaire avec une complexité NP complète. Ensuite, plusieurs solutions centralisées avec une complexité à temps polynomial sont proposées pour résoudre le problème formulé. Les solutions proposées sont basées sur des approches heuristiques et sur la relaxation continue du problème d'optimisation binaire formulé. La deuxième partie de la thèse vise à fournir une solution distribuée pour le problème formulé. La solution distribuée proposée déploie la technique de détente lagrangienne pour convertir le problème global formulé en plusieurs problèmes de Knapsack distribués, chaque réseau traite son problème Knapsack correspondant. La méthode de sous gradient est utilisée pour trouver les multiplicateurs lagrangiens optimaux ou sous optimaux. Enfin, la troisième partie de la thèse étudie de nouvelles perspectives de la formulation du problème d'optimisation et ses solutions centralisées et distribuées correspondantes. Un problème d'association d'utilisateurs et d'allocation de ressources basé sur la priorité est formulé. Le problème est ensuite réduit en plusieurs problèmes résolus à l'aide des solutions proposées réparties et centralisées. En outre, une nouvelle solution de maximisation de l'efficacité énergétique est proposée en modifiant les objectifs du problème d'optimisation originalement formulé<br>It is indicated that the expansion of the wireless data traffic requirements exceeds the capacity growth rate of new wireless access technologies. Therefore, next-generation mobile wireless networks are moving toward heterogeneous architectures usually referred to as heterogeneous wireless networks (HWNs). HWNs are usually characterized by the integration of cellular networks and wireless local area networks (WLANs) to meet user requirements and enhance system capacity. In fact, integrating different types of wireless access technologies in HWNs provides flexible choices for users to be associated with the network that best satisfies their needs. In this context, this thesis discusses the user association and downlink resource allocation problem in a heterogeneous wireless system that is based on integrated Wi-Fi access points (APs) and long-term evolution (L TE) base stations (BSs). The contributions of this thesis could be divided into three main parts. In the first part, a novel user association and resource allocation optimization problem is formulated to maximize the overall user satisfaction in the system. The user satisfaction is based on a weighted profit function that aims at enhancing the relative received signal strength and decreasing the power consumption of mobile terminals (MTs). Since a MT is only allowed to be associated with a single network at a time, the formulated optimization problem is binary with an NP-complete complexity. Then, multiple centralized solutions with polynomial-time complexities are proposed to solve the formulated problem. The proposed centralized solutions are based on heuristic approaches and on the continuous re laxation of the formulated binary optimization problem. The second part of the thesis aims at providing a distributed solution for the formulated problem. The proposed distributed solution deploys the Lagrangian relaxation .technique in order to convert the global formulated problem into multiple distributed Knapsack problems each network processes its corresponding Knapsack problem. The sub-gradient method is used in order to find the optimal, or near optimal, Lagrangian multipliers. Finally, the third part of the thesis studies new perspectives of the formulated optimization problem and its corresponding centralized and distributed solutions. Mainly, a generalized priority-aware user association and resource allocation problem is formulated. The priority-aware problem is then reduced into multiple problems that are solved using the proposed centralized and distributed solutions. Moreover, a novel power efficiency maximization solution is proposed by altering the objectives of the main formulated optimization problem

This dissertation addresses five fundamental resource allocation problems on networks, all of which have applications to support Homeland Security or industry challenges. In the first application, we model and solve the strategic problem of minimizing the expected loss inflicted by a hostile terrorist organization. An appropriate allocation of certain capability-related, intent-related, vulnerability-related, and consequence-related resources is used to reduce the probabilities of success in the respective attack-related actions, and to ameliorate losses in case of a successful attack. Given the disparate nature of prioritizing capital and material investments by federal, state, local, and private agencies to combat terrorism, our model and accompanying solution procedure represent an innovative, comprehensive, and quantitative approach to coordinate resource allocations from various agencies across the breadth of domains that deal with preventing attacks and mitigating their consequences. Adopting a nested event tree optimization framework, we present a novel formulation for the problem as a specially structured nonconvex factorable program, and develop two branch-and-bound schemes based respectively on utilizing a convex nonlinear relaxation and a linear outer-approximation, both of which are proven to converge to a global optimal solution. We also investigate a fundamental special-case variant for each of these schemes, and design an alternative direct mixed-integer programming model representation for this scenario. Several range reduction, partitioning, and branching strategies are proposed, and extensive computational results are presented to study the efficacy of different compositions of these algorithmic ingredients, including comparisons with the commercial software BARON. The developed set of algorithmic implementation strategies and enhancements are shown to outperform BARON over a set of simulated test instances, where the best proposed methodology produces an average optimality gap of 0.35% (compared to 4.29% for BARON) and reduces the required computational effort by a factor of 33. A sensitivity analysis is also conducted to explore the effect of certain key model parameters, whereupon we demonstrate that the prescribed algorithm can attain significantly tighter optimality gaps with only a near-linear corresponding increase in computational effort. In addition to enabling effective comprehensive resource allocations, this research permits coordinating agencies to conduct quantitative what-if studies on the impact of alternative resourcing priorities. The second application is motivated by the author's experience with the U.S. Army during a tour in Iraq, during which combined operations involving U.S. Army, Iraqi Army, and Iraqi Police forces sought to interdict the transport of selected materials used for the manufacture of specialized types of Improvised Explosive Devices, as well as to interdict the distribution of assembled devices to operatives in the field. In this application, we model and solve the problem of minimizing the maximum flow through a network from a given source node to a terminus node, integrating different forms of superadditive synergy with respect to the effect of resources applied to the arcs in the network. Herein, the superadditive synergy reflects the additional effectiveness of forces conducting combined operations, vis-à-vis unilateral efforts. We examine linear, concave, and general nonconcave superadditive synergistic relationships between resources, and accordingly develop and test effective solution procedures for the underlying nonlinear programs. For the linear case, we formulate an alternative model representation via Fourier-Motzkin elimination that reduces average computational effort by over 40% on a set of randomly generated test instances. This test is followed by extensive analyses of instance parameters to determine their effect on the levels of synergy attained using different specified metrics. For the case of concave synergy relationships, which yields a convex program, we design an inner-linearization procedure that attains solutions on average within 3% of optimality with a reduction in computational effort by a factor of 18 in comparison with the commercial codes SBB and BARON for small- and medium-sized problems; and outperforms these softwares on large-sized problems, where both solvers failed to attain an optimal solution (and often failed to detect a feasible solution) within 1800 CPU seconds. Examining a general nonlinear synergy relationship, we develop solution methods based on outer-linearizations, inner-linearizations, and mixed-integer approximations, and compare these against the commercial software BARON. Considering increased granularities for the outer-linearization and mixed-integer approximations, as well as different implementation variants for both these approaches, we conduct extensive computational experiments to reveal that, whereas both these techniques perform comparably with respect to BARON on small-sized problems, they significantly improve upon the performance for medium- and large-sized problems. Our superlative procedure reduces the computational effort by a factor of 461 for the subset of test problems for which the commercial global optimization software BARON could identify a feasible solution, while also achieving solutions of objective value 0.20% better than BARON. The third application is likewise motivated by the author's military experience in Iraq, both from several instances involving coalition forces attempting to interdict the transport of a kidnapping victim by a sectarian militia as well as, from the opposite perspective, instances involving coalition forces transporting detainees between interment facilities. For this application, we examine the network interdiction problem of minimizing the maximum probability of evasion by an entity traversing a network from a given source to a designated terminus, while incorporating novel forms of superadditive synergy between resources applied to arcs in the network. Our formulations examine either linear or concave (nonlinear) synergy relationships. Conformant with military strategies that frequently involve a combination of overt and covert operations to achieve an operational objective, we also propose an alternative model for sequential overt and covert deployment of subsets of interdiction resources, and conduct theoretical as well as empirical comparative analyses between models for purely overt (with or without synergy) and composite overt-covert strategies to provide insights into absolute and relative threshold criteria for recommended resource utilization. In contrast to existing static models, in a fourth application, we present a novel dynamic network interdiction model that improves realism by accounting for interactions between an interdictor deploying resources on arcs in a digraph and an evader traversing the network from a designated source to a known terminus, wherein the agents may modify strategies in selected subsequent periods according to respective decision and implementation cycles. We further enhance the realism of our model by considering a multi-component objective function, wherein the interdictor seeks to minimize the maximum value of a regret function that consists of the evader's net flow from the source to the terminus; the interdictor's procurement, deployment, and redeployment costs; and penalties incurred by the evader for misperceptions as to the interdicted state of the network. For the resulting minimax model, we use duality to develop a reformulation that facilitates a direct solution procedure using the commercial software BARON, and examine certain related stability and convergence issues. We demonstrate cases for convergence to a stable equilibrium of strategies for problem structures having a unique solution to minimize the maximum evader flow, as well as convergence to a region of bounded oscillation for structures yielding alternative interdictor strategies that minimize the maximum evader flow. We also provide insights into the computational performance of BARON for these two problem structures, yielding useful guidelines for other research involving similar non-convex optimization problems. For the fifth application, we examine the problem of apportioning railcars to car manufacturers and railroads participating in a pooling agreement for shipping automobiles, given a dynamically determined total fleet size. This study is motivated by the existence of such a consortium of automobile manufacturers and railroads, for which the collaborative fleet sizing and efforts to equitably allocate railcars amongst the participants are currently orchestrated by the \textit{TTX Company} in Chicago, Illinois. In our study, we first demonstrate potential inequities in the industry standard resulting either from failing to address disconnected transportation network components separately, or from utilizing the current manufacturer allocation technique that is based on average nodal empty transit time estimates. We next propose and illustrate four alternative schemes to apportion railcars to manufacturers, respectively based on total transit time that accounts for queuing; two marginal cost-induced methods; and a Shapley value approach. We also provide a game-theoretic insight into the existing procedure for apportioning railcars to railroads, and develop an alternative railroad allocation scheme based on capital plus operating costs. Extensive computational results are presented for the ten combinations of current and proposed allocation techniques for automobile manufacturers and railroads, using realistic instances derived from representative data of the current business environment. We conclude with recommendations for adopting an appropriate apportionment methodology for implementation by the industry.<br>Ph. D.

Health Technology Assessment (HTA) relies on evidence-based medicine to inform drug coverage recommendations about the most efficient use of resources. Despite appraising the same evidence based on similar methodological approaches, HTA recommendations for the same drug differ across countries. This thesis aimed to understand the reasons for these differences, and based on cross-national comparisons, whether they are a consequence of methodological challenges in HTA. A mixed methods research design was used to develop a methodological framework that allows to breakdown these complex processes in a comparable and understandable manner, by considering: (a) the evidence appraised, (b) its interpretation, and (c) how this influenced the final decision. Ten orphan drug-indication pairs appraised in four countries (England, Scotland, Sweden and France (N=35)) were systematically analysed and compared on this basis. Results present the criteria accounted for at each stage of the process in the decisions, the reasons for differences across countries, and how HTA bodies are dealing with issues relating to orphan drugs. Quantitative analysis of these provided information about agency-specific risk and value preferences, and measured agreement in interpreting the same evidence. There was heterogeneity within and across countries in the criteria accounted for and reasons for cross-country differences. Interviews to competent authorities provided insights about these differences and implications for HTA. Although agreement was seen in the evidentiary requirements or preferences, there were subtle differences in the circumstances where uncertain evidence may be considered acceptable, partly explaining diverging HTA recommendations. The three main contributions of this thesis are: (1) the development of a methodological framework to understand what criteria feed into HTAs, which can be applied to other drugs and countries; (2) through its application, the identification of a full taxonomy of criteria considered in decisionmaking; and (3) the ability to understand the differences in HTA recommendations across countries. A better understanding of HTA in different settings may help advance these processes, and, ultimately, improve access to treatments.

Effective and efficient use of public resources has a vital importance for Turkey, as for all countries. To serve this purpose, public financial management was reformed and performance budgeting system was begun to be implemented in Turkey. In order performance budgeting system to be properly put into practice, the system should have been well designed, regulations should have been adequately prepared and necessary information, guidance and support should be provided to the implementers. In this study, the implementation of performance budgeting system in Turkey was investigated from the perspective of public administrations under general budget and problems in the system were identified. Comments, experiences and suggestions of administrations were obtained via questionnaires and interviews, and analyzed. Additionally, regulatory legal documents and reports of administrations prepared within the performance budgeting concept were also investigated. In order to provide constitution of a more properly designed system and more easy and smooth implementation, to obtain a well adopted system by the implementers and to get results of better quality, proposals were put forward corresponding to the identified problems. Integrated analytic network process with a strategic resource allocation model proposal is presented to be used in update of performance programs in the aim of minimizing the deviations from targeted performance within budget constraints. The proposed model is implemented for the Strategy Development Unit of the Undersecretariat of Treasury.