As the "network of network", the Internet has been playing a central and crucial role in modern society, culture, knowledge, businesses and so on in a period of over two decades by supporting a wide variety of network technologies and applications. However, due to its popularity and multi-provider nature, the future development of the Internet is limited to simple incremental updates. To address this challenge, network virtualization has been propounded as a potential candidate to provide the essential basis for the future Internet architecture. Network virtualization is capable of providing an open and flexible networking environment in which service providers are allowed to dynamically compose multiple coexisting heterogeneous virtual networks on a shared substrate network. Such a flexible environment will foster the deployment of diversified services and applications. A major challenge in network virtualization area is the Virtual Network Embedding (VNE), which aims to statically or dynamically allocate virtual nodes and virtual links on substrate resources, physical nodes and paths. Making effective use of substrate resources requires high-efficient and survivable VNE techniques. The main contribution of this thesis is two high-performance p-Cycle-based survivable virtual network embedding approaches. These approaches take advantage of p-Cycle-based protection techniques that minimize the backup resources while providing a full VN protection scheme against link and node failures.

Chemical and biological contaminants can enter a drinking water distribution system through one of the many access points to the network and can spread quickly affecting a very large area. This is of great concern, and water utilities need to consider effective tools and mitigation strategies to improve water network security. This work presents two components that have been integrated into EPA’s Water Security Toolkit, an open-source software package that includes a set of tools to help water utilities protect the public against potential contamination events. The first component is a novel water quality modeling framework referred to as Merlion. The linear system describing contaminant spread through the network at the core of Merlion provides several advantages and potential uses that are aligned with current emerging water security applications. This computational framework is able to efficiently generate an explicit mathematical model that can be easily embedded into larger mathematical system. Merlion can also be used to efficiently simulate a large number of scenarios speeding up current water security tools by an order of magnitude. The last component is a pair of mixed-integer linear programming (MILP) formulations for efficient source inversion and optimal sampling. The contaminant source inversion problem involves determining the source of contamination given a small set of measurements. The source inversion formulation is able to handle discrete positive/negative measurements from manual grab samples taken at different sampling cycles. In addition, sensor/sample placement formulations are extended to determine the optimal locations for the next manual sampling cycle. This approach is enabled by a strategy that significantly reduces the size of the Merlion water quality model, giving rise to a much smaller MILP that is solvable in a real-time setting. The approach is demonstrated on a large-scale water network model with over 12,000 nodes while considering over 100 timesteps. The results show the approach is successful in finding the source of contamination remarkably quickly, requiring a small number of sampling cycles and a small number of sampling teams. These tools are being integrated and tested with a real-time response system.

We have proposed a method by which the topology of a network might be discovered through an algorithm like the distributed Bellman-Ford algorithm. We have explored the inner workings of two methods to automate power distribution network reconfiguration, the ILP Solver and the Heuristic Solver. We have seen how networks of different shapes can be translated into a flattened topology, which is necessary preprocessing to find a power assignment solution for a network. We have also seen some experimental results comparing the performance of the ILP Solver and the Heuristic Solver. The Heuristic Solver is a very fast, efficient algorithm to reconfigure power distribution, which is important in the case of an emergency. It performs consistently with near perfect results at a speed that is orders of magnitude quicker than the ILP Solver in almost all cases. In an application where a network is small and time is not an important constraint, the ILP Solver could possibly be preferable, but in any context where time is sensitive and near-perfect results are as acceptable as perfect results, the Heuristic Solver is much preferable. There is always room for improvement. Future tests should perhaps allow for non-integer capacity units, or loads that require other values than unit capacity. Optimizing each algorithm by rewriting them in C could give more optimized tests, though this may not be necessary to make judgments about implementing one or the other. There may be some ways to improve the Heuristic Solver, such as arranging the ordered_links in some way that could be more optimal. The algorithm could also be improved by taking advantage of the fact that once there are no more sources with capacity to provide any loads, the process of trying to assign loads to them for power supply can cease. Perhaps this method could be combined with other methods that do not presently account for load priorities or place as much value on fast execution.

