No description available.

No description available.

The rapid technological advancement in the past century resulted in a decreased life cycle of a large number of products and, consequently, increased the rate of technological obsolescence. The disposal of obsolete products has resulted in rapid landfilling and now poses a major environmental threat. The governments in many countries around the world have started imposing regulations to curb uncontrolled product disposal. The consumers, too, are now aware of adverse effects of product disposal on environment and increasingly favor environmentally benign products. In the wake of imminent stringent government regulations and the consumer awareness about ecosystem-friendly products, the manufacturers need to think about the alternatives to product disposal. One way to deal with this problem is to disassemble an obsolete product and utilize some of its components/subassemblies in the manufacturing of new products. This seems to be a promising solution because products now-a-days are made in accordance with the highest quality standards and, although an obsolete product may not be in the required functional state as a whole, it is possible that several of its components or subassemblies are still in near perfect condition. However, product disassembly is a complex task requiring human labor as well as automated processes and, consequently, a huge amount of monetary investment. This research addresses a disassembly optimization problem, which aims at minimizing the costs associated with the disassembly process (namely, the costs of breaking the joints and the sequence dependent set-up cost associated with disassembly operations), while maximizing the benefits resulting from recovery of components/subassemblies from a product. We provide a mathematical abstraction of the disassembly optimization problem in the form of integer-programming models. One of our formulations includes a new way of modeling the subtour elimination constraints (SECs), which are usually encountered in the well-known traveling salesman problems. Based on these SECs, a new valid formulation for asymmetric traveling salesman problem (ATSP) was developed. The ATSP formulation was further extended to obtain a valid formulation for the precedence constrained ATSP. A detailed experimentation was conducted to compare the performance of the proposed formulations with that of other well-known formulations discussed in the literature. Our results indicate that in comparison to other well-known formulations, the proposed formulations are quite promising in terms of the LP relaxation bounds obtained and the number of branch and bound nodes explored to reach an optimal integer solution. These new formulations along with the results of experimentation are presented in Appendix A. To solve the disassembly optimization problem, a three-phase iterative solution procedure was developed that can determine optimal or near optimal disassembly plans for complex assemblies. The first phase helps in obtaining an upper bound on our maximization problem through an application of a Lagrangian relaxation scheme. The second phase helps to further improve this bound through addition of a few valid inequalities in our models. In the third phase, we fix some of our decision variables based on the solutions obtained in the iterations of phases 1 and 2 and then implement a branch and bound scheme to obtain the final solution. We test our procedure on several randomly generated data sets and identify the factors that render a problem to be computationally difficult. Also, we establish the practical usefulness of our approach through case studies on the disassembly of a computer processor and a laser printer. / Master of Science

The design of water distribution systems has received a great deal of attention in the last three decades because of its importance to industrial growth and its crucial role in society for community health, firefighting capability, and quality of life. The cost of installing a water distribution system is typically in the tens of millions of dollars. These systems also account for the largest costs in the municipal maintenance budgets. Furthermore, existing systems are being burdened by increasing urban development and water use. All these factors cause the pipe sizing decisions to be a critical task in designing a cost effective water distribution system that is capable of handling the demand and satisfying the minimum pressure head and hydraulic redundancy requirements. A number of research efforts have focused on the least cost pipe sizing decision, each of them generating improved solutions for several standard test problems from literature, but so far, very little work has been done to test the quality of these solutions. In this thesis, two lower bounding schemes are proposed to evaluate the quality of these solutions. These lower bounding schemes make use of the special concave-convex nature of the nonlinear frictional loss terms. We show that the first is a dual to <i>Eiger et al.’s</i> [1994] bounding procedure while the second method produces far tighter lower bounds with comparable ease. Results on applying these lower bounding schemes to some standard test problems from literature are presented. The second lower bounding scheme is then embedded in a branch-and-bound procedure along with an upper bounding scheme by suitably restricting the flows at each node of the search tree. By branching successively, we attempt to narrow the gap from optimality to generate near optimal solutions to the least cost pipe sizing problem. This results in a comprehensive reduced cost network design that satisfies all pressure and flow requirements for realistically sized problems. The proposed method is applied to standard test problems from the literature. It is hoped that this method will provide a useful tool for city engineers to design a cost effective water distribution system that meets specified hydraulic requirements. / Master of Science

