Made available in DSpace on 2015-05-14T12:36:29Z (GMT). No. of bitstreams: 1 arquivototal.pdf: 2138461 bytes, checksum: b91d7f14f64fd9d32fd38aee2b19b970 (MD5) Previous issue date: 2010-07-16 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / This work approaches the problem of the tasks scheduling (Job Shop Scheduling) through the combination of the GRASP and Tabu Search metaheuristics. The study consists of using the GRASP (Greedy Randomized Adaptive Search Procedure) in the construction phase of the initial solution, suggesting for that, a specific procedure based on Coffman Gramah algorithm. However, such procedure was the great differential in this study, since it offers an initial solution qualitatively better, what allows the reduction of the local search time, where it was utilized the Tabu Search metaheuristic in the local search phase, which provided best results when it was compared with other metaheuristics that have the same structural base. The combination GRASP and Tabu Search were evaluated under two differentiated implementations, being one with Tabu Search in its form more simplified and another one with Tabu Search developing a process of optimized search, using an aditional mathematical model, which demonstrated great advancements in relation at processing time and the obtained results. The computational results, when compared with the existing ones in literature, they had shown that GRASP and Tabu Search combination are capable to produce good solutions. / Este trabalho aborda o problema de escalonamento de tarefas (Job Shop Scheduling) através da combinação das metaheurísticas GRASP e Busca Tabu. O estudo consiste em utilizar o GRASP na fase de construção da solução inicial, sugerindo, para tanto, um procedimento específico baseado no algoritmo de Coffman Gramah. Tal procedimento foi o grande diferencial deste trabalho, visto que oferece uma solução inicial qualitativamente superior, permitindo a redução do tempo de busca local, onde foi utilizada a metaheurística Busca Tabu, a qual demonstrou proporcionar melhores resultados, comparando-se com outras metaheurísticas que seguem a mesma base estrutural. A combinação GRASP e Busca Tabu foi avaliada sob duas implementações diferenciadas, sendo uma com a Busca Tabu em sua forma mais simplificada e outra com a Busca Tabu desenvolvendo um processo de busca otimizada com o auxílio de um modelo matemático , a qual demonstrou grandes progressos quanto ao tempo de processamento e a obtenção de resultados. Os resultados computacionais obtidos, quando comparados com os existentes na literatura, mostraram que a combinação GRASP e Busca Tabu é capaz de produzir boas soluções.

This study considers a vehicle routing problem with time windows, accessibility restrictions on customers and a fleet that is heterogeneous with regard to capacity, average speed and cost. A vehicle can perform multiple routes per day, all starting and ending at a single depot, and it is assigned to a single driver, whose total work hours are limited. The available fleet is divided into an owned fleet, for which a variable cost is incurred, and a chartered fleet, for which only a fixed cost is incurred for each vehicle used. A column generation algorithm embedded in a branch-and-bound framework is proposed. The column generation pricing subproblem required a specific elementary shortest path problem with resource constraints algorithm to address the possibility for each vehicle performing multiple routes per day and to address the need to determine the workdays start time within the planning horizon. To make the algorithm efficient, a constructive heuristic and a learning metaheuristic algorithm based on tabu search were also developed. Both were used on branch-and-bound tree nodes to generate a good initial solution to the linear restricted master problem; particularly, to find a good initial primal bound to the branch-and-bound tree. / Este estudo aborda um problema de roteirização de veículos com janelas de tempo, restrições de acessibilidade nos clientes e uma frota que é heterogênea em relação à capacidade de carga, velocidade média de deslocamento e custo. Um veículo pode percorrer múltiplas rotas por dia, todas começando e terminando em um mesmo depósito, e está designado a um único motorista, cujo total de horas trabalhadas no dia está limitado a um valor máximo. A frota disponível é dividida em uma frota própria, para a qual um custo variável é incorrido, e uma frota de freteiros, para a qual apenas um custo fixo é incorrido para cada veículo utilizado. Um algoritmo baseado em geração de colunas, integrado a um procedimento de branch-and-bound, é proposto neste estudo. O subproblema de precificação da geração de colunas requereu um algoritmo específico para o problema do caminho mínimo elementar com restrições sobre recursos capaz de lidar com a possibilidade de cada veículo percorrer múltiplas rotas por dia e capaz de lidar com a necessidade de determinar o instante de início do dia de trabalho do motorista dentro do horizonte de planejamento. Para tornar o algoritmo eficiente, uma heurística construtiva e uma heurística de melhoria baseada em busca tabu também foram desenvolvidos. Ambos são utilizados nos nós da árvore de branch-and-bound para gerar boas soluções iniciais para o problema mestre restrito da geração de colunas; particularmente, para encontrar um bom limitante primal inicial para a árvore de branch-and-bound.

