Esta tese aborda um problema de dimensionamento e sequenciamento de lotes de produção baseado em uma indústria alimentícia brasileira que opera por meio de diversas linhas de produção heterogêneas. Nesse ambiente produtivo, as linhas de produção compartilham recursos escassos, tais como, trabalhadores e máquinas e devem ser montadas (ativadas) em cada período produtivo, respeitando-se a capacidade disponível de cada recurso necessário para ativação das mesmas. Modelos de programação matemática inteira mista são propostos para representação do problema, bem como diversos métodos heurísticos de solução, compreendendo procedimentos construtivos e de melhoramento baseados na formulação matemática do problema e heurísticas lagrangianas. São propostas heurísticas do tipo relax-and-fix explorando diversas partições das variáveis binárias dos modelos e uma heurística baseada na decomposição do modelo para construção de soluções. Procedimentos do tipo fix-and-optimize e matheuristics do tipo iterative MIP-based neighbourhood search são propostas para o melhoramento das soluções iniciais obtidas pelos procedimentos construtivos. Testes computacionais são realizados com instâncias geradas aleatoriamente e mostram que os métodos propostos são capazes de oferecer melhores soluções do que o algoritmo Branch-and-Cut de um resolvedor comercial para instâncias de médio e grande porte. / This doctoral dissertation addresses the simultaneous lot sizing and scheduling problem in a real world production environment where production lines share scarce production resources. Due to the lack of resources, the production lines cannot operate all simultaneously and they need to be assembled in each period respecting the capacity constraints of the resources. This dissertation presents mixed integer programming models to deal with the problem as well as various heuristic approaches: constructive and improvement procedures based on the mathematical formulation of the problem and lagrangian heuristics. Relax-and-fix heuristics exploring some partitions of the set of binary variables of a model and a decomposition based heuristic are proposed to construct solutions. Fix-and-optimize heuristics and iterative MIP-based neighbourhood search matheuristics are proposed to improvement solutions obtained by constructive procedures. Computational tests are performed with randomly instances and show that the proposed methods can find better solutions than the Branch-and-Cut algorithm of a commercial solver for medium and large size instances.

Orientador: Silvio Alexandre de Araujo / Coorientador: Diego Jacinto Fiorotto / Banca: Kelly Cristina Poldi / Banca: Victor C. B. de Camargo / Resumo: Os problemas de dimensionamento de lotes consistem em determinar a quantidade de itens que devem ser produzidos em todos os períodos de um horizonte de planejamento. Em geral, são considerados custos de produção, preparação de máquina e de manutenção de estoque. Neste trabalho estuda-se uma extensão do problema de dimensionamento de lotes com restrição de capacidade que considera tempos de preparação, preparação carryover e crossover, em que se tem uma única máquina, único estágio, multi-itens e big-bucket (CLSP-SCC). Novas formulações para o CLSP-SCC são apresentadas e evitam a necessidade de definir novas variáveis binárias para modelar a preparação crossover. Também são propostas restrições de quebra de simetria para formulações propostas na literatura. São provadas as relações teóricas que existem entre cada uma destas formulações estudadas. Além disso, é proposta uma heurística híbrida que combina as heurísticas Relax-and-Fix e Fix-and-Optimize (RF-FO), em que a heurística Relax-and-Fix é usada para obter uma solução inicial e a heurística Fix-and-Optimize melhora essa solução. Por fim, apresentam-se os resultados computacionais e conclui-se que os resultados obtidos melhoram significativamente quando comparam-se a formulação clássica com as formulações sem preparação carryover. Compara-se também os resultados da heurística com os do pacote computacional CPLEX e, quando ambos são limitados ao mesmo tempo computacional, a heurística RF-FO obtém melhores resultados / Abstract: Lot-Sizing Problems consist of determining the quantity of items to be produced in each period of a planning horizon. In general, production, setup and inventory costs are considered. In this work an extension of the Capacitated Lot-Sizing Problem is studied, which considers setup times, Setup Carryover and Setup Crossover, single machine, single level, multi items, multi periods and big-bucket (CLSP-SCC). New formulations to the CLSP-SCC are presented and avoid the necessity of defining new extra binary variables to model the setup crossover. Furthermore, symmetry breaking constraints are proposed for formulations from the literature. The theoretical relations between the studied formulations are proved. A Relax-and-Fix and Fixand-Optimize (RF-FO) hybrid heuristic is proposed, in which the Relax-and-Fix helps to find an initial solution and the Fix-and-Optimize improves it. Computational results are presented and the obtained results improve significantly when comparing the classical formulation with the formulation without setup carryover. Finally, the results obtained by the RF-FO heuristic and the computational package CPLEX are compared and, when they both are limited to the same computational time, the RF-FO heuristic obtains better results / Mestre