Context: Unmanned Aerial Vehicles are being widely being used for various scientific and non-scientific purposes. This increases the need for effective and efficient path planning of Unmanned Aerial Vehicles.Two of the most commonly used methods are the A-star algorithm and Mixed Integer Linear Programming.Objectives: Conduct a simulation experiment to determine the performance of A-star algorithm and Mixed Integer Linear Programming for path planning of Unmanned Aerial Vehicle in a simulated environment.Further, evaluate A-star algorithm and Mixed Integer LinearProgramming based computational time and computational space to find out the efficiency. Finally, perform a comparative analysis of A star algorithm and Mixed Integer Linear Programming and analyse the results.Methods: To achieve the objectives, both the methods are studied extensively, and test scenarios were generated for simulation of Objectives: Conduct a simulation experiment to determine the performance of A-star algorithm and Mixed Integer Linear Programming for path planning of Unmanned Aerial Vehicle in a simulated environment.Further, evaluate A-star algorithm and Mixed Integer LinearProgramming based computational time and computational space to find out the efficiency. Finally, perform a comparative analysis of A star algorithm and Mixed Integer Linear Programming and analyse the results.Methods: To achieve the objectives, both the methods are studied extensively, and test scenarios were generated for simulation of Methods: To achieve the objectives, both the methods are studied extensively, and test scenarios were generated for simulation of these methods. These methods are then implemented on these test scenarios and the computational times for both the scenarios were observed.A hypothesis is proposed to analyse the results. A performance evaluation of these methods is done and they are compared for a better performance in the generated environment. Results: It is observed that the efficiency of A-star algorithm andMILP algorithm when no obstacles are considered is 3.005 and 12.03functions per second and when obstacles are encountered is 1.56 and10.59 functions per seconds. The results are statistically tested using hypothesis testing resulting in the inference that there is a significant difference between the computation time of A-star algorithm andMILP. Performance evaluation is done, using these results and the efficiency of algorithms in the generated environment is obtained.Conclusions: The experimental results are analysed, and the Conclusions: The experimental results are analysed, and the efficiencies of A-star algorithm and Mixed Integer Linear Programming for a particular environment is measured. The performance analysis of the algorithm provides us with a clear view as to which algorithm is better when used in a real-time scenario. It is observed that Mixed IntegerLinear Programming is significantly better than A-star algorithm.

Neste trabalho foi desenvolvido um modelo de programação linear inteira mista para localização das instalações da rede logística do biodiesel no Brasil, de forma a que se possa, com sua aplicação, avaliar o potencial de produção de oleaginosas no país, assim como identificar as zonas mais promissoras para a localização dos diversos elos da cadeia do biodiesel, a partir da demanda gerada pela mistura de um percentual de biodiesel ao diesel fóssil. O modelo incorpora quatro elos da cadeia produtiva (fase agrícola, extração de óleo, produção de biodiesel e pontos de demanda). Os parâmetros do modelo foram estimados com base em informações reais de mercado disponíveis (base de dezembro/2007). Obteve-se com a aplicação do modelo a diversos cenários, os municípios mais indicados para produção das oleaginosas, as oleaginosas utilizadas, o volume de produção em cada local e, por fim, a localização e porte das fábricas de óleo e das usinas de biodiesel. Análises de sensibilidade de alguns parâmetros foram executadas para verificação do comportamento do modelo face a incertezas. O trabalho incorpora sugestões e recomendações para aprimoramento do modelo. / In this research a mixed integer linear programming model was developed to locate facilities related to the biodiesel supply chain in Brazil, making possible to evaluate the oleaginous production potential, as well as the most promising regions to became the location of the several levels of the biodiesel chain, in accordance to the biodiesel future demand. The model incorporates four levels of the productive chain (agricultural phase, extraction of oil, biodiesel production and demand points). The model parameters were estimated based on market information available (base of december/2007). The application of the model to several sceneries led to the indication of the most promising regions for production of the oleaginous, the used oleaginous ones, the volume of production in each place and, finally, the location and scale of oil and biodiesel factories. Sensibility analyses were conducted to verify the results related to parameters uncertainty. The research contains suggestion and recommendations for improvement of the model.