Orientador: Vinícius Amaral Armentano / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação / Made available in DSpace on 2018-08-16T07:40:14Z (GMT). No. of bitstreams: 1 Sacchi_LuisHenrique_D.pdf: 1448719 bytes, checksum: f89915d271683e250283d8ec86b25839 (MD5) Previous issue date: 2010 / Resumo: Este trabalho apresenta um estudo computacional da busca tabu paramétrica para resolver problemas de programação inteira mista (PIM) com variáveis binárias. Trata-se de uma heurística genérica para problemas PIM gerais que resolve uma série de problemas de programação linear ao incorporar inequações de ramificação de variáveis inteiras como termos ponderados na função objetivo. O procedimento central do método é baseado em memória de curto prazo da busca tabu, enquanto fases de intensificação e diversificação são induzidas pela memória de longo prazo baseada em freqüência e idéias derivadas de scatter search. Novas estratégias são propostas para encontrar soluções de alta qualidade e extensivos testes computacionais são realizados em instâncias da literatura / Abstract: We present a computational study of parametric tabu search for solving 0-1 mixed integer programming (MIP) problems, a generic heuristic for general MIP problems that solves a series of linear programming problems by incorporating branching inequalities as weighted terms in the objective function. The core procedure is founded on short term memory, whereas both intensification and diversification phases are induced by long term memory based on frequency and ideas derived from scatter search. New strategies are proposed for uncovering feasible and high-quality solutions and extensive computational tests are performed on instances from the literature / Doutorado / Automação / Doutor em Engenharia Elétrica

Orientador: Vinicius Amaral Armentano / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-11T06:29:58Z (GMT). No. of bitstreams: 1 Shiguemoto_AndreLuis_D.pdf: 2284701 bytes, checksum: 01f64264e516fb8e883b2f2632cace5b (MD5) Previous issue date: 2008 / Resumo: Este trabalho aborda a otimização de dois problemas integrados de uma seção de uma cadeia de suprimento. O primeiro é um problema de produção-distribuição ao longo de períodos de um horizonte de planejamento finito. Uma planta com restrições de capacidade processa vários produtos e uma frota homogênea de veículos está disponível para distribuição de produtos para atender a demanda dos clientes. Em cada período, o problema de produção determina quanto processar de cada produto, e o problema de distribuição define a quantidade de cada produto a ser entregue aos clientes e as rotas dos veículos. O objetivo é minimizar os custos de produção e estoque na planta, custos de estoque no cliente e custos de distribuição. O problema é resolvido pela meta-heurística busca tabu integrada com um procedimento de religamento de caminho, que permite soluções infactíveis durante a busca. O segundo problema envolve a seção estoque-produção com demanda estocástica de um único produto, especificada por uma distribuição discreta de probabilidades. O fornecedor deve definir quando visitar os clientes, quanto entregar, e as rotas de cada período, de forma a maximizar o rendimento pelas quantidades entregues e minimizar os custo de estoque nos clientes, custos de demanda perdida e custos de distribuição. O problema é modelado por meio de uma árvore de cenários que aproxima um processo de decisão markoviano. Uma heurística baseada em horizonte rolante é desenvolvida, de forma que em cada passo, o modelo definido em uma janela de tempo é resolvido de forma ótima pelo software de otimização CPLEX / Abstract: This work addresses the optimization of two integrated problems in a section of a suppy chain. The first is a production-distribution problem along periods of a finite planning horizon. A plant with capacity constraints processes several products and a homogeneous fleet of vehicles is available for the distribution of the products in order to satisfy the customers¿ demand. In each period, the production problem determines how much to process of each product, and the distribution problem defines the quantity of the product that should be delivered, and the vehicle routes. The objective is to minimize the production and inventory cost at the plant, inventory costs at the clients and the distribution costs. The problem is solved by the tabu search meta-heuristic integrated with a path relinking procedure, and infeasible solutions are allowed during the search. The second problem involves the section inventory-distribution with stochastic demand defined by a discrete probability distribution. The supplier must define when to visit the clients, how much to deliver, and the routes of each period in order to maximize the reward from delivering the delivered quantities and minimize the inventory costs at the clients, costs for lost demand and distribution costs. The problem is modeled as a scenario tree that approximates a markovian decision process. A heuristic based on a rolling horizon is developed, such that at each step, the model defined in a sliding time window is solved optimally by the optimization software CPLEX / Doutorado / Automação / Doutor em Engenharia Elétrica