Made available in DSpace on 2014-06-11T19:26:55Z (GMT). No. of bitstreams: 0 Previous issue date: 2010-02-23Bitstream added on 2014-06-13T20:55:42Z : No. of bitstreams: 1 defalque_cm_me_sjrp.pdf: 681826 bytes, checksum: 4534893f3d08420f599caa3a4835df06 (MD5) / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / Neste trabalho, propomos um modelo integrado de dimensionamento de lotes e programação da produção para uma fábrica de refrigerantes de pequeno porte denominado P1S1MTS. Neste modelo, as decisões de dimensionamento foram baseadas no modelo P1S1M encontrado na literatura, formulado com base no modelo GLSP. As decisões de sequenciamento foram modeladas utilizando restrições do problema do caixeiro viajante assimétrico. Para validação do modelo proposto e comparação entre os modelos P1S1MTS e P1S1M foram feitos testes computacionais com exemplares ilustrativos. Foram realizados também testes com exemplares baseados em dados reais da fábrica de refrigerantes e exemplares gerados aleatoriamente. Os testes foram resolvidos pelo método Branch-and-Cut incluído no pacote computacional CPLEX 10.0. Notamos que com algumas modificações, é possível que ambos os modelos retratem a mesma situação. A partir destas modificações e com os resultados obtidos, concluímos que a resolução de exempalres do modelo P1S1MTS apresentou um tempo de execução computacioanl menor que a resolução de exemplares do modelo P1S1M gerados com os mesmos dados. / In this work we propose a lot sizing and scheduling model, P1S1MTS, for a smallscale soft drink plant. In this model, the lot sising decisions were based on the P1s!m model found in the literaure. To model the scheduling decisions constraints of the asynmetric traveling salesman problem are used. For the validation of the proposed model and a comparison between the P1S1MTS and the P1S1M models computational tests were executed with illustratuve examples. Tests were also executed with examples based on real data and randomly generated instances. Tests were also executed with examples based on real data and randomly in the software CPLEX 10.0. The results showed taht, with some minor modifications, it is possible that both models depict same situation. From the results obtained we concluded that the P1s!MTS model presented a computational time performance better than the P1S1M model.

Made available in DSpace on 2014-06-11T19:27:55Z (GMT). No. of bitstreams: 0 Previous issue date: 2007-03-23Bitstream added on 2014-06-13T19:15:35Z : No. of bitstreams: 1 silva_fm_me_sjrp.pdf: 817059 bytes, checksum: eb6c0e0e69f3687d3831dbbbc3cf6e09 (MD5) / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / 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. / 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.

Made available in DSpace on 2016-06-02T19:51:23Z (GMT). No. of bitstreams: 1 DissEAVT.pdf: 1007944 bytes, checksum: 161890ccd40c1109dd2342d0421e9add (MD5) Previous issue date: 2003-01-01 / Universidade Federal de Minas Gerais / The object of this work is the integrated problem of lot sizing and sequencing the production of feed for animal nutrition. Such problem consists of deciding how much to produce of each feed in each period, taking itself in account the production sequencing of the lots, in way to satisfy the demand and to minimize the costs of production and storage. A case study was carried through in the facility of supplements from a company of this industry, located inland São Paulo, whose problem can be seen as multi-item, single-period and capacitated. One of the great difficulties to the production planning in this factory is the difficulty to adjust the productive capacity with the demand is season of the products, integrating the lot sizing decisions with the line scheduling decisions, since setup times are dependent of the production sequence. This work use integer linear programming for modeling the problem, which is solved with of the modeling language GAMS/CPLEX. To evaluate the performance of the considered model tests with real data had been carried through. The results show that the model can be useful to support the decisions of lot sizing and sequencing, therefore the solutions of the model in the tests realized are better than the ones elaborated by the production planning department of the company. / O objeto deste trabalho é o problema integrado de dimensionamento de lotes e sequenciamento da produção de rações para nutrição animal. Tal problema consiste em decidir quanto produzir de cada ração em cada período, levando-se em conta a seqüência de produção dos lotes, de maneira a satisfazer a demanda e minimizar os custos de produção e estocagem. Um estudo de caso foi realizado na unidade de suplementos de uma empresa do setor, localizada no interior de São Paulo, cujo problema pode ser visto como multi-item, monoestágio e capacitado. Uma das grandes dificuldades para o planejamento da produção nesta indústria é a dificuldade de ajustar a capacidade produtiva a sazonalidade da demanda dos produtos, integrando as decisões de dimensionamento dos lotes e as decisões de sequenciamento, uma vez que os tempos de preparação (setup) são dependentes da seqüência produtiva. Neste trabalho utiliza-se um modelo de programação linear inteira para tratar o problema, que é resolvido por meio de linguagem de modelagem GAMS/ CPLEX. Para avaliar o desempenho do modelo foram realizados testes com dados reais. Os resultados obtidos mostram que o modelo pode ser útil para apoiar as decisões de dimensionamento e seqüenciamento de lotes, pois os resultados do modelo nos testes realizados foram melhores que os elaborados pelo planejamento da empresa.

