Submitted by Maykon Nascimento (maykon.albani@hotmail.com) on 2016-05-17T20:09:39Z No. of bitstreams: 2 license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Tese Leandro Colombi.pdf: 1600437 bytes, checksum: d40bc605230b5d5995a431dc205d03a6 (MD5) / Approved for entry into archive by Morgana Andrade (morgana.andrade@ufes.br) on 2016-06-03T14:24:51Z (GMT) No. of bitstreams: 2 license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Tese Leandro Colombi.pdf: 1600437 bytes, checksum: d40bc605230b5d5995a431dc205d03a6 (MD5) / Made available in DSpace on 2016-06-03T14:24:51Z (GMT). No. of bitstreams: 2 license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Tese Leandro Colombi.pdf: 1600437 bytes, checksum: d40bc605230b5d5995a431dc205d03a6 (MD5) / CNPQ / O Problema de Grooming de Tráfego (Traffic Grooming Problem - TGP) trata da combinação eficiente de demandas de baixa velocidade em canais de alta velocidade. Com o objetivo de melhorar a utilização da capacidade da rede, o TGP é frequentemente estudado com métodos de otimização usando como função objetivo a minimização do número de transceptores eletro-´ópticos. Por´em, como o TGP pertence á classe de problemas NP-Completo, soluções ótimas com um pequeno tempo computacional são possíveis apenas para redes pequenas (por exemplo, 6 nós). Neste trabalho são propostos novos modelos de Programação Linear Inteira (Integer Linear Programming - ILP), uma heurística e uma solução híbrida para o TGP em redes translúcidas de médio porte (aproximadamente 12 n´os). Inicialmente, são propostos dois modelos ILP para o TGP, um baseado em formulação nó-enlace e outro em enlace-caminho, de forma que seus resultados foram comparados e usados como base para modelos mais complexos. No método híbrido é usada uma heurística para selecionar os caminhos ópticos (i.e., a topologia virtual) e um modelo ILP para rotear de maneira eficiente as demandas de tráfego sobre as topologias física e virtual. A aplicação desse método permitiu, primeiramente, a quantificação dos benefícios dos caminhos ópticos transparentes, em termos da redução do número de transceptores. Além disso, a diminuição do processamento eletrônico do tráfego de trânsito também foi analisada. Para redes maiores, a fase ILP no método híbrido ainda continua sendo um gargalo para as soluções ótimas, sendo assim necessárias soluções totalmente heurísticas. Este trabalho mostra que soluções eficientes podem ser encontradas usando métodos heurísticos simples e rápidos, onde não foi necessário o aumento do custo computacional para o ajuste de parâmetros complexos relacionados a heurística. Finalmente é proposta uma integração do TGP com sobrevivência. Neste trabalho são propostos modelos ILP para formulação de um método iterativo capaz de oferecer uma proteção incremental em uma rede em malha com a minimização do número de transceptores. Além disso, são estudados dois métodos para a proteção da interconexão de redes multi-anel com dois nós de interconexão, Anel Virtual e Drop&Continue. Para essa investigação os resultados numéricos incluem o grooming de tráfego para diferentes cenários como, configurações opaca vs. translúcida e crescimentos de tráfego inter-anel vs. intra-anel. / The Traffic Grooming Problem (TGP) consists in how to arrange low-bandwidth connection requests into high-capacity lightpaths efficiently. TGP solution aims at improving network capacity utilization. The minimal number optoelectronic transceivers that enable accommodating traffic demands is often used as the objec- tive function for solving TGP. However, TGP belongs to a class of NP-hard problems and optimal solutions are only possible to be found within feasible processing time for small networks (e.g., 6 nodes). This work proposes novel Integer Linear Pro- gramming (ILP) models, heuristic and a hybrid solution to TGP for medium-sized (i.e., around 12 nodes) translucent networks. Initially, ILP models using node-link and link-path paradigms are proposed and their solutions are compared. These models lay the foundations for more complex models addressing issues on network design. A hybrid method is then proposed. It makes use of a heuristic for selecting lightpaths (i.e., the virtual topology) and an ILP model to route the traffic demands over both physical and virtual topologies efficiently. The practical implications of such approach is that it allows, for the first time, the quantification of benefits of transparent lightpaths in terms of transceiver count reduction. Moreover, the miti-gation of transit traffic processing in the electronic layer is also analyzed. For large networks the ILP phase in the hybrid approach again becomes the bottleneck for optimal network design and a fully heuristic solution is necessary. This work shows that efficient solutions can be found through a simple and fast tool for network design without the need of complex parameter tuning, as comparisons with results obtained from solving the hybrid model. Finally, the integration of TGP with survivability is proposed. This work puts forward ILP models for an iterative method using two ILP models to design networks with incremental protection with minimal num- ber of transceivers in mesh networks. Dual Node Interconnected (DNI) multi-ring topologies are studied under inter-ring traffic protection using Virtual Ring (VR) and Drop and Continue (D&C) strategies. Results compare optimal solutions that take into account traffic grooming for different network scenarios including opaque vs. translucent configurations and inter vs. intra traffic growth.

Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro Tecnológico. Programa de Pós-Graduação em Engenharia de Automação e Sistemas / Made available in DSpace on 2013-06-25T19:15:09Z (GMT). No. of bitstreams: 1 309792.pdf: 1874704 bytes, checksum: 123c0407eefb86ff006b9c244028d7d8 (MD5) / O problema de alocação de gás de injeção com restrições de alinhamento poço-manifold e restrições de pressão no sistema de produção é um problema não linear inteiro-misto de dificuldade considerável. A complexidade deste problema reside na natureza das decisões discretas do alinhamento e nas não linearidades presentes nas curvas de produção dos poços e de queda de pressão nas tubulações. A abordagem de solução utilizada neste trabalho é a reformulação deste problema em programas lineares inteiros-mistos com o uso de ferramentas de linearização por partes para funções multidimensionais. Foram desenvolvidas sete reformulações lineares inteiras-mistas, considerando aproximações por hipercubos e por simplexes. Enquanto a aproximação por hipercubos é mais simples e possui menos variáveis, a aproximação por simplexes possui mais variáveis, mas é mais detalhada. Foi apresentada uma análise computacional destas formulações para um cenário modelado a partir de um sistema de produção sintético construído com uma ferramenta de escoamento multifásico. Para avaliar o desempenho das formulações desenvolvidas, foram considerados cenários com diferentes disponibilidades de gás no compressor e diferentes qualidades de aproximação. Os resultados da análise computacional mostraram que, para as aproximações por hipercubos, o modelo SOS2 teve melhor desempenho na maioria dos cenários. Para as aproximações por simplexes, o modelo Log teve o melhor desempenho dentre os modelos. Considerando ambas aproximações, para um cenário com qualidade de aproximação fina e com uma restrição mais apertada na disponibilidade de gás de injeção, apenas o modelo Log conseguiu obter a solução ótima para o problema. / The problem of allocating lift-gas to oil wells subject to well-manifold routing, and pressure constraints in the production system is a mixed-integer non-linear problem of considerable difficulty. The complexity of this problem rests on the nature of discrete decisions of the routing and the non linearities of the well production curves and pressure drops in the pipelines. The solution approach used in this work is the reformulation of this problem into mixed-integer linear programs with piecewise-linearization tools for multidimensional functions. Seven mixed-integer linear reformulations were developed with hypercube and simplex approximations. While the hypercube approximation is simpler and more compact, the simplex approximation has more variables, but is more accurate. A computational analysis of the application of these formulations to a synthetic production system represented in a multi-flow simulator is presented. In order to evaluate the performance of these formulations, instances with different availability of lift-gas in the compressor and different qualities of approximation were considered. The results of the computational analysis showed that the SOS2 model solved the problem faster in most instances of the hypercube approximation. With simplex approximations, the Log model was faster in all scenarios. Considering both approximations, when the quality of approximation is accurate and the lift-gas availability is low, only the Log model obtained the optimal solution.

