Nesta dissertação estudamos --- do ponto de vista algorítmico --- o seguinte problema, conhecido como problema da partição conexa balanceada. Dado um grafo conexo G com pesos atribuídos a seus vértices, e um inteiro q >= 2, encontrar uma partição dos vértices de G em q classes, de forma que cada classe da partição induza um grafo conexo e que, ao considerar as somas dos pesos dos vértices de cada classe, a menor das somas seja o maior possível. Em outras palavras, o objetivo é encontrar q classes cujos pesos sejam tão balanceados quanto possível. Sabe-se que este problema é NP-difícil. Mencionamos alguns resultados sobre complexidade computacional e algoritmos que são conhecidos para este problema. Apresentamos algumas heurísticas que desenvolvemos, todas elas baseadas no uso do algoritmo polinomial para árvores, devido a Perl e Schach, que apresentamos com detalhe. Implementamos quatro heurísticas e um algoritmo de 3/4-aproximação conhecido para o caso q=2. Exibimos os resultados obtidos com os vários testes computacionais conduzidos com instâncias aleatórias, com grafos de diferentes pesos e densidades. Os resultados computacionais indicam que o desempenho dessas heurísticas --- todas elas polinomiais --- é bem satisfatório. No caso especial em que q=2, observamos que a heurística mais onerosa sistematicamente produziu soluções melhores ou iguais às do algoritmo de aproximação / In this dissertation we study algorithmic aspects of the following problem, known as the balanced connected partition. Given a connected graph G with weights defined on its vertices, and an integer q >= 2, find a partition of the vertices of G into q classes such that each class induces a connected graph, and furthermore, when we consider the sum of the weights of the vertices in each class, the smallest sum is as large as possible. In other words, the q classes must have weights that are as balanced as possible. This problem is known to be NP-hard. We mention some computational complexity and algorithmic results that are known for this problem. We present some heuristics that we designed, all of them based on the use of the polynomial algorithm for trees, due to Perl and Schach, which we show in detail. We implemented four heuristics and a 3/4-approximation algorithm that is known for q=2. We run tests on many random instances, of graphs with different weights and densities. The computational results indicate that the performance of these heuristics --- all of polynomial time complexity --- are very satisfactory. For q=2, we observed that the most expensive heuristic produced solutions with values which are systematically better or equal to those produced by the approximation algorithm.

El objetivo de la tesis doctoral "MODELOS Y MÉTODOS PARA EL PROBLEMA DE PROGRAMACIÓN DEL LOTE ECONÓMICO CON COPRODUCCIÓN DELIBERADA Y CONTROLADA (DCC-ELSP)", realizada por Dña. Pilar Isabel Vidal Carreras y dirigida por Dr. D. Jose Pedro García Sabater, es analizar y modelar el problema de programación de producción con coproducción controlada y deliberada, en el contexto del sector de los proveedores del automóvil, que se asimila al problema ELSP - Economic Lot Scheduling Problem (Problema de Programación del Lote Económico). Para esto, se requiere la definición de diferentes metodologías y algoritmos que permitan resolverlo de manera satisfactoria. Interés del Problema El origen del problema de esta tesis surge como resultado del continuo y extenso contacto del director de la tesis, Dr. D. José P. García Sabater y más reciente de la doctoranda, Dña. Pilar I. Vidal Carreras, con las empresas suministradoras del sector del automóvil (Garcia-Sabater et al., 2006a; Garcia-Sabater y Marin-Garcia, 2009; Garcia-Sabater et al., 1999; Garcia-Sabater, 2000; Garcia-Sabater y Vidal-Carreras, 2010; Garcia-Sabater et al., 2006b; Miralles et al., 2005; Vidal-Carreras y Garcia-Sabater, 2005). La coproducción deliberada y controlada (DCC - Deliberate Controlled Coproduction), esto es, la opción de fabricar o no (deliberación) dos productos simultáneamente de manera controlada, en este entorno aparece con frecuencia. Para citar un ejemplo comentar como los automóviles contienen muchas partes simétricas para el lado izquierdo y derecha del vehículo (retrovisores, puertas, faros, etc). Estos procesos de producción son a menudo diseñados para producir la parte izquierda y la parte derecha al mismo tiempo. Esta situación no parece ser un problema cuando se producen piezas para un coche nuevo. Sin embargo, las mismas instalaciones de fabricación se utilizan para producir piezas de repuesto para reemplazar las piezas dañadas. / Vidal Carreras, PI. (2011). Modelos y métodos para el problema de programación del lote económico con coproducción deliberada y controlada (DCC-ELSP) [Tesis doctoral no publicada]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/9919 / Palancia

