Nessa dissertação apresentamos um problema de programação da produção, motivado por uma indústria alimentícia caracterizada pela perecibilidade dos produtos, sequenciamento da produção dos lotes e pela necessidade de sincronização de recursos escassos para operação das linhas de produção. Em indústrias desse ramo, existem altos custos associados a estocagem dos produtos, a fim de evitar sua perda, de modo que é essencial a boa gestão dos processos industriais e do estoque. Modelos matemáticos de programação inteira mista foram desenvolvidos para tratar o problema, bem como o estudo da inclusão de diversas restrições da literatura para o tratamento da perecibilidade. Testes computacionais foram realizados para as validações dos modelos matemáticos, entretanto, devido à dificuldade de determinar soluções de boa qualidade pelo solver de otimização, foram propostos métodos heurísticos baseados na formulação matemática. Com o objetivo de mostrar o desempenho das heurísticas, comparamos as suas performances na resolução de instâncias da literatura e exemplares baseados no cenário produtivo da indústria com os resultados do solver. / In this dissertation we present a lot sizing and scheduling problem motivated by a food industry characterized by the perishability of the products, sequencing the production of the lots and by the need of synchronization of scarce resources for the operation of the production lines. In this type of industry, there are high costs associated with stocking the products in order to avoid their loss, so that good management of industrial processes and inventory is essential. Mathematical models of mixed integer programming were developed to treat the problem, as well as the study of the inclusion of several restrictions of the literature for the treatment of perishability. Computational tests were performed for the validations of the mathematical models, however, due to the difficulty of determining solutions of good quality by the optimization solver, heuristic methods based on the mathematical formulation were proposed. In order to show the performance of the heuristics, we compare their performances in solving instances of the literature and exemplars based on the productive scenario of the industry with the results of solver.

O setor de fundições é importante para a economia, pois produz componentes básicos para muitos outros setores, de modo que seu bom desempenho tem repercussão nos demais. Um modelo de programação inteira mista para uma fundição de mercado de pequeno porte, que visa principalmente minimizar atrasos na entrega dos pedidos, foi proposto na literatura. Neste trabalho é feito um estudo do modelo e é proposta uma nova abordagem, independente de qualquer software comercial, baseada na decomposição do problema em dois subproblemas: o planejamento da produção das ligas e o planejamento da produção dos itens. Ambos foram resolvidos por uma heurística lagrangiana baseada em transferêrencias. Testes computacionais mostraram que a abordagem proposta é capaz de gerar soluções de boa qualidade, em tempo computacional aceitável / The foundry sector is important to the economy as it produces basic components for many other sectors, to such an extent that its performance has a repercussion in other sectors. A recently published mixed integer-programming model for small market-driven foundries, which aims to minimize delays when delivering orders, was proposed in the literature. In this work, a study of this model was undertaken and a new approach is put forward, regardless of any commercial software, based on dealing with the problem in two sub problems: production planning of alloys and production planning of items. Both sub problems were solved by a Lagrangian heuristic based on transfers. Computational tests show that the approach proposed is able to generate solutions of good quality in acceptable computational time