Submitted by Izabel Monteiro (izabel_22@hotmail.com) on 2016-06-17T14:20:01Z No. of bitstreams: 1 Dissertação-Francisco Ivan Rodrigues de Andrade.pdf: 6673381 bytes, checksum: 9501e6a18c7292453a100a4e6fdaba24 (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2016-06-23T20:11:38Z (GMT) No. of bitstreams: 1 Dissertação-Francisco Ivan Rodrigues de Andrade.pdf: 6673381 bytes, checksum: 9501e6a18c7292453a100a4e6fdaba24 (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2016-06-23T20:14:26Z (GMT) No. of bitstreams: 1 Dissertação-Francisco Ivan Rodrigues de Andrade.pdf: 6673381 bytes, checksum: 9501e6a18c7292453a100a4e6fdaba24 (MD5) / Made available in DSpace on 2016-06-23T20:14:26Z (GMT). No. of bitstreams: 1 Dissertação-Francisco Ivan Rodrigues de Andrade.pdf: 6673381 bytes, checksum: 9501e6a18c7292453a100a4e6fdaba24 (MD5) Previous issue date: 2015-06-19 / Search for energy efficiency is currently one of the main global challenges. Energy demand is growing and this is attributed to increased energy consumption in homes. In this scenario of a big energy demand, public policies related to changes in the tariff structure of the bills have been applied in an attempt to improve the use of energy resources and prevent collapses in the Brazilian electric sector. It is becoming evident that the knowledge and the management of residential energy consumption need to be improved. Thus, home energy management systems have been proposed for monitoring and control of electrical infrastructure and appliances in homes. However, most existing solutions are designed with limited scope such as lighting control with motion detection, climate control based on ambient temperature and control of turning on and off electrical appliances. To overcome these limitations, studies have been conducted with the aim of providing features that minimize power consumption and energy costs based on the quantity of people in the residential and their profiles. Studies in the literature seek to generate schedules for the implementation of appliances considering different variables and constraints such as appliance power, runtime, variable rate by time, balanced usage of appliances out off-peak hours and user criteria of comfort/preference, featuring a NP-Hard optimization problem. To solve this problem, we propose in the work a method called Zippy, which assists the reduction of energy cost through running appliances schedules while meeting a set of predefined constraints. The proposed method uses Tabu Search metaheuristic to assist in the appliance execution schedule in a more economically way. Experiments carried out in a database from a home showed that the method is able to provide good programming acquiring an overall savings of up to 46% compared with the original cost obtained without the method. / A busca pela eficiência energética representa atualmente um dos principais desafios mundiais. Em função do cenário crescente de demanda de energia, políticas públicas relacionadas a mudanças na estrutura tarifária das contas de energia têm sido aplicadas na tentativa de melhorar a utilização dos recursos energéticos e evitar colapsos no setor de energia elétrica brasileiro. Tal fato torna cada vez mais evidente a necessidade de conhecer e gerenciar o consumo de energia residencial. Dessa forma, sistemas de gerenciamento de energia residencial têm sido propostos para o monitoramento e controle da infraestrutura elétrica e dos eletrodomésticos em residências. No entanto, a maioria das soluções existentes é projetada com escopo limitado, tais como controle de iluminação com detecção de movimento, controle do clima com base na temperatura interna do ambiente, e controle para ligar e desligar aparelhos elétricos. Para superar estas limitações, estudos têm sido realizados com o objetivo de fornecer funcionalidades que permitam minimizar o consumo e o custo de energia em função do número e perfil das pessoas na residência. Na literatura há trabalhos que geram programações para a execução dos aparelhos considerando diferentes variáveis e restrições como potência de aparelho, tempo de execução, tarifa variável por horário e balanceamento de uso dos aparelhos para fora do horário de ponta, a combinação desse grande número de variáveis caracteriza um problema de otimização de complexidade NP-difícil. Para superar este problema, este trabalho propõe um método, denominado Zippy, que auxilia na redução do custo de energia por meio de uma programação de horários de execução dos aparelhos, satisfazendo ao mesmo tempo um conjunto de restrições pré-definidas. O método proposto utiliza a metaheurística Busca Tabu para auxiliar na geração de programação de execução de aparelhos em intervalos de tempo mais viáveis economicamente. Experimentos realizados com uma base de dados de uma residência mostram que o método é capaz de fornecer boas programações adquirindo uma economia geral de até 46% quando comparado com os custos originais obtidos sem a aplicação do método.

Orientador: Vinícius Amaral Armentano / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação / Made available in DSpace on 2018-08-22T22:56:34Z (GMT). No. of bitstreams: 1 Branchini_RodrigoMoretti_D.pdf: 2921053 bytes, checksum: 29694a6f4803c5c222c97cbe95a2b199 (MD5) Previous issue date: 2013 / Resumo: Este trabalho aborda um problema de planejamento tático em empresas de transporte marítimo de carga que coletam e entregam as demandas contratadas por seus clientes. As viagens associadas a estas demandas são obrigatórias, mas a empresa pode também atender a demandas spot associadas com viagens opcionais para aumentar seu lucro durante um horizonte de tempo de médio prazo. O problema de otimização é formulado como um modelo de programação inteira mista que é definido em um grafo orientado em que nós representam viagens obrigatórias e opcionais. As decisões do modelo são determinar o número e tipo de navios que compõem a frota, designar um navio a um conjunto de viagens obrigatórias e opcionais, definir as rotas de cada navio e estipular os tempos de início de atendimento nos portos para cada viagem. Um algoritmo de busca tabu com uma lista de candidatos e um conjunto de soluções de elite são propostos para resolver instâncias do problema. Os resultados computacionais da busca tabu são comparados com as soluções ótimas e sub-ótimas encontradas pelo CPLEX para o modelo de programação inteira mista / Abstract: We address a tactical planning problem faced by many liner shipping companies that have committed contractual voyages while trying to serve optional spot voyages to increase its revenue over the medium-term horizon. The optimization problem is formulated as a mixed integer programming model that is defined on a directed graph whose nodes represent contractual and spot voyages. The decisions include the number and type of vessels deployed the assignment of vessels to contractual and spot voyages and the determination of vessel routes and schedules in order to maximize the profit. A tabu search algorithm with a candidate list and a pool of elite and diverse solutions is proposed in order to solve a set of benchmark instances of the problem. The results obtained by tabu search are compared to optimal and suboptimal solutions yielded by the CPLEX solver to the mixed integer programming formulation of the problem / Doutorado / Automação / Doutor em Engenharia Elétrica

[pt] O aumento do consumo de energia elétrica leva os sistemas de distribuição a operar próximo do seu limite, podendo ocorrer situações de máximo fluxo de potência ativa e reativa nos ramos, ou seja, problemas de estabilidade de tensão. A mudança da topologia da rede permite encontrar uma configuração em que os índices de estabilidade de tensão estão distantes do ponto de máximo carregamento do sistema, reduzir as perdas técnicas e tornar a distribuição de carga nos alimentadores mais uniforme. Contudo, o número de possibilidades de chaveamento cresce com o aumento da dimensão da rede elétrica e a busca pela solução ótima requer esforço computacional elevado. O uso do algoritmo heurístico de Busca Tabu permite direcionar a busca por novas configurações de qualidade, armazenando suas características e proibindo a adição e/ou remoção de atributos por um período, evitando que a busca termine em um valor mínimo (máximo) local. Os resultados das análises em diferentes níveis de carregamento, que representam a operação do sistema radial de distribuição com carga leve, pesada e crítica, mostram que o algoritmo de Busca Tabu adotado neste trabalho consegue maximizar a margem de potência da barra crítica do sistema, levando o ponto de operação original à uma distância maior do ponto de máximo carregamento do sistema, na região normal de operação e minimizando as perdas técnicas. Com isso, evita-se que o sistema opere no ponto de máximo carregamento ou, na pior das hipóteses, na região anormal de operação, onde as ações de controle têm efeito oposto ao esperado. / [en] The increase of the consumption of electric energy takes the distribution systems to operate next to its limits, which might cause situation of maximum active and reactive power flow in the branches, that is, problems of voltage stability. The change of the topology of the network allows to find a configuration where de voltage stability indexes are far from de maximum loading point, improve voltage profile, reduce power losses and load balancing. However, the number of possible switching grows with the dimension of network and searching for optimal solution requires high computational effort. Using Tabu Search heuristics allows guiding the search for new configuration of high quality, being storing its characteristics and forbidding the addition and/or removal of attributes for a period, avoiding that the search finishes in a local minimum (maximum) value. The results in different loading levels, that represent the operation of radial distribution system with normal, weighed and critical load, show that the Tabu Search algorithm maximizes the voltage stability margin, leading the original operation point to a new one that is far from the maximum loading point, in the normal region of operation. With this, it is prevented that the system operates next to the maximum loading point or, in the worse case, in the abnormal region of operation, where the actions of control have opposing effect to the waited one.

The thesis deals with optimization problems which arise at distribution planning. These problems can often be easily formulated as integer programming problems, but rarely can be solved using mixed integer programming techniques. Therefore, it is necessary to study the efficiency of heuristic algorithms. The main focus of the thesis is on the vehicle routing problem with time windows. A tabu search algorithm for this problem was developed and implemented. It uses integer programming to solve the set partitioning problem in order to find optimal distribution of all customers into feasible routes found during the search. The results of the classical integer programming approach, basic insertion heuristic and presented tabu search algorithm are compared in a numerical study.

Orientador: Ruben Augusto Romero Lazaro / Resumo: Este trabalho apresenta uma proposta baseada na meta-heurística Busca Tabu, chamada de Busca Tabu Reformulada para resolver o problema de operação ótima dos sistemas de distribuição, utilizando uma estratégia integrada de reconfiguração e alocação de bancos de capacitores fixos e chaveados para obter a topologia radial que apresente o menor custo de operação. Para encontrar a topologia radial inicial foi aplicado o algoritmo de Prim, em que foi obtida uma solução reconfigurada, e essa solução encontrada foi submetida à uma heurística para alocação de capacitores fixos e chaveados. A proposta de solução inicial é submetida ao algoritmo de Busca Tabu Reformulada que utiliza uma vizinhança que considera como solução vizinha uma topologia vizinha da topologia radial corrente e com a proposta de alocação de bancos de capacitores modificada. Como proposta da metodologia Busca Tabu Reformulada o procedimento é repetido até um critério de parada definido. Todos os programas foram escritos em linguagem FORTRAN 77. Os algoritmos propostos foram testados com os sistemas de 33, 70, 84 e 136 barras. / Abstract: This paper presents a proposal based on the Tabu Search metaheuristic called Tabu Search Reformulated to solve the problem of optimal operation of the distribution systems, using an integrated strategy of reconfiguration and allocation of fixed and switched capacitor banks to obtain the radial topology which presents the lowest operating cost. To find the initial radial topology the Prim algorithm was applied, in which a reconfigured solution was obtained, and this solution was submitted to a heuristic for the allocation of fixed and switched capacitors. The initial solution proposal is submitted to the Reformulated Tabu Search algorithm that uses a neighborhood that considers as neighbor solution a neighboring topology of the current radial topology and with the proposed allocation of modified capacitor banks. As a proposal of the Tabu Search Reformulated methodology, the procedure is repeated up to a defined stop criterion. All the programs were written in FORTRAN 77 language. The proposed algorithms were tested with the 33, 70, 84 and 136-node systems. / Mestre

Neste trabalho é proposta uma nova técnica de solução para resolver o problema de planejamento da expansão de sistemas de transmissão estático através da introdução da tomada de decisão fuzzy. Na técnica apresentada neste trabalho, a tomada de decisão fuzzy é aplicada para o desenvolvimento de um algoritmo heurístico construtivo. O sistema fuzzy é utilizado para contornar alguns problemas críticos das heurísticas que utilizam o índice de sensibilidade como guia para inserção de novas linhas. A heurística apresentada nesse trabalho é baseada na técnica dividir para conquistar. Verificou-se que a deficiência das heurísticas construtivas é decorrente da decisão de inserir novas linhas baseada em valores não seguros encontrados através da solução do modelo utilizado. Para contornar tal deficiência, sempre que surgirem valores não seguros divide-se o problema original em dois subproblemas, um que analisa a qualidade da resposta para o caso em que a linha é inserida e outro para verificar a qualidade da resposta para o caso em que a linha não é inserida. A tomada de decisão fuzzy é utilizada para decidir sobre quando dividir o problema em dois novos subproblemas. Utilizou-se o modelo cc com a estratégia de Villasana-Garver-Salon para realizar a modelagem da rede elétrica para os problemas da expansão de sistemas de transmissão aqui propostos. Ao serem realizados testes em sistemas de pequeno, médio e grande portes certificou-se que o método pode encontrar a solução ótima de sistemas de pequeno e médio portes. Porém, a solução ótima dos sistemas de grande porte testados não foi encontrada. Para melhorar a qualidade da solução encontrada utilizou, em uma segunda fase, a metaheurística busca tabu. A busca tabu utiliza o modelo cc. Os resultados se mostraram bastante promissores. Os testes foram realizados em alguns sistemas reais brasileiros e com o sistema real colombiano. / A new solution technique to solve the long-term static transmission expansion planning (TEP) problem based on fuzzy decision making is proposed. The technique applies the concepts of fuzzy decision making in a constructive heuristic algorithm. The fuzzy system is used to circumvent some critical problems of heuristics that use sentivity indices as a guide for insertion and construction of new lines. The heuristic algorithm proposed in this work is based on the divide and conquer technique. It has been verified that the deficiency of the constructive heuristics is due to the decision of inserting new lines based only on information given by the index, which usually is calculated from a relaxed mathematical representation of the problem and can become less accurate during the solution process. In order to be able to deal with such problem, whenever the quality of the index decreases, the original problem is divided into two sub-problems: one examines the quality of the solution when the transmission line indicated by the sensitivity index is inserted and the other subproblem checks the opposite. Fuzzy decision-making is used to decide the moment to divide the problem into two subproblems based on other information. The hybrid linear model is used to model the long-term transmission expansion planning problem and is used in the proposed algorithm. Tests was done with systems of small-term, medium-term and long-term. The optimal solution of small-term and medium-term was foundo using just the construtive heuristic algorithm with fuzzy decision-making. To deal with long-term systems was used the solutions of the construtive heuristic algorithm with fuzzy decision-making to init a tabu search. The tabu search uses the dc model. The results are very promising. The test was done with some real brazilian systems and with the real colombian system.