O sequenciamento e a programação da produção trazem grandes benefícios financeiros às empresas se realizados de forma adequada. Atualmente, soluções generalizadas apresentam resultados aceitáveis, porém têm como consequência benefícios inferiores quando comparados a estudos específicos. O ramo da otimização de resultados possui dois tipos de soluções: as exatas para problemas de menores dimensões e não exatas, ou heurísticas, para problemas de médias e grandes dimensões. Este trabalho apresenta algoritmos exatos do tipo Branch & Bound e Modelos de Programação Linear Inteira Mista para solucionar quatro variações de problemas de scheduling: Fm|block|&sum;Cjm, Fm|block|&sum;Tj, Fm|block, Sijk|&sum;Cjm e Fm|block, Sijk|&sum;Tj. As abordagens utilizadas são inéditas na literatura e apresentaram resultados animadores para a maioria dos cenários. O limitante para o tempo total de fluxo obteve resposta ótima em 100% dos casos para problemas de até 20 tarefas e 4 máquinas em menos de uma hora. Para o tempo total de atraso, o limitante se mostrou mais eficiente quando os valores das due dates apresentam alta taxa de dispersão. Para os casos com setup, foram elaboradas três variações de limitantes para cada problema. O limitante com setup que apresentou o melhor desempenho foi o que obteve a melhor relação entre o seu valor numérico e seu custo computacional. Os modelos MILP solucionaram 100% dos problemas sem setup para até 20 tarefas e 4 máquinas e para os casos com setup, foram solucionados problemas de até 14 tarefas e 4 máquinas no tempo limite de uma hora. Os testes computacionais mostram a eficiência na redução do número de nós e, consequentemente, no tempo de execução. Portanto, o estudo realizado indica que, para problemas de pequeno porte e médio, os métodos em questão possuem grande potencial para aplicações práticas. / Job Sequence and Programming give benefits both financial and organizational to any company when performed properly. Nowadays, there is still a gap between theory and practice due to solutions that are short in specification. The analyzed problems differ in type and dimension thus modifying its complexity. The results optimization field is divided into two types of solution: the exact solution for minor problems and the non-exact solution for greater dimension problems. The present paper presents exact algorithms to solve the problems Fm|block|&sum;Cjm, Fm|block|&sum;Tj, Fm|block, Sijk|&sum;Cjm by the Branch & Bounds and Mixed Integer Linear Program models. The approaches are new and presented good results for most cases. Bounds for the no-setup total flow time scenario solved 100% of the 20 jobs and 4 machines cases. High dispersion range due dates contributed for the effectiveness of the no-setup total tardiness bound\'s effectiveness. Three different approaches were developed for the setup cases. The best approach aimed to optimize the value/effort factor for the B&B. The Mixed Integer Linear Program models solved 100% of the no-setup cases for 20 jobs and 4 machines. The MILPs setup cases solved optimally 14 jobs and 4 machines cases. Computational tests were executed and analyzed and they highlighted the node count reduction and, consequently, the execution time. The present study points out that the exact methods can be applied to small and medium scheduling problems in practice.

