Orientador: Maria do Socorro Nogueira Rangel / Banca: Valeriano Antunes de Oliveira / Banca: Flávio Molina da Silva / Resumo: Nessa dissertação é feito uma revisão das características gerais dos problemas de corte e empacotamento e apresentam-se duas tipologias encontradas da literatura para classificar os problemas. São estudados em detalhes três problemas: (i) o problema da mochila limitada, (ii) o problema de corte bidimensional guilhotinado 2estágios restrito, e (iii) o problema do corte de estoque bidimensional. Para o problema (i) é proposto um algoritmo de programação dinâmica adaptado de um algoritmo proposto na literatura. Esse algoritmo é a base para a proposta de duas estratégias para resolver o problema (ii). Os algoritmos desenvolvidos para o problema (ii) são então usados no processo de geração de colunas usado para resolver o problema de corte de estoque exato. Resultados de um estudo computacional realizado para avaliar o desempenho dos algoritmos propostos usando instâncias da literatura são apresentados e analisados / Abstract: In this dissertation a review of the main characteristics of the Cutting and Packing problems are presented together with a summary of two typologies proposed in the literature to classify the problems. Three problems are studied in detail: (i) the Bounded Knapsack problem, (ii) the constraint two-dimensional guillotine 2-stage cutting problem, and (iii) the two-dimensional cutting stock problem. For problem (i) we propose a dynamic programming algorithm adapted from one given in the literature. This algorithm is the basis for the proposal of two strategies to solve the problem (ii). The algorithms developed for problem (ii) are then used in the column generation process employed to solve the exact cutting stock problem. Results of a computational study conducted to evaluate the performance of the proposed algorithms using instances of the literature are presented and analyzed / Mestre