Tese (Doutorado) - Universidade Federal de Santa Catarina, Centro Tecnológico. / Made available in DSpace on 2012-10-18T20:52:01Z (GMT). No. of bitstreams: 0Bitstream added on 2016-01-09T03:49:43Z : No. of bitstreams: 1 142984.pdf: 5015554 bytes, checksum: bcc15bb9ee8dc4d8d284c211d36ac53a (MD5)

In this paper we proposed 0-1 integer programming formulation to model single batch processing machine. This problem deals with a set of jobs with non-identical sizes and processing times that has to be grouped to form batches according to the limited capacity of the machine. The processing time of a batch is the longest processing time of all jobs in the batch. The performance measure is the total time required to process all jobs (makespan). The formulation presented strengthens the model, i.e., it is closer to the optimal formulation than those proposed in the literature. Computational experiments demonstrate that the model is consistent and adequately represents the problem addressed. / Neste trabalho é proposta uma formulação de programação inteira 0-1 para modelar o problema de programação e dimensionamento de lotes de produção em máquina única. Este problema considera um conjunto de tarefas com diferentes tamanhos e tempos de processamento que devem ser agrupadas em lotes de acordo com a capacidade limitada da máquina. O tempo de processamento de um lote é determinado pelo maior tempo de processamento dentre todas as tarefas que compõem o lote. A medida de desempenho é o tempo total necessário para processar todas as tarefas (makespan). A formulação apresentada é mais forte, ou seja, mais próxima da formulação ideal do que aquelas propostas na literatura. Experimentos computacionais demonstram que o modelo é consistente e representa adequadamente o problema tratado.