O problema do sequenciamento da produção diz respeito à alocação das tarefas nas máquinas em um ambiente de fabricação, o qual vem sendo amplamente estudado. O sequenciamento pode variar em tamanho e complexidade dependendo do tipo de ambiente onde ele é aplicado, do número e tipos de restrições tecnológicas e da função objetivo do problema. A utilização de métodos de decisão para a solução de problemas de sequenciamento na indústria depende de modelos que sejam capazes de oferecer soluções para os problemas reais, que geralmente envolvem diversas restrições, os quais devem ser considerados simultaneamente. No presente trabalho o problema de sequenciamento da produção em ambientes flow shop permutacionais, com bloqueio com buffer zero, e com tempos de setup dependente da sequência e da máquina, com o objetivo de minimização do makespan é estudado, sendo este considerado um problema NP-Completo. O problema é pouco explorado na literatura. No presente trabalho é apresentado um procedimento de cálculo para o makespan e três métodos de solução para o problema: quatro limitantes inferiores para o procedimento Branch-and-Bound; quatro modelos MILP, sendo dois deles adaptados; e 28 modelos heurísticos construtivos adaptados para o problema. Os métodos desenvolvidos baseiam-se em propriedades matemáticas do problema que são apresentadas neste trabalho como limitante inferior e limitante superior. Dentre todos os modelos MILP, o modelo adaptado RBZBS1 obteve os melhores resultados para os problemas menores e o modelo desenvolvido TNZBS1 obteve os melhores desvios relativos médios do makespan para os problemas maiores, que não foram resolvidos dentro do limite de tempo computacional estipulado. O limitante inferior para o Branch-and-Bound LBTN2 foi melhor que os demais tanto no tempo computacional e no número de nós explorados como também no número de problemas não resolvidos e no desvio relativo médio do makespan. Foi realizado uma comparação entre o melhor modelo MILP e o melhor limitante inferior para o Branch-and-Bound, sendo que o último obteve melhores resultados para os problemas testados. Entre os métodos heurísticos adaptados, o PF foi o que obteve, de uma forma geral, os melhores resultados em todas as fases. / Production scheduling is defined as a problem of allocating jobs in machines in a production environment and it has been largely studied. The scheduling can vary in difficulty and complexity depending on the environment, the variety and types of technological restraints and the objective function of the problem. The use of decision making methods to solve scheduling problems in the industry needs models that are capable to solve real problems, that usually involve a big variety of restraints that have to be simultaneously studied. At the present work the scheduling problem in a permutational flow shop environment, considering blocking with zero buffer, and sequence and machine dependent setup times, with the objective of minimizing makespan is studied, which is considered a NP-Complete problem and little explored in literature. The work presents a calculation procedure for the makespan and three solution methods for the problem: four lower bounds for the Branch-and-Bound procedure; four MILP models, two of which are adapted; and 28 constructive heuristic methods adapted to the problem. The methods developed are based on mathematical properties of the problem that are presented in this work as a lower bound and an upper bound. Among all the MILP models, the adapted model RBZBS1 was the one to obtain the best results for the smaller problems, and the developed model TNZBS1 obtained the smallest mean relative deviation of the makespan for the bigger problems that were not solved within the specified computational time limit. The lower bound for the Branch-and-Bound LBTN2 obtained smaller computational times and number of explored nodes as well as the number of unsolved problems and the mean relative deviation for the makespan than all other lower bounds. Also, a comparison among the best MILP model and the best lower bound for the Branch-and-Bound was performed, being that the last obtained better results for the tested problems. Among the adapted heuristic methods, the PF heuristic was the one that obtained, in general, the better results in all phases.