Orientador: Edilaine Martins Soler / Resumo: Neste trabalho, o problema de Fluxo de Potência Ótimo Reativo problema é modelado como um problema de Programação Não Linear Inteira Mista que tem como objetivo minimizar as perdas de potência ativa nas linhas de transmissão de energia elétrica e satisfazer as restrições físicas e operacionais do Sistema Elétrico de Potência. Afim de solucionar o problema, propõem-se três abordagens heurísticas de solução, denominadas de heurística de factibilidade, heurística de melhoria de solução e gap de integralidade como restrição de igualdade. As duas primeiras abordagens são baseadas na minimização do gap de integralidade das variáveis discretas. A heurística de factibilidade objetiva encontrar uma solução factível para o problema por meio de uma busca local. Já a heurística de melhoria de solução objetiva encontrar soluções factíveis melhores a cada iteração até que não seja mais possível, por meio de uma restrição de corte de nível da função objetivo. A terceira abordagem considera a função gap de integralidade como uma restrição do problema de Fluxo de Potência Ótimo Reativo contínuo. Em todas as abordagens, o problema de Fluxo de Potência Ótimo Reativo original é transformado em um problema contínuo resolvido pelo método de pontos interiores com filtro disponibilizado no solver Interior Point OPTimizer em interface com o software General Algebraic Modeling System. Testes numéricos com os sistemas elétricos IEEE 14, 30, 118 e 300 barras e PEGASE 1354 barras são realizados para comp... (Resumo completo, clicar acesso eletrônico abaixo) / Abstract: In this work, the Reactive Optimal Power Flow problem is modeled as a Mixed-IntegerNon-Linear Programming problem and aims to minimize the active power losses throughoutthe transmission system, while satisfying the physical and technical constraints of thePower System. In order to solve the problem, three heuristics approaches are proposed,namely feasibility and solution improvement heuristics. The first and the second proposedheuristics are based on the minimization of the integrality gap of the discrete variables. Thefeasibility heuristic aims to find a feasible solution to the problem through a local search.The solution improvement heuristic aims to find better feasible solution iteratively until itis no longer possible, by adding level cuts in the objective function. The third approachconsiders the proposed integrality gap function as a new constraint of the continuousReactive Optimal Power Flow problem. In both approaches, the original Reactive OptimalPower Flow problem is modeled as a continuous problem and solved by the interior pointmethod with filter implemented in the Interior Point OPTimizer solver under the GeneralAlgebraic Modeling System interface. Numerical tests with the IEEE 14-, 30-, 118 and300-bus and the PEGASE 1354-bus electrical power systems are performed to show theefficiency of the proposed approaches. The numerical results indicate that the proposedapproaches showed to be competitive when compared to exact methods published in theliterature. / Doutor