Made available in DSpace on 2015-09-17T15:26:00Z (GMT). No. of bitstreams: 0 Previous issue date: 2015-04-13. Added 1 bitstream(s) on 2015-09-17T15:46:16Z : No. of bitstreams: 1 000847503.pdf: 9295725 bytes, checksum: 35bd73628c5e5dd21ebe81497ef3e10d (MD5) / O aumento consistente e constante do consumo de energia elétrica, o crescimento irregular e desordenado de edificações residenciais, comerciais e industriais, dentro e fora dos centros urbanos, as irregularidades nas características do fator de potência das cargas instaladas, podem colocar em xeque o bom desempenho dos sistemas elétricos de distribuição sendo necessário e urgente, a aplicação de ferramentas computacionais eficientes que atuem na otimização da operação. A investigação, análise e projeto destes sistemas são o foco da automação da distribuição, que visa redução das perdas técnicas que pode ser feita através da reconfiguração e alocação de bancos de capacitores que contribuirão para o melhoramento nos perfis de tensão e a minimização de perda de potência ativa nas linhas. Este trabalho visa propor a melhoria no desempenho econômico da operação de sistemas de distribuição através da minimização de determinados custos da operação, propondo investimentos que garantam lucros em seu retorno, através da solução simultânea dos problemas de reconfiguração de sistemas de distribuição radiais para alguns tipos de carregamento e do problema da alocação dos bancos de capacitores que será feita através de urna metaheurística especializada para avaliar a qualidade de cada proposta de solução fornecida pela meta-heurística sendo implementado um módulo de fluxo de carga em sistemas de distribuição radial com uso de um algoritmo de varredura / The consistent and steady increase in electricity consumption, the irregular and uncontrol­ led growth of residential, commercial and industrial buildings, inside and outside urban centers, the irregularities in the characteristics of the power factor of the loads installed, can risk the good performance electrical distribution systems is necessary and urgent, the application of eflicient computational tools that work on optimizing the operation. The research, analysis and design of these systems is the focus of distribution automa­ tion, which aims to reduce technical losses can be clone by reconfiguring and allocation of capacitors which contribute to the improvement in the voltage profile and minimizing loss active power lines. This work aims to propose improvements in the economic perfor­ mance of the distribution system operation by minimizing certain costs of the operation, proposing investments to ensure profits on their return, by the simultaneous solution of the reconfiguration of radial distribution systems problems for some types of loading and allocation problem of capacitor banks to be made by a specialized metaheurist to assess the quality of each proposed solution provided by metarheuristics are implemented a load module radial flow distribution system using an algorithm scan