O problema do sequenciamento da produção diz respeito à alocação das tarefas nas máquinas em um ambiente de fabricação, o qual vem sendo amplamente estudado. O sequenciamento pode variar em tamanho e complexidade dependendo do tipo de ambiente onde ele é aplicado, do número e tipos de restrições tecnológicas e da função objetivo do problema. A utilização de métodos de decisão para a solução de problemas de sequenciamento na indústria depende de modelos que sejam capazes de oferecer soluções para os problemas reais, que geralmente envolvem diversas restrições, os quais devem ser considerados simultaneamente. No presente trabalho o problema de sequenciamento da produção em ambientes flow shop permutacionais, com bloqueio com buffer zero, e com tempos de setup dependente da sequência e da máquina, com o objetivo de minimização do makespan é estudado, sendo este considerado um problema NP-Completo. O problema é pouco explorado na literatura. No presente trabalho é apresentado um procedimento de cálculo para o makespan e três métodos de solução para o problema: quatro limitantes inferiores para o procedimento Branch-and-Bound; quatro modelos MILP, sendo dois deles adaptados; e 28 modelos heurísticos construtivos adaptados para o problema. Os métodos desenvolvidos baseiam-se em propriedades matemáticas do problema que são apresentadas neste trabalho como limitante inferior e limitante superior. Dentre todos os modelos MILP, o modelo adaptado RBZBS1 obteve os melhores resultados para os problemas menores e o modelo desenvolvido TNZBS1 obteve os melhores desvios relativos médios do makespan para os problemas maiores, que não foram resolvidos dentro do limite de tempo computacional estipulado. O limitante inferior para o Branch-and-Bound LBTN2 foi melhor que os demais tanto no tempo computacional e no número de nós explorados como também no número de problemas não resolvidos e no desvio relativo médio do makespan. Foi realizado uma comparação entre o melhor modelo MILP e o melhor limitante inferior para o Branch-and-Bound, sendo que o último obteve melhores resultados para os problemas testados. Entre os métodos heurísticos adaptados, o PF foi o que obteve, de uma forma geral, os melhores resultados em todas as fases. / Production scheduling is defined as a problem of allocating jobs in machines in a production environment and it has been largely studied. The scheduling can vary in difficulty and complexity depending on the environment, the variety and types of technological restraints and the objective function of the problem. The use of decision making methods to solve scheduling problems in the industry needs models that are capable to solve real problems, that usually involve a big variety of restraints that have to be simultaneously studied. At the present work the scheduling problem in a permutational flow shop environment, considering blocking with zero buffer, and sequence and machine dependent setup times, with the objective of minimizing makespan is studied, which is considered a NP-Complete problem and little explored in literature. The work presents a calculation procedure for the makespan and three solution methods for the problem: four lower bounds for the Branch-and-Bound procedure; four MILP models, two of which are adapted; and 28 constructive heuristic methods adapted to the problem. The methods developed are based on mathematical properties of the problem that are presented in this work as a lower bound and an upper bound. Among all the MILP models, the adapted model RBZBS1 was the one to obtain the best results for the smaller problems, and the developed model TNZBS1 obtained the smallest mean relative deviation of the makespan for the bigger problems that were not solved within the specified computational time limit. The lower bound for the Branch-and-Bound LBTN2 obtained smaller computational times and number of explored nodes as well as the number of unsolved problems and the mean relative deviation for the makespan than all other lower bounds. Also, a comparison among the best MILP model and the best lower bound for the Branch-and-Bound was performed, being that the last obtained better results for the tested problems. Among the adapted heuristic methods, the PF heuristic was the one that obtained, in general, the better results in all phases.