O problema de dimensionamento de lotes determina um plano de produção que apoia às tomadas de decisões, a médio prazo, em meios industriais. Este plano de produção indica as quantidades de cada item que devem ser produzidas em cada período do horizonte de planejamento, de acordo com um objetivo dado e satisfazendo a demanda dos clientes. Diversos métodos de solução foram propostas na literatura, considerando a dificuldade de solução de algumas classes de problemas e a necessidade de métodos que gerem soluções de alta qualidade em um tempo computacional adequado. Neste trabalho, abordamos heurísticas baseadas na formulação matemática (LP-and-fix, relax-and-fix e fix-and-optimize), uma metaheurística (algoritmo de abelhas) e dois métodos híbridos, utilizados na solução de dois problemas distintos de dimensionamento de lotes multiestá- gio com limitação de capacidade. Consideramos também, a utilização de três formulações da literatura, para verificar a influência de cada uma sobre as abordagens de solução verificadas. Os resultados computacionais demonstraram que os métodos baseados na formulação matemática do problema se mostraram eficientes, mas limitados normalmente a ótimos locais, enquanto os métodos híbridos puderam superar estes ótimos locais, utilizando conceitos da metaheurística algoritmo de abelhas para isto. Além disso, pudemos verificar a influência de uma formulação \"forte\" sobre as soluções geradas pelas abordagens de solução, demonstrando que métodos baseados em relaxação linear conseguem obter maiores vantagens deste tipo de formulação, mas outras abordagens podem ou não obter estas vantagens, dependendo do problema abordado / The lot-sizing problem determines a production plan, which supports the decision making, in the medium term, at the industrial environment. This production plan indicates the amounts of each item to be produced in each period of the planning horizon, according to a given objective and satisfying customer\'s demand. Diverse solution methods have been proposed in the literature, considering the difficulty of solving some problem classes and the need of methods to generate solutions quickly. In this work, we develop matheuristics (LP-and-fix, relax-and-fix and fix-and-optimize), one metaheuristic (bees algorithm) and two hybrid methods, used to solve two different multilevel capacitated lot-sizing problems. We also consider the use of three different formulations of the literature to verify the influence of each one on the solutions approaches. The computational results show that the matheuristics proved to be efficient, but usually limited to local optima, while the hybrid methods could escape from these local optima, using concepts of bees algorithm to do this. Additionally, we test the effect of a tight formulation on the solutions approaches, demonstrating that LP-based heuristics can obtain further advantages from this type of formulation, but other approaches can take these advantages, depending on the problem addressed

Neste trabalho, abordamos métodos de resolução para o problema de dimensionamento de lotes que contempla o planejamento da produção de vários produtos em múltiplas máquinas. A fabricação dos produtos consome tempo de produção e preparação de uma capacidade de produção limitada. A demanda pelos produtos é conhecida e pode ser atendida com atraso durante um horizonte de planejamento finito. O objetivo é minimizar a soma dos custos de produção, preparação para a produção, estoque dos produtos e atraso na entrega destes. Em uma primeira etapa, desenvolvemos uma busca tabu determinística baseada em outra, aleatória, que foi apresentada na literatura. Com isso, realizamos uma análise sobre a influência de fatores aleatórios sobre heurísticas do tipo busca tabu quando aplicadas ao problema estudado. Posteriormente, desenvolvemos um método híbrido baseado em busca tabu, branch-and-cut e programação linear para a resolução do problema. Nos testes computacionais realizados, o método proposto mostrou-se competitivo quando comparado a outras heurísticas apresentadas na literatura / This paper proposes two methods to solve the capacitated lot-sizing problem with multiple products and parallel machines. The manufacturing of products consumes machines capacity (production time and setup time), which is scarce. The demand for the products is known and can be met with backlogging. The objective is to minimize the sum of production, setup, holding and backlog costs. In a first step, we developed a deterministic tabu search heuristic based on a random version from the literature and then conducted an analysis of the influence of random factors on tabu search heuristics when applied to solve the studied problem. Subsequently, we designed a hybrid method based on tabu search, branch-andcut and linear programming. Computational experiments show that this hybrid method is competitive with other heuristics presented in the literature