O problema de programação de operações em ambiente no-wait flow shop tem sido abordado desde a década de 60. Por se tratar de um ambiente em que as tarefas devem ser processadas continuamente e sem interrupções entre uma máquina e outra, um tempo de espera entre o início da tarefa anterior e o início da tarefa atual deve ser determinado na primeira máquina. Neste sentido, uma vez que a tarefa inicia seu processamento, as máquinas devem estar disponíveis para que atendam a restrição de no-wait. Portanto, operações de manutenção preventiva são necessárias para que a programação seja atendida sem maiores problemas. Este trabalho aborda dois problemas: no-wait flow shop e no-wait flow shop com operações de manutenção preventiva. O critério de desempenho adotado foi a duração total da programação (makespan). Por meio de uma revisão de literatura, mecanismos de construção de soluções foram identificadas e classificadas e, baseando-se em tais, novos métodos heurísticos construtivos simples e compostos foram propostos para o problema no-wait flow shop e uma heurística composta foi desenvolvida considerando as operações de manutenção preventiva. Experimentações computacionais para os dois problemas foram realizadas para fins de comparação e avaliação dos métodos propostos com os métodos heurísticos construtivos da literatura. Para o problema Fm|no - wait|Cmax resultados evidenciaram que as heurísticas propostas H4GPSLLS e MH4GPSLLS superaram as heurísticas da literatura em qualidade de solução, com diferença estatisticamente significativa no nível de 5% de significância. Para o problema Fm|no - wait, m(k)|Cmax, pode-se constatar que a heurística BIHLS e as heurísticas H4GPSLLS e MH4GPSLLS apresentaram desempenho superior com diferença estatística significativa no nível de 5% de significância em comparação as heurísticas da literatura. / The no-wait flow shop scheduling problem has been studied since 60\'s. In this environment, jobs must be processed continuously without interruption between one machine and another, and because of this, a delay between the start time of the previous job and the start time of the current job must be determined in the first machine. In this sense, since a job starts its processing, the machines must be available to respect the no-wait constraint. Therefore, preventive maintenance operations are needed. This work adresses two problems: the m machine no-wait flow shop and the m machine no-wait flow shop with preventive maintenance operations. The performance measure adopted was the makespan. By means of a literature review, mechanisms of solution construction were identified and classified. New simple and composite constructive heuristics were proposed to the no-wait flow shop problem and a new composite constructive heuristic was developed considering the preventive maintenance operations. Computational experiments and their respective analyses for both problems were carried out to compare and evaluate the performance between the proposed methods and the constructive heuristics of the literature. Regarding Fm|no - wait|Cmax problem, results show that the proposed heuristics H4GPSLLS and MH4GPSLLS outperformed the heuristics of the literature in quality of the solution and is statistically significative to 5% of significance level. To the Fm|no - wait, m(k)|Cmax problem it can be seen that the proposed heuristic BIHLS and H4GPSLLS and MH4GPSLLS outperformed the heuristics of the literature and is statistically better to 5% of significance level.

Esta pesquisa trata o Problema de Programação de Tripulantes (PPT), presente no planejamento operacional das empresas aéreas. O principal objetivo do PPT é atribuir o conjunto de tripulantes requeridos para a operação dos voos de uma malha aérea de maneira a minimizar o custo total da tripulação, levando em conta a legislação pertinente e a satisfação dos tripulantes. O PPT é normalmente dividido na literatura em dois subproblemas independentes, modelados e resolvidos sequencialmente: Problema de Determinação de Viagens (PDV) e Problema de Atribuição de Escalas (PAE). Esta decomposição não incorpora os atributos (disponibilidade, qualificação, senioridade e preferências individuais) dos tripulantes de forma global, o que não permite uma estimativa real de custo e afeta a qualidade da solução final. O estado da arte envolve a solução integrada do PPT, eliminando a necessidade de se resolver inicialmente o PDV e permitindo a obtenção de uma solução mais realista. O PPT, no entanto, é de natureza combinatória. Assim sendo, esta pesquisa propõe e explora modelos baseados em programação linear inteira e em heurísticas para a solução integrada do PPT. Essas heurísticas incorporam fundamentos da meta-heurística GRASP, da heurística de economias de Clarke e Wright e da heurística day-by-day. Os modelos foram testados com sucesso para a solução de instâncias baseadas na malha real de três empresas aéreas brasileiras. / This doctoral research treats the Crew Scheduling Problem (CSP), as part of the airlines operational planning. The CSP consists of optimally assigning the required crew members to planned flights, in such a way that it minimizes the total cost of the aircrew, taking into consideration the proper legislation and the satisfaction of the crew members. The CSP is usually divided into two independent subproblems, modeled and solved sequentially: Crew Pairing Problem (CPP) and Crew Rostering Problem (CRP). This decomposition does not incorporate all the crew members attributes (availability, qualification, seniority and individual preferences), which does not lead to a real cost estimate and affects the quality of the final solution. The state of the art involves the integrated solution of CSP, without solving the CPP at first and providing a more realistic solution. The CSP, however, has a combinatorial nature. This research proposes and explores models based on integer linear programming and on heuristics to solve the CSP in an integrated way. These heuristics incorporate GRASP metaheuristic, Clarke and Wright savings heuristic and day-by-day heuristic. The models were successfully tested to solve instances related to the networks of three Brazilian airlines.