Orientador: Silvio Alexandre de Araujo / Banca: Helenice de Oliveira Florentino Silva / Banca: Maria do Socorro Nogueira Rangel / Resumo: Este trabalho trata do problema de corte de estoque unidimensional inteiro, que consiste em cortar um conjunto de objetos disponíveis em estoque para a produção de itens menores demandados, de tal forma que se otimize uma ou mais funções objetivos. Foi estudado o caso em que existe apenas um tipo de objeto em estoque em quantidades suficiente para atender a demanda. Três adaptações de um método heurístico baseadas nos conceitos dos algoritmos evolutivos multiobjetivo são propostas para resolver o problema considerando duas funções objetivo conflitantes, a minimização do número de objetos cortados e a minimização do número de diferentes padrões de corte. As adaptações utilizam as idéias presentes no método da Soma Ponderada, no Vector Evaluated Genetic Algorithm e no Multiple Objective Genetic Algorithm. Estas heurísticas são analisadas resolvendo-se instâncias geradas aleatoriamente. / Abstract: This work deals with the one-dimensional integer cutting stock problem, which consist of cutting a set of available objects in stock in order to produce ordered smaller items in such a way as to optimize one or more objective functions. On the case studied there is just one type of object in stock available in sufficient quantity to satisfy the demand. Three adaptations of a heuristic method based on the multi-objective evolutionary algorithms concepts are proposed to solve the problem considering two conflicting objective functions, the minimization of the number of objects to be cut and the minimization of the number of different cutting patterns. The adaptations consider the ideas from the Weighted Sum method, the Vector Evaluated Genetic Algorithm and the Multiple Objective Genetic Algorithm. These heuristics are analyzed by solving randomly generated instances. / Mestre

Made available in DSpace on 2016-06-02T19:51:30Z (GMT). No. of bitstreams: 1 DissJRDL.pdf: 648879 bytes, checksum: d0336140896c62906f4999d62e04668f (MD5) Previous issue date: 2003-01-01 / This work presents optimization models to support decisions of the Production Planning and Control (PPC) in the industry of grains electrocasting. A case study was accomplished in one of the largest companies in the State of São Paulo. The objective of the study is to contribute for the improvement of the system of PCP of companies of grains electrocasting, in such a way to obtain gains of productivity and to improve the user service level with respect to due date satisfaction. For that Mixed Integer Linear Programming models were applied to aid particularly in the decisions of production scheduling. Optimizing the production scheduling in the industry of grains electrocasting is not a simple task, mainly due to the greatness of setup times of the equipments, the diversity of products and the limitations of the order due dates. / Este trabalho apresenta modelos de otimização para apoiar decisões do Planejamento e Controle da Produção (PCP) na indústria de grãos eletrofundidos. Um estudo de caso foi realizado numa das maiores empresas do setor no estado de São Paulo. O objetivo do estudo é contribuir para a melhoria do sistema de PCP de empresas de grãos eletrofundidos, de maneira a obter ganhos de produtividade e melhorar o nível de serviço aos clientes no atendimento dos prazos de entrega. Para isso, foram aplicados modelos de Programação Linear Inteira Mista para auxiliar particularmente nas decisões da programação da produção, e analisar os resultados obtidos. Otimizar a programação da produção na indústria de grãos eletrofundidos não é uma tarefa simples, principalmente devido à grandeza dos tempos de preparação dos equipamentos, à diversidade de produtos e às limitações dos prazos de entrega.