L’industrie forestière est un secteur qui, même s’il est en déclin, se trouve au cœur du débat sur la mondialisation et le développement durable. Pour de nombreux pays tels que le Canada, la Suède et le Chili, les objectifs sont de maintenir un secteur florissant sans nuire à l’environnement et en réalisant le caractère fini des ressources. Il devient important d’être compétitif et d’exploiter de manière efficace les territoires forestiers, de la récolte jusqu’à la fabrication des produits aux usines, en passant par le transport, dont les coûts augmentent rapidement. L’objectif de ce mémoire est de développer un modèle de planification tactique/opérationnelle qui permet d’ordonnancer les activités pour une année de récolte de façon à satisfaire les demandes des usines, sans perdre de vue le transport des quantités récoltées et la gestion des inventaires en usine. L’année se divise en 26 périodes de deux semaines. Nous cherchons à obtenir les horaires et l’affectation des équipes de récolte aux blocs de coupe pour une année. Le modèle mathématique développé est un problème linéaire mixte en nombres entiers dont la structure est basée sur chaque étape de la chaine d’approvisionnement forestière. Nous choisissons de le résoudre par une méthode exacte, le branch-and-bound. Nous avons pu évaluer combien la résolution directe de notre problème de planification était difficile pour les instances avec un grand nombre de périodes. Cependant l’approche des horizons roulants s’est avérée fructueuse. Grâce à elle en une journée, il est possible de planifier les activités de récolte des blocs pour l’année entière (26 périodes). / Forest industry is a sector located at the heart of the debate on globalisation and sustainable development, even if it is in decline. For many countries like Canada, Sweden and Chile, the objectives are to maintain a flourishing sector without damaging the environment and to realize the finite nature of resources. It is important to be competitive and to operate effectively on forest territories, from harvesting to manufacturing products, through transport, in a context where costs increase rapidly. This master’s thesis is developing a tactical operational planning model to organize activities for a year to meet requests for factories, without losing sight of the transport of harvested quantities and inventory management factory. The year is divided into 26 periods of two weeks. We seek harvest teams schedules and assignment to harvest areas (units) for a year. The problem is formulated as a mixed integer programming model, whose structure is based on each stage of the forest supply chain. We choose to solve it by an exact method, branch-and-bound. We were able to assess how the direct resolution of our planning problem was difficult for instances with a large number of periods. However the rolling horizon approach has proved successful. In a day, we obtained the harvest activities planning for 26 periods.

Dans ces travaux, nous présentons des méthodes d'optimisation théoriques et numériques pour la conception optimale de circuits magnétiques pour propulseurs à effet Hall. Ces problèmes de conception sont des problèmes inverses très difficiles à résoudre que nous formulons sous forme de problèmes d'optimisation topologique. Les problèmes resultant sont non convexes avec des contraintes aux équations différentielles de Maxwell. Au cours de ces travaux, des approches originales ont été proposées afin de résoudre efficacement ces problèmes d'optimisation topologique. L'approche de densité de matériaux SIMP (Solid Isotropic Material with Penalization) qui est une variante de la méthode d'homogénéisation a été privilégiées. De plus, les travaux de ma thèse ont permis la mise en place de codes d'optimisation dénommé ATOP (Algorithm To Optimize Propulsion) utilisant en parallèle les logiciels de calculs scientifiques Matlab et d'élément finis FEMM (Finite Element Method Magnetics). Dans ATOP, nous utilisant à la fois des algorithmes d'optimisation locale de type descente basés sur une analyse de la sensibilité du problème et des algorithmes d'optimisation globale principalement de type Branch and Bound basés sur l'Arithmétique des Intervals. ATOP permettra d'optimiser à la fois la forme topologique des circuits magnétiques mais aussi le temps et le coût de production de nouvelles génération de propulseurs électriques. / In this work, we present theoretical and numerical optimization method for designing magnetic circuits for Hall effect thrusters. These design problems are very difficult inverse ones that we formulate under the form of topology optimization problems. Then, the obtained problems are non convex subject to Maxwell equations like constraints. Some original approaches have been proposed to solve efficiently these topology optimization problems. These approaches are based on the material density model called SIMP approach (Solid Isotropic Material with Penalization) which is a variante of the homogenization method. The results in my thesis allowed to provide optimization source code named ATOP (Algorithm To Optimize Propulsion) unsung in parallel two scientific computing softwares namely Matlab and FEMM (Finite Element Method Magnetics). In ATOP, we use both local optimization algorithms based on sensitivity analysis of the design problem; and global optimization algorithms mainly of type Branch and Bound based on Interval Arithmetic analysis. ATOP will help to optimize both the topological shape of the magnetic circuits and the time and cost of production (design process) of new generations of electrical thrusters.