A indústria de fundição produz uma vasta gama de itens com presença na cadeia produtiva de vários setores da economia. São gerados pelo setor, desde itens simples de uso doméstico até itens sofisticados, utilizados por indústrias de base e pelo setor de autopeças. Por ser um segmento muito importante para a economia brasileira, estudos visando melhorar sua eficiência são fundamentais para assegurar sua competitividade em relação ao cenário mundial. Segundo a literatura, um dos principais fatores que influenciam sua produtividade é o planejamento da produção. Nos últimos anos, os investimentos nesta área vem aumentando e tem recebido mais atenção do ponto de vista acadêmico. Esta dissertação aborda o planejamento da produção em fundições de pequeno porte, cujas principais decisões são: decidir quais ligas fundir nos fornos disponíveis e quais itens devem ser vazados a partir das ligas fundidas. Uma questão ainda não considerada na literatura é a obrigatoriedade de completar a produção de todos os itens de um pedido para que este seja considerado atendido e entregue ao cliente. No entanto, em muitos casos reais, um pedido não pode ser atendido parcialmente, ou seja, os itens que compõem esse pedido podem fazer parte de um mesmo item final. Em outros casos, o pedido pode ser atendido parcialmente, mas incorre-se em custos adicionais de expedição. Esta dissertação busca preencher esta lacuna, para tanto, propomos: (1) um modelo matemático para tratar o problema de planejamento da produção de pedidos em fundições de pequeno porte; (2) um modelo para tratar a possibilidade de múltiplas entregas para o problema estudado. Além disso, também é proposta uma heurística Relax-and Fix (relaxe-e-fixe) para a solução do problema integrado / The foundry industry produces plenty of different items present in various sectors of the economy. Such items range from simple household gadgets to sophisticated devices used by basic industries and the auto parts sector. This industry is important for the Brazilian economy and studies aiming at the improvement of its efficiency are fundamental to ensure its competitiveness worldwide. As highlighted in the literature, an important factor that influences the production in the sector is the produiction planning.; In recent years, the investments in this area have been increasing and more attention has been drawn by academic studies. This dissertation deals with the production planning in small foundries, whose major decisions are the determination of the alloys to the merged and items to be produced. A question that still has not considered in the literature is the obligation to complete the production of the orders to be delivered to the client. However, in many real cases, an order cannot bi partially delivered, that is, the pieces, which are parts of the order, may be pats of the final product. In other cases, the order may be partially delivered, but with additional expedition costs. In this dissertation the objective is close that question, so we propose: (1) a mathematical model for production-planning problem of complete orders for small foundry industry; (2) a mathematical model to treat the possibility of partial delivery to the sama problem. Furthermore, we proppose a Relax-and-Fix heuristic for the integrated model

Orientador: Silvio Alexandre de Araujo / Coorientadora: Adriana Cristina Cherri / Banca: Sonia Cristina Poltrooniere Silva / Banca: Roberto Fernandes Tavares Neto / Resumo: Dois problemas fundamentais surgem no planejamento da produção de muitos processos produtivos: o problema de dimensionamento de lotes e o problema de corte de estoque. Geralmente, as empresas tratam estes problemas separadamente, porém, ao considerá-los de maneira integrada, é possível obter melhores resultados. Neste trabalho, investiga-se o problema integrado de dimensionamento de lotes e corte de estoque tridimensional aplicado a uma indústria de colchões, visando à redução de custos e desperdícios. É proposto um modelo matemático de programação inteira mista para a resolução do problema. Testes computacionais com base em dados coletados em uma indústria do setor foram realizados, permitindo comparar as soluções obtidas pelo modelo e as soluções adotadas pela indústria. Testes adicionais foram realizados com dados aleatórios, a fim de avaliar o comportamento do modelo para diferentes casos. Os resultados indicam que o modelo apresenta um bom desempenho, reduzindo os custos da função objetivo para diferentes conjuntos de testes. Com base nos resultados, algumas direções interessantes podem ser exploradas pela indústria, como por exemplo, ao aumentar o número de padrões de corte, aumenta-se o número de combinações possíveis para o corte, resultando em melhor aproveitamento de material e redução nos custos. / Abstract: Two fundamental problems arise in the production planning of many productive processes: the lot-sizing problem and the cutting stock problem. Generally, companies deal with these problems separately, but by considering them in an integrated way, it is possible to obtain better results. In this paper, the integrated lot-sizing and three-dimensional cutting stock problem applied to a mattress industry is investigated, aiming at reducing costs and waste. It is proposed a mathematical model of mixed integer programming for the problem resolution. Computational tests based on data collected in an industry of the sector were carried out, allowing to compare the solutions obtained by the model and the solutions adopted by the industry. Additional tests were performed with random data in order to evaluate the behaviour of the model for different cases. The results indicate that the model performs well, reducing the objective function costs for different sets of tests. Based on the results, some interesting directions can be explored by the industry, for example, by increasing the number of cutting patterns, the number of possible combinations for cutting is increased, resulting in better material utilization and reduction in costs. / Mestre