[pt] Este trabalho faz reflexões sobre como é possível avançar na melhoria do gerenciamento de transporte, especificamente em relação às decisões mais operacionais, como a roteirização, através de métodos heurísticos simples e já difundidos na literatura. Utilizando um estudo de caso, é possível apresentar os benefícios da mudança de um método empírico de roteirização, totalmente baseado nos conhecimentos tácitos, para a aplicação de um método de criação de áreas de entregas e definição de rotas fixas de forma empírica. Além desta análise, o trabalho também apresenta a aplicação de um método dinâmico de roteirização utilizando o método de Clarke e Wright. Da comparação dos resultados obtidos surgem sugestões de criação de rotinas e ferramentas para aplicação do método, de forma consistente e definitiva, na operação da empresa do estudo de caso. / [en] In this research some considerations are made about the possibility of improving making the transportation management, specifically in operations decisions, like routing vehicles, using simple and well known heuristic methods mentioned in the literature. Using a case study, it is possible to show the benefits of changing an empirical routing method based on implicit knowledge towards an empirical application using fixed routes. In additional, is applied a dynamic routing method: the Clarke and Wright`s Method. Results are compared, and after that are recommended routine and tools development to use this application method, consistent and emphatically, in the company case study operation.

Orientador: Edson Luiz França Senne / Banca: José Roberto Dale Luche / Banca: Luiz Leduino Neto / Resumo: Neste trabalho propõe-se uma abordagem para o Problema de Balanceamento de Linhas de Montagem (do inglês, Assembly Line Balancing Problem - ALBP) para aumentar a eficiência de uma indústria montadora de veículos. O ALBP caracteriza-se como um problema de sequenciamento de tarefas em estações de trabalho classificado como um problema de Otimização Combinatória NP-difícil e, portanto, a solução exata do problema em ambientes reais geralmente implica em elevado custo computacional. Para resolver o ALBP, foram formulados um modelo matemático de otimização inteira mista para obtenção de soluções determinísticas e um modelo estocástico com recurso que considera a incerteza dos tempos de execução das tarefas pelos operadores. A motivação para o desenvolvimento do presente trabalho decorre da observação de interrupções constantes do fluxo de produção nesta indústria, atribuídas às mais diversas naturezas, e que causavam transtornos e elevados níveis de estresse aos trabalhadores. Ambos os modelos, determinístico e estocástico, aumentaram a capacidade de produção de 196 unidades/dia para 245 e 233 unidades/dia, respectivamente. O modelo estocástico aumentou o tempo de ciclo CT em 5,6% quando comparado ao modelo determinístico, embora diminua a capacidade efetiva em 4,8% Porém, não considerar a incerteza no tempo de execução das tarefas pode diminuir a quantidade produzida em até 10,6%. Contrariamente ao entendimento comum em linhas de montagem, este trabalho conclui que reduzir os tem... (Resumo completo, clicar acesso eletrônico abaixo) / Abstract: This work proposes solution approaches to the Assembly Line Balancing Problem (ALBP) to increase the efficiency of a vehicle assembler industry. The ALBP is characterized as a task sequencing in workstations which is classified as a NP-hard Combinatorial Optimization problem and, therefore, the exact solution of the problem in real environments usually implies a high computational cost. In order to solve the ALBP, a mathematical model of mixed integer optimization to obtain deterministic solutions and a stochastic model with resource that considers the uncertainty of the execution times of the tasks by the operators were formulated. The motivation for the development of this work stems from the constant interruptions of the production flow in this industry, attributed to the most diverse natures, which cause disorders and high levels of stress to the workers. The deterministic and stochastic models increased the production capacity from 196 units / day to 245 and 233 units / day, respectively. The stochastic model increased the cycle time by 5.6% when compared to the deterministic model, although it reduced the effective capacity by 4.8%, which is equivalent to 12 vehicles / day. However, not considering the uncertainty in task execution times can decrease the amount produced by up to 10.6% or 26 vehicles / day. Contrary to the most acceptable idea, this work concludes that reducing idle times to minimum levels is detrimental to assembly line productivity. This is due to the ... (Complete abstract click electronic access below) / Mestre

Made available in DSpace on 2016-12-23T14:33:34Z (GMT). No. of bitstreams: 1 dissertacao.pdf: 412800 bytes, checksum: 479ec97937646fdcffeadd81d19f1b7a (MD5) Previous issue date: 2006-06-01 / Computar a solução ótima para uma unidade de problema MAX-SAT Ponderado (weighted maximum satisfiability) é difícil mesmo se cada cláusula contiver apenas dois literais. Neste trabalho, será descrita a implementação de uma nova heurística aplicada a instâncias de problema do tipo MAX-SAT Ponderado, mas perfeitamente extensível a outros problemas. Para comparação, serão geradas soluções para uma quantidade significativa de problemas e seus resultados serão comparados com os de outras heurísticas já desenvolvidas para esse tipo de problema, dentre elas as heurísticas consideradas "estado da arte", ou seja, heurísticas que têm obtido os melhores resultados no universo das heurísticas existentes.

Orientador: Silvio Alexandre de Araújo / Banca: Reinaldo Morabito Neto / Banca: Franklina Maria Bragion de Toledo / Resumo: Este trabalho consiste numa extensão do estudo de um problema de dimensionamento de lotes com custo de transporte feito por Norden e Velde [53], onde a produção dos itens é transportada, em paletes, para um armazém. O transporte é feito por uma empresa terceirizada sob um contrato com os seguintes custos pré-estabelecidos: um custo fixo de contrato, um custo para o transporte de um determinado volume de paletes e um custo adicional para paletes extras. O problema foi estendido, no presente trabalho, considerando restrições de capacidade e a possibilidade de atrasos no atendimento a demanda. Nosso objetivo é propor um modelo matemático para o problema estendido e desenvolver dois métodos heurísticos de resolução. Tais métodos são baseados em dois tipos de relaxação: relaxação Lagrangiana e relaxação Lagrangiana/Surrogate. Os resultados obtidos pelas heurísticas são comparados com os resultados obtidos pelo pacote de otimização CPLEX 10.0. Além disso, é feita uma comparação entre os métodos heurísticos. / Abstract: This work consist of an extension of a study of the capacitated lot-sizing problems with transportation cost by Norden and Velde [53], where the production of itens is transported into pallets to an warehouse. The transportation is executed by another company, under a contract with the following transportation cost established: a fixed contract cost, a transportation cost for determined quantity of pallets and an additional cost for extra pallets. The problem was extended, in this work, considering capacity constraint and backlogging. Our objective is to propose a mathematical model for the extended problem and to develop two heuristics methods of resolution. The methods are based on two types of relaxation: Lagrangian relaxation and Lagrangian/Surrogate relaxation. The results obtained by heuristics are compared with the results obtained by CPLEX 10.0. Furthermore, a comparison between the heuristics is made. / Mestre

Orientador: Rubén Augusto Romero Lázaro / Banca: José Roberto Sanches Mantovani / Banca: Walmir de Freitas Filho / Resumo: O Problema do Planejamento da Expansão de Sistemas de Transmissão é um problema de otimização combinatória, cujo objetivo é buscar o atendimento de requisitos de cargas a custos mínimos de investimentos, percebendo um horizonte de longo prazo. A perspectiva do planejamento otimizado deve ser feita observando duas possiblidades: o planejamento estático e o planejamento multiestágio. No planejamento estático, o planjedor procura responder as questões onde e que tipos de elementos de transmissão precisam ser adicionados ou construídos para integrar a solução do sistema futuro. No entanto, quando a estratégia de expansão ótima abrange todo um período, o planejador deseja saber quando o circuito deve ser instalado, trata-se de um planejamento multiestágio. Em ambas alternativas, a resolução do problema do planejamento deve abranger duas etapas consecutivas: a modelagem matemática e a técnica de solução para resolver essa modelagem. Neste trabalho é apresentada uma proposta de planejamento estático utilizando aMetaheurística GRASP como técnica de solução para o problema do planejamento. / Abstract: The Problem of Expansion Planning of Transmission Systems is a combinatorial optimization problem whose goal is to seek the assistance of cargo requirements at minimal cost investment, realizing a long-term horizon.The prospect of planning should be optimized observing two possibilities: planning static and multistage planning. In planning static, designer seeks to answer the questions where and what types of transmission elements need to be added or built to integrate the solution of the future system. However, when the optimal expansion strategy covers the whole period, the planner wants to know when the circuit must be installed, it is a multistage planning. In both alternatives, solving the problem of planning should cover two consecutive steps: mathematical modeling and solution technique to solve this modeling.This work presents a planning proposal using the static technique as GRASP metaheuristic solution to the problem of planning. / Mestre

Orientador: Rubén Augusto Romero Lázaro / Banca: José Roberto Sanches Mantovani / Banca: Antonio Padilha Feltrin / Banca: Carlos Roberto Mendonça da Rocha / Banca: Edgar Manuel Carreño Franco / Resumo: Neste trabalho foi apresentado uma nova modelagem matemática para problemas de Planejamento da expansão de sistemas de transmissão ao longo prazo que permite uma mudança no conceito de expansão de sistema de transmissão. Nos problemas de planejamento da expansão de sistemas de transmissão tradicionais apenas as adições de linhas candidatas são consideradas. Neste trabalho um novo conceito de planejamento da expansão do sistema de transmissão é encontrar uma nova solução para a topologia base onde todas as linhas estão temporariamente desconectadas e a implementação dessas linhas são reconsideradas quando elas podem voltar à sua posição anterior. Portanto as linhas da topologia de base não será restabelecida se impedir o desempenho do sistema. Depois um novo problema é resolvido para encontrar o plano futuro da rede do sistema elétrico, com a adição de novas linhas de candidatas na topologia base modificada. A fim de encontrar um plano mais eficiente para a rede futura, a metodologia proposta é implementada usando a linguagem de modelagem para a programação matemática (AMPL) e solucionada usando o solver comercial CPLEX. A fim de validar a abordagem proposta e fazer alguma comparação com o método na literatura, três sistemas de testes são realizados, tais como: o sistema de 24-Bus IEEE teste com 41 linhas de candidatas, um estudos de casos práticos do sistema de 46-Bus do Sul do Brasil com 79 linhas de candidatas, e do sistema colombiano 93-Bus com 155 candidatas. Para sistemas de grande porte, a fim de facilitar a implementação do modelo matemático, uma estratégia é apresentada para reduzir o espaço de busca das barras em que a geração ou a demanda. Nos problemas de planejamento da expansão da transmissão geralmente nos deparamos com um problema de programação não-linear inteira mista (PNLIM) usando o modelo DC, o que torna impossível usar o solver linear ... / Abstract: In this work and in order to solve the long-term transmission expansion planning problems, a novel mathematical model which is based on a change in the concept of expanding a transmission system is presented. In traditional transmission system expansion planning, only the additions of candidate lines are considered. In this work, a new concept of transmission system expansion planning is to find a new solution for the base topology where all the lines are temporarily disconnected and the implementation of these lines are reconsidered when they may return to their previous position. Therefore, the lines of the base topology will not be reconnected if they prevent the system performance. Afterwards a new problem is solved to find the future plan of the electrical system network with the addition of new candidate lines in the modified base topology. In order to find a more efficient plan for the future network, the proposed methodology is implemented using a Modeling Language for Mathematical Programming (AMPL) and solved using the commercial solver of CPLEX. In order to validate the proposed approach and make some comparison with the method in the literature, three test systems are conducted such as: the 24-Bus IEEE test system with 41 candidate lines, a practical case studies of 46-Bus South Brazilian system with 79 candidate lines, and the 93-Bus Colombian system with 155 candidates. For large-scale systems, in order to facilitate the implementation of the mathematical model, a strategy to reduce the search space of the buses in which the generation or demand has been presented. In the transmission expansion planning problems, usually we face with a mixed integer non-linear programming problem (MINLP) using the DC model, which make it impossible to use the linear solver of CPLEX. The strategy to overcome this problem is using the disjunctive linear model, which is a DC linear equivalent model. The ... / Doutor

Orientador: Rubén Augusto Romero Lázaro / Banca: José Roberto Sanches Mantovani / Banca: Sergio Azevedo de Oliveira / Banca: Luis Gustavo Wesz da Silva / Banca: João Bosco Augusto London Junior / Resumo: Este trabalho aborda o problema de planejamento da expansão da rede de transmissão (PERT) e utiliza o modelo CC no horizonte de planejamento estático, em duas variações: com restrições de segurança N-1 (PERTES) e a formulação usual, sem restrições de segurança (PERTE). As meta-heurísticas busca tabu, GRASP e busca local iterada foram implementadas utilizando o framework ParadisEO e os parâmetros foram ajustados com auxílio do software paramILS. Os algoritmos foram testados em 42 sistemas teste divididos em 6 grupos de sistemas: Garver 6 barras (4 sistemas teste), IEEE 24 barras (10 sistemas teste), Sul Brasileiro 46 barras (4 sistemas teste), Sudeste Brasileiro 79 barras (4 sistemas teste), Nordeste Brasileiro 87 barras (8 sistemas teste) e Colombiano 93 barras (12 sistemas teste). Os testes verificaram a viabilidade de utilizar o framework ParadisEO para implementação de meta-heurísticas para o PERT. Além disso, foi criado um conjunto de informações de referência para utilização em trabalhos futuros com os problemas PERTE e PERTES / Abstract: This work deals with the energy network transmission expansion planning problem (TEP) and uses two variations of the CC model on the static planning horizon: with N-1 security constraints (STEPS) and the usual formulation, without security constraints (STEP). The meta-heuristics tabu search (TS), GRASP and iterated local search (ILS) were implemented using the framework ParadisEO and the parameters tunning were made with the aid of paramILS. The algorithms were tested in 42 test systems divided into 6 groups: Garver 6 bars (4 test systems), IEEE 24 bars (10 test systems), 46 South Brazilian bars (4 test systems), Brazilian Southeast 79 bars (4 test systems), Brazilian Northeast 87 bars (8 test systems) and Colombian 93 bars (12 test systems). The tests showed the viability of ParadisEO framework to implement meta-heuristics for the TEP problem. In addition, a large benchmark for use in future STEP and SSTEP works was created. / Doutor

Orientador: Silvio Alexandre de Araujo / Banca: Maria do Socorro Nogueira Rangel / Banca: Kelly Cristina Poldi / Banca: Sonia Cristina Poltroniere Silva / Banca: Deisemara Ferreira / Resumo: Nesta tese, estamos interessados em tratar de maneira integrada dois conhecidos problemas da literatura. Esta integração é referida na literatura como problema integrado de dimensionamento de lotes e corte de estoque. A ideia consiste em considerar simultaneamente, as decisões relacionadas com ambos os problemas, de modo a capturar a interdependência entre estas decisões e, assim, obter uma melhor solução global. Propõe-se um modelo matemático geral para o problema integrado de dimensionamento de lotes e corte de estoque (GILSCS), que considera vários níveis de integração e nos permite classificar a literatura, em termos de modelos matemáticos, dos problemas integrados. A classificação é organizada a partir de dois principais aspectos de integração que são: a integração através dos períodos de tempo e a integração entre os níveis de produção. Em um horizonte de planejamento que considera vários períodos, o estoque fornece uma ligação entre os períodos. Esta integração, por períodos de tempo, constitui o primeiro tipo de integração. O problema geral também considera a produção em diferentes níveis: objetos são fabricados ou comprados e então são cortados para produzir peças menores e estas, por sua vez, constituem componentes para a produção dos produtos finais. A integração entre os diferentes níveis de produção consiste no segundo tipo de integração. A revisão da literatura também possibilita direcionar interessantes áreas para pesquisas futuras. O comportamento da solução... / Abstract: In this thesis, the subject of interest is in treating, in an integrated way, two wellknown problems in the literature. This integration is referred in the literature as the integrated lot-sizing and cutting stock problem. The basic idea is to consider, simultaneously, the decisions related to both problems so as to capture the interdependency between these decisions in order to obtain a better global solution. We propose a mathematical model for a general integrated lot-sizing and cutting stock (GILSCS) problem. This model considers multiple dimensions of integration and enables us to classify the current literature, in terms of mathematical models, in this field. The main classification of the literature is organized around two types of integration. In a planning horizon which consists of multiple periods, the inventory provides a link between the periods. This integration across time periods constitutes the first type of integration. The general problem also considers the production in different levels: objects are fabricated or purchased and then, they are cut to produce the pieces which are then assembled as components in the production of final products. The integration between these production levels constitutes the second type of integration. The literature review also enables us to point out interesting areas for future research. The behavior of a solution to this type of problem, with three levels of production and several time periods, is studied considering the ... / Doutor

Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro Tecnológico / Made available in DSpace on 2012-10-18T04:39:43Z (GMT). No. of bitstreams: 0Bitstream added on 2013-07-16T18:20:37Z : No. of bitstreams: 1 179212.pdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / O Problema de Alocação de Veículos (VSP - Vehicle Scheduling Problem) consiste em atribuir veículos a um conjunto predeterminado de viagens, com horários de saída e chegada fixos, minimizando os custos operacionais. O objetivo desta pesquisa é comparar a eficiência de algumas técnicas heurísticas para a solução do VSP, e em particular a aplicação da metaheurística denominada Busca Local Dirigida (BLD) quando aplicada sobre soluções iniciais obtidas com as heurísticas pesquisadas. BLD é um método geral, baseado em penalidades, as quais são utilizadas no algoritmo de busca local, para ajudar a guiar a busca para fora de mínimos locais. A técnica opera aumentando a função objetivo com as penalidades. O método BLD foi aplicado para duas funções objetivas distintas, uma baseada em custo e a outra em tempo, utilizando como soluções iniciais as soluções obtidas pelo método de programação concorrente e o método de atribuição. Uma importante contribuição deste trabalho é o estudo computacional que compara a metaheurística com as soluções iniciais citadas, utilizando dados reais e custos fictícios. As conclusões são apresentadas sobre a qualidade dos resultados e sugestões para trabalhos futuros são comentadas