Problemas de corte e empacotamento de itens irregulares são problemas que visam determinar um leiaute ótimo de objetos pequenos dentro de objetos maiores, a fim de atender a uma demanda. Estes problemas têm grande importância prática, já que surgem em vários tipos de indústria (como a têxtil, a de móveis e a de calçados). O problema estudado neste trabalho é o problema de corte de itens irregulares em recipientes. Os recipientes são delimitados e o objetivo é encontrar um leiaute dos objetos menores, sem sobreposição, dentro dos objetos maiores utilizando a menor quantidade de recipientes. Propomos um novo método de resolução para o problema. Nosso método é um algoritmo que gerencia um conjunto de heurísticas, de baixo nível, específicas para a resolução do problema com recipientes retangulares e irregulares. Recipientes irregulares são polígonos convexos e não convexos, que podem ser furados. As heurísticas desenvolvidas utilizam uma malha de pontos sobre a técnica de no-fit polygon para evitar a sobreposição dos itens e encontrar posições viáveis no recipiente retangular ou irregular. Os experimentos computacionais foram feitos para um grande conjunto de instâncias, de recipientes retangulares e irregulares. Os resultados demonstram a competitividade do método, que obtêm resultados bons e algumas soluções ótimas, em um tempo computacional aceitável. / Cutting and packing of irregular items are problems that aim to determine the optimum layout of small objects within larger objects (that we call bins), in order to meet a demand. These problems have great practical importance, since they emerge in various types of industry (such as textile, furniture and shoemaking). The problem studied in this work is the irregular bin packing problem. The bins are enclosed and the goal is to find a layout of items, without overlap, within the bins by using the minimum quantity of them. We propose a new method of resolution to this problem. Our method is an algorithm that manages a set of low-level heuristics, specific to solve the problem with rectangular bins and irregular bins. Irregular bins are convex and non-convex polygons, which may contain holes. The developed heuristics uses a mesh of points and the technique of no-fit polygon to avoid the overlapping of items and find feasible positions in rectangular or irregular bins. The computational experiments were performed for a large set of instances, using both rectangular and irregular bins. The results demonstrate the competitiveness of the method, which can get good results and some optimal solutions within an acceptable computational time.