CoordenaÃÃo de AperfeiÃoamento de Pessoal de NÃvel Superior / A utilizaÃÃo de vetores de bits à prÃtica corrente na representaÃÃo de conjuntos por endereÃamento direto com o intuito de reduzir o espaÃo de memÃria necessÃrio e melhorar o desempenho de aplicaÃÃes com uso de tÃcnicas de paralelismo em bits. Nesta dissertaÃÃo, examinamos implementaÃÃes para representaÃÃo de conjuntos por endereÃamento direto. A estrutura bÃsica nessas implementaÃÃes à o vetor de bits. No entanto, alÃm dessa estrutura bÃsica, implementamos tambÃm duas variaÃÃes. A primeira delas consiste em uma estratificaÃÃo de vetores de bits, enquanto a segunda emprega uma tabela de dispersÃo. As operaÃÃes associadas Ãs estruturas implementadas sÃo a inclusÃo ou remoÃÃo de um elemento do conjunto e a uniÃo ou interseÃÃo de dois conjuntos. Especial atenÃÃo à dada ao uso de paralelismo em bits nessas operaÃÃes. As implementaÃÃes das diferentes estruturas nesta dissertaÃÃo utilizam uma interface e uma implementaÃÃo abstrata comuns, nas quais as operaÃÃes sÃo especificadas e o paralelismo em bits à explorado. A diferenÃa entre as implementaÃÃes està apenas na estrutura utilizada. Uma comparaÃÃo experimental à realizada entre as diferentes estruturas utilizando algoritmos enumerativos para o problema de conjunto independente mÃximo. Duas abordagens sÃo utilizadas na implementaÃÃo de algoritmos enumerativos para o problema de conjunto independente mÃximo, ambas explorando o potencial de paralelismo em bits na representaÃÃo do grafo e na operaÃÃo sobre subconjuntos de vÃrtices. A primeira delas à um algoritmo do tipo {em branch-and-boound} proposto na literatura e a segunda emprega o mÃtodo das bonecas russas. Em ambos os casos, o uso de paralelismo em bits proporciona ganhos de eficiÃncia quando empregado no cÃlculo de limites inferiores baseados em cobertura por cliques. Resultados de experimentos computacionais sÃo apresentados como forma de comparaÃÃo entre os dois algoritmos e como forma de avaliaÃÃo das estruturas implementadas. Esses resultados permitem concluir que o algoritmo baseado no mÃtodo das bonecas russas à mais eficiente quanto ao tempo de execuÃÃo e quanto ao consumo de memÃria. AlÃm disso, os resultados experimentais mostram tambÃm que o uso de estratificaÃÃo e tabelas de dispersÃo permitem ainda maior eficiÃncia no caso de grafos com muito vÃrtices e poucas arestas. / The use of bit vectors is a usual practice for represent sets by direct addressing with the aim of reduce memory consumed and improve efficiency of applications with the use of bit parallel techniques. In this text, we study implementations for represent sets by direct addressed. The basic structure in this implementations is the bit vector. Besides that basic implementation, we implement two variations also. The first one is a stratification of the bit vector, while the second uses a hash table. The operations linked to the implemented structure are include and remove an element and the union and intersection of two sets. Especial attention is given to the use of bit parallel in this condition. The implementation of the different structures in this work use an base interface and a base abstract class, where the operations are defined and the bit parallel is used. An experimental comparative between this structures is carry out using enumerative algorithms for the maximum stable set problem. Two approaches are used in the implementation of the enumerative algorithms for the maximum stable set problem, both using the bit parallel in the representation of the graph and on the operations with subsets of vertices. The first one is a known branch-and-bound algorithm and the second uses the Russian dolls method. In both cases, the use of bit parallel improve efficiency when the lower bounds are calculated based in a clique cover of the vertices. The results of computational experiments are presented as comparison between the two algorithms and as an assessment of the structures implemented. These results show that the algorithm based on the method Russian Dolls is more efficient regarding runtime and the memory consumed. Furthermore, the experimental results also show that the use stratification and hash tables also allow more efficiency in the case of sparse graphs.