O trabalho apresentado nesta dissertação é referente ao estudo da evacuação de pessoas, mais especificamente, a evacuação predial faseada. O objetivo é determinar, para instâncias de até 25 andares, os instantes de liberação de cada grupo de pessoas, a fim de minimizar o tempo total de evacuação do edifício. No entanto, a determinação destes instantes deve considerar o risco ao qual os diferentes grupos estão submetidos, priorizando a evacuação do andar afetado. Além disso, os conflitos de diferentes grupos por espaço nas rotas de evacuação também devem ser evitados, já que, são nessas situações que acontecem grande parte dos acidentes. Para atingir tal objetivo, foi elaborado um modelo matemático de programação linear inteira. Devido à alta complexidade do modelo, fez-se necessária a aplicação de métodos heurísticos para a obtenção de soluções. Dessa maneira, foram desenvolvidas uma heurística de busca baseada em GRASP e uma heurística lagrangeana. Apesar da heurística lagrangeana atestar a qualidade da solução (a partir da comparação do resultado obtido com o limitante inferior), a heurística de busca mostrou-se mais adequada para o problema, pois forneceu resultados de qualidade com pouco esforço computacional. / This dissertation studies the evacuation of people, more specifically, building phased evacuation. The objective of this study is to determine, for buildings of up to 25 floors, in which instants each group of people has to be released, in order to minimize the total evacuation time. Furthermore, the determination of these instants has to consider the risk to which each group of people is submitted, thus the affected floor has to be the first group to be released. In addition, conflicts for space between groups should be avoided, since such situations increase the occurrences of accidents. To achieve this goal, an integer linear programming model was designed. Due to the high complexity of the model, it was necessary to apply heuristics to obtain solutions for some instances. Therefore, a search heuristic based on GRASP and a lagrangian heuristic were developed. Despite the fact that the lagrangian heuristic attests to the quality of the solution (when it is compared to the lower bound), the search heuristic was considered more suitable for this problem because it provided quality results with lower computational efforts.

Orientador: Vinicius Amaral Armentano / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-10T01:09:54Z (GMT). No. of bitstreams: 1 Fonseca_SaraLuisadeAndrade_M.pdf: 1363535 bytes, checksum: aa7c01c779a21ea25aa3b603425c92fe (MD5) Previous issue date: 2007 / Resumo: Em 1958, Gomory propôs uma desigualdade válida ou corte a partir do tableau do método simplex para programação linear, que foi utilizado no primeiro método genérico para resolução de problemas de programação inteira. Em 1960, o corte foi estendido para problemas de programação inteira mista. Em 1973, Chvátal sugeriu um corte derivado da formulação original do problema de programação inteira, e devido à equivalência com o corte de Gomory, este passou a ser chamado de corte de Chvátal-Gomory. A importância do corte de Gomory só foi reconhecida em 1996 dentro do contexto do método branch-and-cut para resolução de problemas de programação inteira e programação inteira mista. Desde então, este corte é utilizado em resolvedores comerciais de otimização. Recentemente, diversos cortes novos derivados do corte de Chvátal-Gomory foram propostos na literatura para programação inteira. Este trabalho trata do desenvolvimento de algoritmos para alguns destes cortes, e implementação computacional em um contexto de branch-and-cut, no ambiente do resolvedor CPLEX. A eficácia dos cortes é testada em instâncias dos problemas da mochila multidimensional, designação generalizada e da biblioteca MIPLIB. / Abstract: In 1958, Gomory proposed a valid inequality or cut from the tableau of the simplex method for linear programming, which was used in the first generic method for solving integer programming problems. In 1960, the cut was extended to handle mixed integer programming problems. In 1973, Chvátal suggested a cut that is generated from the original formulation of an integer programming problem, and due to the equivalence with the Gomory cut, it was named Chvátal-Gomory cut. The importance of the Gomory cut was recognized only in 1996 in the context of the branch-and-cut method for solving (mixed) integer programming problems. Today, such a cut is utilized in optimization commercial solvers. Recently, several new cuts derived from the Chvátal-Gomory cut have been proposed in the literature for integer programming. This work deals with the development of algorithms and computational implementations for some of the new proposed cuts, in a context of the branch-and-cut method, by using the CPLEX solver. The efficiency of the cuts is tested on instances of the multi-dimensional knapsack, generalized assignment problems, and instances from the MIPLIB library. / Mestrado / Automação / Mestre em Engenharia Elétrica