O problema de programação de operações em ambiente no-wait flow shop tem sido abordado desde a década de 60. Por se tratar de um ambiente em que as tarefas devem ser processadas continuamente e sem interrupções entre uma máquina e outra, um tempo de espera entre o início da tarefa anterior e o início da tarefa atual deve ser determinado na primeira máquina. Neste sentido, uma vez que a tarefa inicia seu processamento, as máquinas devem estar disponíveis para que atendam a restrição de no-wait. Portanto, operações de manutenção preventiva são necessárias para que a programação seja atendida sem maiores problemas. Este trabalho aborda dois problemas: no-wait flow shop e no-wait flow shop com operações de manutenção preventiva. O critério de desempenho adotado foi a duração total da programação (makespan). Por meio de uma revisão de literatura, mecanismos de construção de soluções foram identificadas e classificadas e, baseando-se em tais, novos métodos heurísticos construtivos simples e compostos foram propostos para o problema no-wait flow shop e uma heurística composta foi desenvolvida considerando as operações de manutenção preventiva. Experimentações computacionais para os dois problemas foram realizadas para fins de comparação e avaliação dos métodos propostos com os métodos heurísticos construtivos da literatura. Para o problema Fm|no - wait|Cmax resultados evidenciaram que as heurísticas propostas H4GPSLLS e MH4GPSLLS superaram as heurísticas da literatura em qualidade de solução, com diferença estatisticamente significativa no nível de 5% de significância. Para o problema Fm|no - wait, m(k)|Cmax, pode-se constatar que a heurística BIHLS e as heurísticas H4GPSLLS e MH4GPSLLS apresentaram desempenho superior com diferença estatística significativa no nível de 5% de significância em comparação as heurísticas da literatura. / The no-wait flow shop scheduling problem has been studied since 60\'s. In this environment, jobs must be processed continuously without interruption between one machine and another, and because of this, a delay between the start time of the previous job and the start time of the current job must be determined in the first machine. In this sense, since a job starts its processing, the machines must be available to respect the no-wait constraint. Therefore, preventive maintenance operations are needed. This work adresses two problems: the m machine no-wait flow shop and the m machine no-wait flow shop with preventive maintenance operations. The performance measure adopted was the makespan. By means of a literature review, mechanisms of solution construction were identified and classified. New simple and composite constructive heuristics were proposed to the no-wait flow shop problem and a new composite constructive heuristic was developed considering the preventive maintenance operations. Computational experiments and their respective analyses for both problems were carried out to compare and evaluate the performance between the proposed methods and the constructive heuristics of the literature. Regarding Fm|no - wait|Cmax problem, results show that the proposed heuristics H4GPSLLS and MH4GPSLLS outperformed the heuristics of the literature in quality of the solution and is statistically significative to 5% of significance level. To the Fm|no - wait, m(k)|Cmax problem it can be seen that the proposed heuristic BIHLS and H4GPSLLS and MH4GPSLLS outperformed the heuristics of the literature and is statistically better to 5% of significance level.

Made available in DSpace on 2017-07-10T17:11:50Z (GMT). No. of bitstreams: 1 Parte 1.pdf: 9399593 bytes, checksum: 2b9a870f5813a4e937b5ce7233c9debc (MD5) Previous issue date: 2015-03-20 / Fundação Parque Tecnológico Itaipu / In this dissertation the modeling of an expert system to support analysis in medium voltage overhead lines is presented, allowing simulations of different networks in a web environment. Based on object-oriented methodology, this system follows as a demonstration of the application of artificial intelligence to act on problems relating to the Electrical Power Distribution Systems. With its implementation, it was possible to automate the processing of data for the calculation of power flow, showing through interface, information necessary for carrying out the analysis in these systems. The modeling of the backward forward sweep method was attached to the proposed model, and was employed as the expert system inference engine, and a heuristic model was established to power flow solution, with the property to adapt to the characteristics of networks, with representation of balanced or unbalanced loads, and with two types of mechanisms to suggest improvements and diagnostics on networks with problems in voltages profiles. / Neste trabalho é apresentada a modelagem de um sistema especialista para suporte à análises em redes de média tensão, possibilitando simulações de diversas redes em ambiente web. Baseado na metodologia orientada a objetos, este sistema segue como uma demonstração da aplicação de inteligência artificial para atuar em problemas relacionados com os Sistemas de Distribuição de Energia Elétrica. Com a sua implementação foi possível automatizar o processamento de dados para o cálculo do fluxo de potência, apresentando por meio de interface gráfica, as informações necessárias para a realização das analises nestes sistemas. Acoplando a modelagem do método backward forward sweep no modelo proposto, empregando-a como motor de inferência do sistema especialista, foi estabelecida uma modelagem de solução heurística para o fluxo de potência, com a propriedade de se adaptar às características das redes, com representação de cargas balanceadas ou desbalanceadas, e com dois tipos de mecanismos para sugestão de melhorias e diagnósticos em redes com problemas nos perfis de tensões.

