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.

Development drilling is used in underground mining to create access tunnels. A common method involves using a drilling rig, known as a jumbo, to drill holes into the face of a tunnel. Jumbo drill rigs have two or more articulated arms with drills as end-effectors, that extend outwards from a vehicle. Once drilled, the holes are charged with explosives and fired to advance the tunnel. There is an ongoing imperative within the mining industry to reduce development times and reducing time spent drilling is seen as the best opportunity for achieving this. Notwithstanding that three-boom jumbos have been available for some years, the industry has maintained a preference for using jumbo rigs with two drilling booms. Three-boom machines have the potential to reduce drilling time by as much as one third, but they have proven difficult to operate and, in practice, this benefit has not been realized. The key difficulty lies in manoeuvering the booms within the tight confines of the tunnel and ensuring sequencing the drilling of holes so that each boom spends maximum time drilling. This thesis addresses the problem of optimally sequencing multi-boom jumbo drill rigs to minimize the overall time to drill a blast hole pattern, taking into account the various constraints on the problem including the geometric constraints restricting motion of the booms. The specific aims of the thesis are to: ² develop the algorithmic machinery needed to determine minimum- or near-minimum-time drill assignment for multi-boom jumbos which is suitable for "real-time" implementation; ² use this drill pattern assignment algorithm to quantify the benefits of optimal drill pattern assignment with three-boom jumbos; and ² investigate the management of unplanned events, such as boom breakdowns, and assess the potential of the algorithm to assist a human operator with the forward planning of drill-hole selection. Jumbo drill task assignment is a combinatorial optimization problem. A methodology based around receding horizon mixed integer programming is developed to solve the problem. At any time the set of drill-holes available to a boom is restricted by the location of the other booms as well as the tunnel perimeter. Importantly these constraints change as the problem evolves. The methodology builds these constraints into problem through use of a feasibility tensor that encodes the moves available to each boom given configurations of other booms. The feasibility tensor is constructed off-line using a rapidly exploring random tree algorithm. Simulations conducted using the sequencing algorithm predict, for a standard drill-hole pattern, a 10 - 22% reduction in drilling time with the three-boom rig relative to two-boom machines. The algorithms developed in this thesis have two intended applications. The first is for automated jumbo drill rigs where the capability to plan drilling sequences algorithmically is a prerequisite. Automated drill rigs are still some years from being a reality. The second, and more immediate application is in providing decision support for drill rig operators. It is envisaged that the algorithms described here might form the basis of a operator assist that provides guidance on which holes to drill next with each boom, adapting this plan as circumstances change.

This work integrates perennial feedstock yield modeling using climate model data from current and future climate scenarios, land use datasets, transportation network data sets, Geographic Information Systems (GIS) tools, and Mixed integer linear programming (MILP) optimization models to examine biorefinery network designs in the southeastern United States from an overall systems perspective. Both deterministic and stochastic cases are modeled. Findings indicate that the high transportation costs incurred by biorefinery networks resulting from the need to transport harvested biomass from harvest location to processing facilities can be mitigated by performing initial processing steps in small scale mobile units at the cost of increased unit production costs associated with operating at smaller scales. Indeed, it can be financially advantageous to move the processing units instead of the harvested biomass, particularly when considering a 10-year planning period (typical switchgrass stand life). In this case, the mobile processing supply chain configuration provides added flexibility to respond to year-to-year variation in the geographic distribution of switchgrass yields. In order to capture the effects of variation in switchgrass yields and incorporate it in optimization models, yield modeling was conducted for both current and future climate scenarios. (In general profits are lower in future climate scenarios). Thus, both the effects of annual variation in weather patterns and varying climate scenarios on optimization model decisions can be observed.

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.

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.

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.

Das Ziel dieses Projektes ist, die bestehende tägliche Produktionsablaufplanung in der Handgalvanik bei dem Lohngalvanikbetrieb C. Jentner GmbH mit Hilfe eines mathematischen Modells zu optimie-ren. Hierfür wurde das Flexible-Job-Shop-Modell von Ziaee ([1], S. 91-95) ausgewählt und auf die Gegebenheiten vor Ort angepasst. Es gehört zu den MILP-Problemen (mixed integer linear programming- gemischt ganzzahlige Programmierung). Bei der Verwendung des Modells für die Praxis stellt die Modellgröße, die benötigt wird, um die Vorgänge in der Produktion ausreichend abbilden zu können, ein Problem dar. Diese führt zu langen Lösungszeiten, die für den täglichen Einsatz in der Produktionsablaufplanung ungeeignet sind. Zur Lösung dieses Problems wurde ein problemspezifisches Verfahren basierend auf Aggregations- und Dekompositionstechniken entwickelt. Durch Anwendung dieses Verfahrens kann die Problemgröße für den Solver klein und so die Lösungszeit in einem für die tägliche Produktionsablaufplanung annehmbaren Rahmen gehalten werden.

With a fast-growing electricity demand and a larger proportion of intermittent energy sources follows a greater need for flexible and balancing sources of electricity, such as hydropower. Planning of hydropower production is considered to be a difficult problem to solve due to several nonlinearities, combinatorial properties and the fact that it is a large scale system with spatial-temporal coupling. Optimization approaches are used for solving such problems and a common simplification is to disregard the effect of head variation on the power output. This thesis presents two methods for modeling the head dependency in optimization models for hydropower river systems, the Triangulation method and the Bilinear method. The Triangulation method implements a three-dimensional interpolation technique called triangulation, using a MILP formulation. This is a commonly used method found in the literature. The Bilinear method is a novel approach that applies a piecewise bilinear approximation of the power production function, resulting in a BLP problem. Also, a strategy for selecting which hydropower stations to include head dependence for is provided. The performance of the methods was evaluated on authentic test cases from Lule River and compared to results obtained by Vattenfall's current model without head dependency. The Triangulation method and the Bilinear method give higher accuracy, and are therefore considered more realistic, than the current model. Further, the results indicate that it is sufficient to include head dependence for a subset of stations since the error is significantly reduced. Mid- to long-term scenarios were solved with high accuracy when a subset of the stations was modeled as head dependent. Overall, the Bilinear method had a significantly shorter computational time than the Triangulation method.