Esta tese aborda um problema de dimensionamento e sequenciamento de lotes de produção baseado em uma indústria alimentícia brasileira que opera por meio de diversas linhas de produção heterogêneas. Nesse ambiente produtivo, as linhas de produção compartilham recursos escassos, tais como, trabalhadores e máquinas e devem ser montadas (ativadas) em cada período produtivo, respeitando-se a capacidade disponível de cada recurso necessário para ativação das mesmas. Modelos de programação matemática inteira mista são propostos para representação do problema, bem como diversos métodos heurísticos de solução, compreendendo procedimentos construtivos e de melhoramento baseados na formulação matemática do problema e heurísticas lagrangianas. São propostas heurísticas do tipo relax-and-fix explorando diversas partições das variáveis binárias dos modelos e uma heurística baseada na decomposição do modelo para construção de soluções. Procedimentos do tipo fix-and-optimize e matheuristics do tipo iterative MIP-based neighbourhood search são propostas para o melhoramento das soluções iniciais obtidas pelos procedimentos construtivos. Testes computacionais são realizados com instâncias geradas aleatoriamente e mostram que os métodos propostos são capazes de oferecer melhores soluções do que o algoritmo Branch-and-Cut de um resolvedor comercial para instâncias de médio e grande porte. / This doctoral dissertation addresses the simultaneous lot sizing and scheduling problem in a real world production environment where production lines share scarce production resources. Due to the lack of resources, the production lines cannot operate all simultaneously and they need to be assembled in each period respecting the capacity constraints of the resources. This dissertation presents mixed integer programming models to deal with the problem as well as various heuristic approaches: constructive and improvement procedures based on the mathematical formulation of the problem and lagrangian heuristics. Relax-and-fix heuristics exploring some partitions of the set of binary variables of a model and a decomposition based heuristic are proposed to construct solutions. Fix-and-optimize heuristics and iterative MIP-based neighbourhood search matheuristics are proposed to improvement solutions obtained by constructive procedures. Computational tests are performed with randomly instances and show that the proposed methods can find better solutions than the Branch-and-Cut algorithm of a commercial solver for medium and large size instances.

Este trabalho trata de um problema de programação da produção em fundições de pequeno porte, que consiste em programar as ligas que devem ser produzidas em cada período do planejamento e como tais ligas devem ser usadas para a produção de itens sob encomenda, de modo que atrasos e custos operacionais sejam minimizados. Devido à certa incerteza nos dados do problema, a estratégia de horizonte rolante foi empregada. Este problema é representado por um modelo matemático de programação linear inteira mista. Neste trabalho foi desenvolvida uma heurística do tipo residual para obter uma boa solução inteira factível do problema, partindo da solução contínua encontrada pelos métodos relaxe-e-fixe e busca local / This work addresses a planning production problem that arises in small market-driven foundries, which consists of programming a number of alloys that have to be produced in each period of the planning horizon and how these alloys should be used to producing ordered items, in such way that delays and operational costs are minimized. Due to uncertainties in the problem data, the strategy of rolling horizon was used. This problem is modeled as a mixed integer linear programe. In this work we developed a residual typed heuristic in order to obtain a good feasible integer solution of the problem, which are built from the continuous solution found by relax-and-fix and local search methods. Keywords: Lot-sizing problems, mixed integer linear programming, production planning in foundries

Neste trabalho, apresentamos um estudo sobre o problema de dimensionamento de lotes com múltiplas plantas, múltiplos itens e múltiplos períodos. As plantas têm capacidade de produção limitada e a fabricação de cada produto incorre em tempo e custo de preparação de máquina. Nosso objetivo é encontrar um plano de produção que satisfaça a demanda de todos os clientes, considerando que a soma dos custos de produção, de estoque, de transporte e de preparação de máquina seja a menor possível. Este trabalho tem duas contribuições centrais. Primeiramente, propomos a modelagem do problema de dimensionamento de lotes com múltiplas plantas utilizando o conceito de localização de facilidades. Para instâncias de pequena dimensão, os testes computacionais mostraram que a resolução do problema remodelado apresenta, como esperado, resultados melhores que o modelo original. No entanto, seu elevado número de restrições e de variáveis faz com que as instâncias de maiores magnitudes não consigam ser resolvidas. Para trabalhar com instâncias maiores, propomos um método híbrido (math-heurística), que combina o método relax-and-fix, com a restrição de local branching. Testes computacionais mostram que o método proposto apresenta soluções factíveis de boa qualidade para estas instâncias / In this work, we present a study about the multi-plant, multi-item, multi-period lot-sizing problem. The plants have limited capacity, and the production of each item implies in setup times and setup costs. Our objective is to find a production plan which satisfies the demand of every client, considering that the sum of the production, stocking, transport and setup costs is the lowest possible. This work has two main contributions. Firstly, we propose the multi-plant lot-sizing problem modeling using the facility location concept. For small dimension problems, computational tests showed that the remodeled problem resolution presents, as expected, better results than the original model. However, the great number of restrictions and variables make bigger instances to be intractable. To work with the bigger dimension instances, we propose a hybrid method (math-heuristic), which combines the relax-and-fix method and the local branching restriction. Computational tests show that the proposed math-heuristic presents good quality feasible solutions for these instances