O problema do caixeiro viajante (PCV) é um problema clássico de otimização que possui diversas variações, aplicações e instâncias. Encontrar a solução ótima para muitas instâncias desse problema é geralmente muito difícil devido o alto custo computacional. Vários métodos de otimização, conhecidos como meta-heurísticas (MHs), são capazes de encontrar boas soluções para o PCV. Muitos algoritmos baseados em diversas MHs têm sido propostos e investigados para diferentes variações do PCV. Como não existe um algoritmo universal que encontre a melhor solução para todas as instâncias de um problema, diferentes MHs podem prover a melhor solução para diferentes instâncias do PCV. Desse modo, a seleção a priori da MH que produza a melhor solução para uma dada instância é uma tarefa difícil. A pesquisa desenvolvida nesta tese investiga o uso de abordagens de meta-aprendizado para selecionar as MHs mais promissoras para novas instâncias de PCV. Essas abordagens induzem meta-modelos preditivos a partir do treinamento das técnicas de aprendizado de máquina em um conjunto de meta-dados. Cada meta-exemplo, em nosso conjunto de meta-dados, representa uma instância de PCV descrita por características (meta-atributos) do PCV e pelo desempenho das MHs (meta-atributo alvo) para essa instância. Os meta-modelos induzidos são usados para indicar os valores do meta-atributo alvo para novas instâncias do PCV. Vários experimentos foram realizados durante a investigação desta pesquisa e resultados importantes foram obtidos / The traveling salesman problem (TSP) is a classical optimization problem that has several variations, applications and instances. To find the optimal solution for many instances of this problem is usually a very hard task due to high computational cost. Various optimization methods, known as metaheuristics (MHs), are capable to generate good solutions for the TSP. Many algorithms based on different MHs have been proposed and investigated for different variations of the TSP. Different MHs can provide the best optimization solution for different TSP instances, since there is no a universal algorithm able to find the best solution for all instances. Thus, a priori selection of the MH that produces the best solution for a given instance is a hard task. The research developed in this thesis investigates the use of meta-learning approaches to select the most promising MHs for new TSP instances. These approaches induce predictive meta-models from the training of machine learning techniques on a set of meta-data. In our meta-data, each meta-example is a TSP instance described by problem characteristics (meta-features) and performance of MHs (target meta-features) for this instance. The induced meta-models are used to indicate the values of the target meta-feature for new TSP instances. During the investigation of this research, several experiments were performed and important results were obtained

A presente pesquisa considera o problema de programação de uma frota de embarcações de lançamentos de dutos, conhecidas como Pipe Layer Support Vessel (PLSVs), as quais fazem parte da frota de apoio marítimo de uma operação offshore. As embarcações do tipo PLSVs são responsáveis pelas tarefas de lançamento de dutos submarinos, que escoam a produção dos poços de petróleo, e pela interligação destes dutos à infraestrutura submarina. A programação da frota deve atender uma demanda de serviço conhecida, em um horizonte de médio prazo, respeitando restrições operacionais, visando minimizar o atraso ponderado total das tarefas ou evitar que existam atrasos. Foi desenvolvido um método para estimar o valor da solução ótima do problema, baseado na técnica de relaxação Lagrangiana, e um conjunto de heurísticas para gerar soluções viáveis para o problema. / This research considers the problem of scheduling a fleet of specialized vessels used for launching pipes and connecting them to the subsea infrastructure, in an offshore oil production environment. The Pipe Layer Support Vessels (PLSV) must be scheduled such that the demand is fully attended within the planning horizon, observing other operational constraints, with the purpose of minimizing the total weighted tardiness. The solution method is based on constructive and local search heuristics. Bounds on the optimal solution were derived by a Lagrangean relaxation algorithm.