Diversas pesquisas e estudos científicos mostram que uma grande porcentagem das pessoas com deficiência é excluída do mercado de trabalho, sobretudo em países em desenvolvimento. Com o intuito de alterar essa realidade, destacam-se, entre outras medidas, a criação de Centros de Trabalho para Deficientes (CTDs). Tais organizações empregam trabalhadores com deficiência em vários setores empresariais, dando-lhes oportunidades iniciais e preparando-os para que possam, mais tarde, ser inseridos no mercado de trabalho convencional. Vários destes centros operam linhas de produção, principal objeto de estudo desta tese. Nosso estudo é situado em uma etapa idealmente posterior aos CTDs, referente à inserção de trabalhadores com deficiência em linhas de produção convencionais. A demanda por estudos neste contexto tem crescido nos últimos anos, devido sobretudo a políticas corporativas de responsabilidade social e exigências legislativas, como a \"Lei das Cotas\", presentes em diversos países. O planejamento da operação de linhas de produção na presença de trabalhadores com deficiência envolve uma série de desafios, devido à heterogeneidade entre trabalhadores, que faz com que o tempo de execução das tarefas seja dependente de cada indivíduo. Nos deparamos, assim, com um problema de dupla alocação, em que as variáveis de decisão determinam as tarefas a serem inseridas em estações e a alocação de trabalhadores para as mesmas, de modo a otimizar alguma medida de eficiência. O balanceamento de linhas de produção convencionais com uma parcela de trabalhadores com deficiência é denominado problema de balanceamento de linhas de produção e integração de trabalhadores (ALWIBP, do inglês: assembly line worker integration and balancing problem), sendo um caso particular do problema de balanceamento de linhas de produção e designação de trabalhadores (ALWABP, do inglês: assembly line worker assignment and balancing problem), cuja ocorrência é mais comum em linhas de CTDs. Nosso objetivo consiste em estudar formas eficientes de proporcionar a integração de trabalhadores com deficiência em linhas convencionais. Para tanto, abordamos variações do ALWIBP que consideram: (i) minimização de diferentes funções objetivo (número de estações ou tempo de ciclo); (ii) linha de produção com leiautes distintos (simples ou em U); (iii) incertezas quanto ao tempo de execução de cada tarefa (abordagem robusta); (iv) estratégias de rotação de tarefas ou alocação de trabalhadores com deficiência na linha com espaçamento regular. Para cada uma destas extensões, foram desenvolvidos formulações matemáticas, métodos de resolução e novos conjuntos de instâncias teste. Experimentos computacionais indicam possibilidades de adaptação de linhas de produção convencionais à inserção de trabalhadores com deficiência, a custos adicionais baixos ou quase nulos. Portanto, este trabalho oferece alternativas para uma maior flexibilidade na integração de pessoas com deficiência, tornando-os tão eficientes quanto qualquer outro trabalhador denominado \"convencional\". / A number of studies show that a large percentage of disabled people are excluded from the labor market, in particular in developing countries. In order to deal with this problem, one can highlight the importance of Sheltered Work Centers for Disabled (SWDs). These organizations employ disabled workers in various corporate sectors, giving them initial opportunities and preparing them so that they can be later integrated into the conventional labor market. Many of these centers operate assembly lines, the main object of study of this thesis. Our study considers an ideally later stage of SWDs, related with the insertion of disabled workers in conventional assembly lines. The demand for studies in this field has grown over the years, due to corporate social responsibility policies and legal requirements such as \"quotas legislations\", present in many countries. Planning the operation of assembly lines with disabled workers involves a series of challenges due to the heterogeneity among workers, which are reflected in task times being worker dependent. This results in a double allocation problem, where decisions must determine both the tasks and the workers to be assigned to the stations, in order to optimize some efficiency measure. The conventional assembly line balancing with a parcel of disabled workers is known as the assembly line worker integration and balancing problem (ALWIBP), being a particular case of the assembly line worker assignment and balancing problem (ALWABP), which occurance is more common in SWDs. Our goal consists in studying efficient ways to promote the integration of people with disabilities in conventional assembly lines. For that, we address ALWIBP variants that consider: (i) minimization of different objective functions (number of stations or cycle time); (ii) different assembly line layouts (simple or U-shaped); (iii) uncertainties on task execution times (robust approach); (iv) job rotation strategies or allocation of disabled workers in the line with regular spacing. For each of these extensions, we develop mathematical formulations, solution methods and new sets of benchmark instances. Computational experiments indicate possibilities for adapting conventional assembly lines to the insertion of disabled workers, at low or close to null additional costs. Therefore, this study offers alternatives ways of increasing exibility in the integration of people with disabilities, making them as efficient as any other conventional worker.