Um importante problema de programação da produção surge em indústrias de papel integrando o problema de planejamento em múltiplas máquinas paralelas com o problema de corte. O problema de dimensionamento de lotes deve determinar a quantidade de jumbos (bobinas grandes de papel) de diferentes tipos de papel a serem produzidos em cada máquina. Estes jumbos são então cortados para atender a demanda de itens (bobinas menores de papel). O planejamento, que minimiza custos de produção e preparação, deve produzir jumbos (cada máquina produz jumbos de larguras diferentes) que diminuam a perda no processo de corte. Por outro lado, o melhor número de jumbos do ponto de vista de minimizar a perda no processo de corte pode acarretar em altos custos de preparação. Ambos são problemas de otimização combinatória não trivial, o que tem motivado extensas pesquisas nas últimas décadas, entretanto, essa combinação não é bem explorada na literatura. Neste trabalho, são propostos um modelo de otimização integrado e métodos heurísticos de solução. Foram realizados experimentos computacionais com o intuito de analisar o desempenho dos métodos propostos e os resultados apresentaram- se bastante satisfatórios, significando que tais métodos são apropriados para tratar o problema integrado. / An important production programming problem arises in paper industries coupling mul- tiple machine scheduling with cutting stock. From machine scheduling the problem of determining the quantity of jumbos (large rolls of paper) of different types of paper to be produced in each machine arises. These jumbos are then cut to meet the demand for items (smaller rolls of paper). Scheduling that minimizes setups and production costs may produce jumbos (each machine produces jumbos of a specific width) which may increase waste in the cutting process. On the other hand, the best number of jumbos in the point of view of minimizing waste in the cutting process may lead to high setup costs. Both problems are non-trivial combinatorial optimization problems, which have motivated ex- tensive research in the last decades, however their combination is not well explored in the literature. In this work, a coupled optimization modelling and heuristic solution methods are proposed. Computational experiments are devised in order to analyze the performance of the methods and the results had been presented sufficiently satisfactory, meaning that such methods are appropriate to deal with the integrated problem.

Um importante problema de programação da produção surge em indústrias de papel integrando o problema de planejamento em múltiplas máquinas paralelas com o problema de corte. O problema de dimensionamento de lotes deve determinar a quantidade de jumbos (bobinas grandes de papel) de diferentes tipos de papel a serem produzidos em cada máquina. Estes jumbos são então cortados para atender a demanda de itens (bobinas menores de papel). O planejamento, que minimiza custos de produção e preparação, deve produzir jumbos (cada máquina produz jumbos de larguras diferentes) que diminuam a perda no processo de corte. Por outro lado, o melhor número de jumbos do ponto de vista de minimizar a perda no processo de corte pode acarretar em altos custos de preparação. Ambos são problemas de otimização combinatória não trivial, o que tem motivado extensas pesquisas nas últimas décadas, entretanto, essa combinação não é bem explorada na literatura. Neste trabalho, são propostos um modelo de otimização integrado e métodos heurísticos de solução. Foram realizados experimentos computacionais com o intuito de analisar o desempenho dos métodos propostos e os resultados apresentaram- se bastante satisfatórios, significando que tais métodos são apropriados para tratar o problema integrado. / An important production programming problem arises in paper industries coupling mul- tiple machine scheduling with cutting stock. From machine scheduling the problem of determining the quantity of jumbos (large rolls of paper) of different types of paper to be produced in each machine arises. These jumbos are then cut to meet the demand for items (smaller rolls of paper). Scheduling that minimizes setups and production costs may produce jumbos (each machine produces jumbos of a specific width) which may increase waste in the cutting process. On the other hand, the best number of jumbos in the point of view of minimizing waste in the cutting process may lead to high setup costs. Both problems are non-trivial combinatorial optimization problems, which have motivated ex- tensive research in the last decades, however their combination is not well explored in the literature. In this work, a coupled optimization modelling and heuristic solution methods are proposed. Computational experiments are devised in order to analyze the performance of the methods and the results had been presented sufficiently satisfactory, meaning that such methods are appropriate to deal with the integrated problem.