Made available in DSpace on 2014-06-11T19:22:18Z (GMT). No. of bitstreams: 0 Previous issue date: 2001-02-17Bitstream added on 2014-06-13T19:07:26Z : No. of bitstreams: 1 fiorotto_dj_me_sjrp.pdf: 485977 bytes, checksum: 8cd2b3ba49a25a9c6a863795f27811c3 (MD5) / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / O problema de dimensionamento de lotes é um problema de otimização da produção, em que o objetivo é planejar a quantidade de itens a ser produzida em várias, ou única, máquinas em cada período ao longo do horizonte de tempo, de modo a tender uma demanda e otimizar uma função objetivo. Este trabalho aborda o problema de dimensionamento de lotes em um único estágio em um ambiente com máquinas paralelas distintas. Cada item pode ser produzido em qualquer máquina, acarretando um tempo de preparação que é gasto antes de começar a produção. O objetivo do trabalho consiste em obter limitantes inferiores de boa qualidade para este problema. Para tanto, é desenvolvido um método de solução baseado numa reformulação do problema a e na relaxação lagrangiana de um conjunto de restrições. Alguns resultados computacionais são apresentados algumas propostas futuras para a continuidade do trabalho. / The lot-sizing problem is a production optimization problem, where the objective is to plan the quantity of items to be produced in multiple, or single, machines in each period over a time horizon, in order to satisfy a demand and optimize an objective function. This work addresses the single stage parallel machine lot-sizing problem. Each item can be produced on any machine, and incur a setup time before to start the production. The objective of this work is to lower bounds of good quality for this problem. A solution method is developed based on a reformulation of the problem and the Lagrangian relaxation of a set of constrainsts. Some computational results are presented comparing the proposed method with a method from the literature, and, some future researches are proposed.

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

O setor de fundições é importante para a economia, pois produz componentes básicos para muitos outros setores, de modo que seu bom desempenho tem repercussão nos demais. Um modelo de programação inteira mista para uma fundição de mercado de pequeno porte, que visa principalmente minimizar atrasos na entrega dos pedidos, foi proposto na literatura. Neste trabalho é feito um estudo do modelo e é proposta uma nova abordagem, independente de qualquer software comercial, baseada na decomposição do problema em dois subproblemas: o planejamento da produção das ligas e o planejamento da produção dos itens. Ambos foram resolvidos por uma heurística lagrangiana baseada em transferêrencias. Testes computacionais mostraram que a abordagem proposta é capaz de gerar soluções de boa qualidade, em tempo computacional aceitável / The foundry sector is important to the economy as it produces basic components for many other sectors, to such an extent that its performance has a repercussion in other sectors. A recently published mixed integer-programming model for small market-driven foundries, which aims to minimize delays when delivering orders, was proposed in the literature. In this work, a study of this model was undertaken and a new approach is put forward, regardless of any commercial software, based on dealing with the problem in two sub problems: production planning of alloys and production planning of items. Both sub problems were solved by a Lagrangian heuristic based on transfers. Computational tests show that the approach proposed is able to generate solutions of good quality in acceptable computational time

Este texto trata de um dos temas fundamentais no planejamento de produção, o problema de dimensionamento de lotes de um único item. Uma descrição sucinta e informal do problema segue abaixo. Considere um intervalo de tempo dividido em períodos e que a cada período de tempo está associada a demanda de um item. Dados os custos e as eventuais restrições na produção e no armazenamento, determine os períodos em que se produzirá e em que quantidade para que as demandas sejam atendidas com o menor custo possível, respeitando as restrições impostas. Apresentamos aqui resultados sobre a estrutura ótima do problema, sobre complexidade e algoritmos para os casos básicos do problema / This text studies one of the core subjects in production planning, the single-item lot-sizing problem. A brief and informal description of this problem follows below. Considering a time interval split into time periods and that there is a demand of an item associated with each time period. Given production and holding costs and possibly production and holding restrictions, determine in which periods the production must occur and in which quantity, in order to attend the demands with a minimum cost, without violate any restriction. Here, it will be shown some results about the optimal structure of the problem, about the complexity and algorithms for the simpler cases