Submitted by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2018-02-08T12:48:35Z No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Tese_Eduardo Bezerra Valetim.pdf: 1753904 bytes, checksum: b47b056ce4f5f67a30051e12c578323a (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2018-02-08T12:49:13Z (GMT) No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Tese_Eduardo Bezerra Valetim.pdf: 1753904 bytes, checksum: b47b056ce4f5f67a30051e12c578323a (MD5) / Made available in DSpace on 2018-02-08T12:49:13Z (GMT). No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Tese_Eduardo Bezerra Valetim.pdf: 1753904 bytes, checksum: b47b056ce4f5f67a30051e12c578323a (MD5) Previous issue date: 2017-09-29 / The power wall is a barrier to improvement in the processor design process due to the power consumption of components. The production of energy optimum systems demands knowledge of different disciplines. The usage of heterogeneous multicore platforms is appealing for recent applications, e.g., hard real-time systems. The motivation is the potential reduced energy consumption offered by such platforms. Hard real-time systems are present in life critical environments. Reducing the energy consumption on such systems is an onerous process. Scheduling becomes particularly challenging to improve system utilization and minimize system energy consumption and peak temperature on such platforms, specially subject to hard real-time constraints. Therefore, we propose a study to effectively answer the pertinent research question: “How to offer users timing correctness and guarantees of hard real-time systems executed on heterogeneous multicore systems with energy and temperature constraints?”. Finding optimal solutions for such question has still several open research questions. The main aim of this thesis is to propose an energy optimization method for hard realtime system on heterogeneous multicore platform demonstrating that it is possible to timely compute timing correctness and guarantees using a sufficient and necessary condition; accounting for energy, temperature, preemption, precedence, shared resources constraints, and architectural interference. The proposal is a two fold approach. First, we investigate the process of finding the optimal task to core and frequency to task processes by means of applying exact schedulability tests for heterogeneous multicore platforms. Second, the outcome of the optimization analysis shall be used as reference to the on-line scheduler. We believe that we have achieved the main objective of this research by combining: (a) schedulability analysis from hard real-time systems, (b) representative mathematical formulations, based on integer linear programming, covering modern processors technological characteristics and using a classical combinatorial mathematical formulation (Multilevel Generalized Assignment Problem), and (c) robust exact implicit enumeration algorithmic strategies from combinatorial optimization, such as branch-and-cut and branch-and-price. The systematic literature review in the research subject reveals that the field has open questions to be answered. For instance, to the knowledge of the author only five works in the state-of-the-art literature deal with the problem by providing optimal solutions. Typically, the existing approaches focus on either heuristics or approximation algorithms. Also, only one work has a proposal to evaluate the schedulability in this scenario with an exact test. The typical formulation in the specialized literature is a 0/1 integer linear programming model which considers a continuous processor frequency domain and determines a single operating frequency per processor. One of the hypotheses tested in this research is: stronger feasibility analysis offers tighter bounds for the problem. We believe that this can be observed, for example, in the results produced by solvers for fixed priority schedulers, by means of an analysis based on a comparative study. By applying less accurate schedulability tests, such as utilization based, the solvers take longer to converge to optimal solutions, when compared to solvers that apply exact schedulability tests based on response time analysis. Another hypothesis tested in this research is: practical instances of the problem are timely solvable to optimal. We have experimented, by means of a comparative study, on finding feasible solutions for workload for fixed priority schedulers with up to 50 tasks distributed on four processors with seven different available frequencies. On independent hard real-time tasks scheduled using EDF policy, we found optimal distribution of up to 90 tasks on four processors with seven different available frequencies. In both cases, the solutions were found within 30 min of execution time. Similarly, on dependent tasks workload, we have optimally distributed 22 tasks, from an automotive control hard real-time application, on four processors with seven different available frequencies, with two shared resources and 23 precedence constraints within 1.5 h. We consider a few hours in the design phase a price worth paying in this context. / .

As the "network of network", the Internet has been playing a central and crucial role in modern society, culture, knowledge, businesses and so on in a period of over two decades by supporting a wide variety of network technologies and applications. However, due to its popularity and multi-provider nature, the future development of the Internet is limited to simple incremental updates. To address this challenge, network virtualization has been propounded as a potential candidate to provide the essential basis for the future Internet architecture. Network virtualization is capable of providing an open and flexible networking environment in which service providers are allowed to dynamically compose multiple coexisting heterogeneous virtual networks on a shared substrate network. Such a flexible environment will foster the deployment of diversified services and applications. A major challenge in network virtualization area is the Virtual Network Embedding (VNE), which aims to statically or dynamically allocate virtual nodes and virtual links on substrate resources, physical nodes and paths. Making effective use of substrate resources requires high-efficient and survivable VNE techniques. The main contribution of this thesis is two high-performance p-Cycle-based survivable virtual network embedding approaches. These approaches take advantage of p-Cycle-based protection techniques that minimize the backup resources while providing a full VN protection scheme against link and node failures.

The Course Timetabling Problem is a widely studied optimization problem where a number of sections are scheduled in concert with the assignment of students to sections in order to maximize the desirability of the resulting schedule for all stakeholders. This problem is commonly solved as a linear program with variables for each student or group of students with identical schedules. In this paper we explore an alternative formulation that aggregates binary student variables into integer variables denoting the number of students enrolled in a course. Our solution method assumes decomposition of the general schedule into time blocks, and applies a unique set theory based, integer linear programming formulation that seeks to maximize the total number of students enrolled in their desired sections across the time blocks. Once the problem has been solved, the simpler problem of disaggregating the solution is resolved. This approach can be used to find exact solutions, given sufficient computing power, or simplified to quickly find solutions within calculable bounds of optimality. Case studies with a local elementary school and a local high school show that the new formulation is significantly faster and can be made to be reasonably accurate.

Steelmaking industry, one of the most electricity-intensive industrial processes, is seeking for new approaches to improve its competitiveness in terms of energy savings by taking advantage of the volatile electricity prices. This fluctuation in the price is mainly caused by the increasing share of renewable energy sources, the liberalization of energy markets and the growing demand of the energy. Therefore, making the production scheduling of steelmaking processes with knowledge about the cost of the energy may lead to significant cost savings in the electricity bills. With this aim in mind, different models are developed in this project in order to improve the existing monolithic models (continuous-time based scheduling) to find an efficient formulation of accounting for electricity consumption and also to expand them with more detailed scheduling of Electric Arc Furnace stage in the production process. The optimization of the energy cost with multiple electricity sources and contracts and the production planning are usually done as stand-alone optimizers due to their complexity, therefore as a new approach in addition to the monolithic model an iterative framework is developed in this work. The idea to integrate the two models in an iterative manner has potential to be useful in the industry due to low effort for reformulation of existing models. The implemented framework uses multiparametric programming together with bilevel programming in order to direct the schedule to find a compromise between the production constraints and goals, and the energy cost. To ensure applicability heuristic approaches are also examined whenever full sized models are not meeting computational performance requirements. The results show that the monolithic model implemented has a considerable advantage in terms of computational time compared to the models in the literature and in some cases, the solution can be obtained in a few minutes instead of hours. In the contrary, the iterative framework shows a bad performance in terms of computational time when dealing with real world instances. For that matter a heuristic approach, which is easy to implement, is investigated based on coordination theory and the results show that it has a potential since it provides solutions close to the optimal solutions in a reasonable amount of time. Multiparametric programming is the main core of the iterative framework developed in this internship and it is not able to give the solutions for real world instances due to computational time limitations. This computational problem is related to the nature of the algorithm behind mixed integer multiparametric programming and its ability to handle the binary variables. Therefore, further work to this project is to develop new approaches to approximate multiparametric technique or develop some heuristics to approximate the mp-MILP solutions.

Dans cette thèse, nous étudions des Hoist Scheduling Problems (HSP) qui se posent fréquemment dans des lignes automatiques de traitement de surface. Dans ces lignes, des ponts roulants sont utilisés pour transporter les pièces entre les bains. Ainsi, les ponts roulants jouent un rôle essentiel dans la performance de ces lignes ; et un ordonnancement optimal de leurs mouvements est un facteur déterminant pour garantir la qualité des produits et maximiser la productivité. Les lignes que nous étudions comportent un seul pont roulant mais peuvent être des lignes de base ou des lignes étendues (où des bains sont à fonctions et/ou capacités multiples). Nous examinons trois Hoist Scheduling Problems : l’optimisation robuste d’un HSP cyclique, l’ordonnancement dynamique d’une ligne étendue de type job shop et l’ordonnancement cyclique d’une telle ligne.Pour l’optimisation robuste d’un HSP cyclique, nous définissons la robustesse comme la marge dans le temps de déplacement du pont roulant. Nous formulons le problème en programmation linéaire en nombres mixtes à deux objectifs pour optimiser simultanément le temps de cycle et la robustesse. Nous démontrons que le temps de cycle minimal augmente avec la robustesse, et que par conséquent la frontière Pareto est constituée d’une infinité de solutions. Les valeurs minimales et maximales des deux objectifs sont établies. Les résultats expérimentaux à partir de benchmarks et d’instances générées aléatoirement montrent l’efficacité de l’approche proposée.Nous étudions ensuite un problème d’ordonnancement dynamique dans une ligne étendue de type job shop. Nous mettons en évidence une erreur de formulation dans une un modèle existant pour un problème similaire mais sans bains multi-fonctions. Cette erreur peut rendre l’ordonnancement obtenu sous-optimal voire irréalisable. Nous construisons un nouveau modèle qui corrige cette erreur. De plus il est plus compact et s’applique au cas avec des bains à la fois à capacités et à fonctions multiples. Les résultats expérimentaux menés sur des instances avec ou sans bains multi-fonctions montrent que le modèle proposé conduit toujours à une solution optimale et plus efficace que le modèle existant.Nous nous focalisons enfin sur l’ordonnancement cyclique d’une ligne étendue de type job shop avec des bains à fonctions et capacités multiples. Nous construisons un modèle mathématique en formulant les contraintes de capacité du pont roulant, les intervalles des durées opératoires, et les contraintes de capacité des bains. Nous établissons également des contraintes valides. Les expériences réalisées sur des instances générées aléatoirement montrent l’efficacité du modèle proposé. / This thesis studies hoist scheduling problems (HSPs) arising in automated electroplating lines. In such lines, hoists are often used for material handing between tanks. These hoists play a crucial role in the performance of the lines and an optimal schedule of the hoist operations is a key factor in guaranteeing product quality and maximizing productivity. We focus on extended lines (i.e. with multi-function and/or multi-capacity tanks) with a single hoist. This research investigates three hoist scheduling problems: robust optimization for cyclic HSP, dynamic jobshop HSP in extended lines and cyclic jobshop HSP in extended lines.We first study the robust optimization for a cyclic HSP. The robustness of a cyclic hoist schedule is defined in terms of the free slacks in hoist traveling times. A bi-objective mixed-integer linear programming (MILP) model is developed to optimize the cycle time and the robustness simultaneously. It is proved that the optimal cycle time strictly increases with the robustness, thus there is an infinite number of Pareto optimal solutions. We established lower and upper bounds of these two objectives. Computational results on several benchmark instances and randomly generated instances indicate that the proposed approach can effectively solve the problem.We then examine a dynamic jobshop HSP with multifunction and multi-capacity tanks. We demonstrate that an existing model for a similar problem can lead to suboptimality. To deal with this issue, a new MILP model is developed to generate an optimal reschedule. It can handle the case where a multi-function tank is also multi-capacity. Computational results on instances with and without multifunction tanks indicate that the proposed model always yields optimal solutions, and is more compact and effective than the existing one.Finally, we investigate a cyclic jobshop HSP with multifunction and multi-capacity tanks. An MILP model is developed for the problem. The key issue is to formulate the time-window constraints and the tank capacity constraints. We adapt the formulation of time-window constraints for a simpler cyclic HSP to the jobshop case. The tank capacity constraints are handled by dealing with the relationships between hoist moves so that there is always an empty processing slot for new parts. Computational experiments on numerical examples and randomly generated instances indicate that the proposed model can effectively solve the problem.