Orientador: Silvio Alexandre de Araujo / Coorientador: Diego Jacinto Fiorotto / Banca: Mariá Cristina Vasconcelos Nascimento Rosset / Banca: Desiree Maldonado Carvalho / Resumo: O problema de dimensionamento de lotes com plantas flexíveis e custo de transporte consiste em definir quais plantas deverão ser flexíveis para produzir determinados itens e em determinar a quantidade de itens que deve ser produzida em cada planta e para quais clientes estes itens deverão ser entregues de forma a suprir as demandas predeterminadas, em um horizonte de tempo finito e dividido em períodos, levando em conta custos de produção, preparo, estoque, hora extra, flexibilidade e transporte. Neste trabalho é proposto um modelo matemático para este problema, além de uma análise computacional a fim de verificar se, com um orçamento de flexibilidade predefinido, pode-se oferecer as mesmas vantagens comparado ao orçamento de flexibilidade total. São analisados os casos de flexibilidade com plantas dedicada, plantas com flexibilidade total e algumas reduções deste nível de flexibilidade, como de 20%, 50% e 80% deste orçamento para investir em possíveis flexibilidades das plantas. Os resultados computacionais, para instâncias de tamanho pequeno indicam que é possível obter bons resultados com flexibilidade reduzida e que investir em flexibilidade é importante. Para instâncias de tamanho médio, a dificuldade em se resolver o modelo matemático não permitiu uma análise precisa sobre flexibilidade / Abstract: The lot sizing problem with flexible plants and transport costs consists in defining which plants should be flexible to produce certain items and to determine the quantity of items that should be produced in each plant and to which customers these items should be delivered in order to meet predetermined demands, in a finite time horizon divided into time periods, taking into account production, setup, inventory, overtime, flexibility and transportation costs. In this work, we propose a mathematical model for this problem, in addition to a computational analysis, in order to determine if, with a lower flexibility budget, the same benefits can be achieved compared to the total flexibility budget. We analyze the cases of flexibility with dedicated plants, plants with total flexibility and some reductions of flexibility, such as 20%, 50% and 80% of this budget to invest in possible plant flexibility. The computational results for small instances indicate that it is possible to obtain good results with reduced flexibility and that investing in flexibility is important. For medium instances, the difficulty in solving the mathematical model has not allowed an accurate analysis of flexibility / Mestre

Neste trabalho é apresentada uma revisão do método simplex com geração de colunas e sua aplicação ao problema de corte de estoque. É apresentado o problema combinado, que acopla os problemas de dimensionamento de lotes e de corte de estoque, incluindo uma formulação matemática deste problema. Em seguida consideramos algumas propriedades da matriz de restrições e como construir uma base esparsa para ela, utilizando um reordenamento estático das colunas básicas. Resultados numéricos de uma implementação em MATLAB que realiza trocas de colunas da base e verifica sua esparsidade, simulando o método simplex são apresentados. Após uma troca de colunas básicas, estas são atualizadas de forma eficiente, de modo que cause o menor preenchimento da matriz. Foram realizados também testes computacionais para verificar a robustez do método, através de operações inversas à decomposição e comparação com as colunas originais. Concluímos que a proposta de construção da base estática esparsa leva a bons resultados computacionais com relação à velocidade e robustez em comparação com abordagens que não consideram a estrutura esparsa da matriz de restrições.

Orientador: Silvio Alexandre de Araujo / Coorientador: Diego Jacinto Fiorotto / Banca: Sonia Cristina Poltroniere Silva / Banca: Fernando Luiz Pio dos Santos / Resumo: Este trabalho trata-se do problema de dimensionamento de lotes com máquinas paralelas flexíveis, que consiste basicamente em determinar a quantidade de itens a serem produzidos, em um horizonte de tempo finito, satisfazendo uma demanda, com várias máquinas. Este problema é de origem econômica e envolve custos de produção, estoque e preparação de máquinas. No problema padrão, cada item pode ser produzido em qualquer uma das máquinas, ou seja, têm-se a flexibilidade total de máquinas. No entanto nem sempre é viável ter flexibilidade total das máquinas, devido aos custos. Portanto, pode ser interessante implementar apenas uma flexibilidade limitada. A consideração ou não de uma máquina para produzir um produto específico torna-se uma variável de decisão e há um custo de investimento associado às estas decisões. Os resultados computacionais realizados com o CPLEX mostraram que a formulação é muito difícil, especialmente para instâncias com muitos itens. Assim, neste trabalho foram propostas três heurísticas para o problema, com intuito de buscar boas soluções para o problema em baixos tempos computacionais. As heurísticas foram comparadas ao modelo via pacote de otimização e observou que conforme o número de itens e de máquinas foram aumentando, os resultados obtidos foram melhores / Abstract: This work deals with the problem of lot-sizing with flexible parallel machines, which basically consists of determining the quantity of items to be produced, in afinite time horizon, satisfying a demand, with several machines. This problem is of economic origin and involves production, inventory and machine preparation costs. In the standard problem, each item can be produced in any of the machines, that is, they have the total flexibility of machines. However, it is not always feasible to have total machine flexibility due to costs. Therefore, it may be interesting to implement only limited flexibility. The consideration or not of a machine to produce a specific product becomes a decision variable and there is an investment cost associated with these decisions. The computational results obtained with CPLEX showed that the formulation is very difficult, especially for instances with many items. Thus, in this work three heuristics were proposed for the problem, in order to find good solutions to the problem in low computational times. The heuristics were compared to the model via optimization package and observed that as the number of items and machines were increasing, the results were better / Mestre

Neste trabalho é apresentada uma revisão do método simplex com geração de colunas e sua aplicação ao problema de corte de estoque. É apresentado o problema combinado, que acopla os problemas de dimensionamento de lotes e de corte de estoque, incluindo uma formulação matemática deste problema. Em seguida consideramos algumas propriedades da matriz de restrições e como construir uma base esparsa para ela, utilizando um reordenamento estático das colunas básicas. Resultados numéricos de uma implementação em MATLAB que realiza trocas de colunas da base e verifica sua esparsidade, simulando o método simplex são apresentados. Após uma troca de colunas básicas, estas são atualizadas de forma eficiente, de modo que cause o menor preenchimento da matriz. Foram realizados também testes computacionais para verificar a robustez do método, através de operações inversas à decomposição e comparação com as colunas originais. Concluímos que a proposta de construção da base estática esparsa leva a bons resultados computacionais com relação à velocidade e robustez em comparação com abordagens que não consideram a estrutura esparsa da matriz de restrições.

Segundo uma pesquisa recente realizada junto ao setor de fundições, uma importante preocupação do setor é melhorar seu planejamento de produção. Um plano de produção em uma fundição envolve duas etapas interdependentes: a determinação das ligas a serem fundidas e dos lotes que serão produzidos. Neste trabalho, estudamos o problema de dimensionamento de lotes para fundições de pequeno porte, cujo objetivo é determinar um plano de produção de mínimo custo. Como sugerido na literatura, a heurística proposta trata as etapas do problema de forma hierárquica: inicialmente são definidas as ligas e, posteriormente, os lotes que são produzidos a partir delas. Para a solução do problema, propomos um algoritmo genético que explora um conjunto de possibilidades para a determinação das ligas e utiliza uma heurística baseada em relaxação lagrangiana para determinação dos itens a serem produzidos. Além disso, uma abordagem para o mesmo problema é proposta utilizando o problema da mochila para determinar os itens a serem produzidos. Bons resultados foram obtidos pelos métodos propostos / According to a recent research made by the foundry sector, one of the most concern of the industry is to improve its production planning. A foundry production plan involves two independent stages: the determination of alloys to be merged and the lots that will be produced. In this work, we studied the lot-sizing problem for small foundries, whose purpose is to determine a plan of minimum production cost. As suggested in the literature, the heuristic proposed addresses the problem stages in a hierarchical way: rst we dene the alloys and, subsequently, the lots that are produced from them. We propose a genetic algorithm that explores some possible sets of alloys produced and uses a Lagrangian heuristic to determine the items to be produced. Also, we propose one approach to the same problem that uses the knapsack problem to determine the items to be produced. Good results were obtained by the methods proposed

Tese de mestrado integrado. Engenharia Industrial e Gestão. Faculdade de Engenharia. Universidade do Porto. 2010

Tese de mestrado integrado. Engenharia Industrial e Gestão. Faculdade de Engenharia. Universidade do Porto. 2008

Made available in DSpace on 2015-09-17T15:25:55Z (GMT). No. of bitstreams: 0 Previous issue date: 2015-04-01. Added 1 bitstream(s) on 2015-09-17T15:46:25Z : No. of bitstreams: 1 000844047.pdf: 1360010 bytes, checksum: a9736371c9025fa6942b795285c51961 (MD5) / Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP) / O problema de dimensionamento de lotes é um problema de otimização da produção e consiste em determinar a quantidade de produtos a serem produzidos em cada período ao longo de um horizonte de tempo nito, de modo a atender uma demanda e otimizar uma função objetivo, por exemplo, minimizar os custos. Esta tese aborda duas extensões diferentes do problema de dimensionamento de lotes padrão. Na primeira parte, considerase o problema de dimensionamento de lotes com vários itens, tempos de preparação e máquinas paralelas distintas, e na segunda parte, o problema de dimensionamento de lotes com vários itens e preparação crossover. Para a primeira parte desta tese, em que estuda-se o problema de dimensionamento de lotes com máquina paralelas, o objetivo é aplicar diferentes métodos de solução que utilizam relaxação Lagrangiana e decomposição de Dantzig-Wolfe para obter limitantes inferiores de alta qualidade e desenvolver heurísticas Lagrangianas para obter boas soluções factíveis (limitantes superiores). Baseado em uma reformulação forte do problema como um problema de caminho mínimo e diferente da abordagem tradicional em que as restrições de ligação são as restrições de capacidade, utiliza-se as restrições de uxo, isto é as restrições de demanda, como as restrições de ligação. O objetivo desta abordagem é obter limitantes inferiores de alta qualidade e para tanto, utiliza-se três métodos de solução diferentes. No primeiro a relaxação Lagrangiana é aplicada as restrições de uxo. Para os outros dois resolve-se o problema mestre aplicando métodos de solução diferentes que combinam relaxação Lagrangiana e decomposição de Dantzig-Wolfe de forma hibrida. Duas heurísticas primais, baseadas em transferências de produção, são utilizadas para gerar soluções factíveis. Experimentos computacionais utilizando conjuntos de dados da literatura são apresentados e mostram que os métodos de... / The lot sizing problem is a production optimization problem and consists of determining the quantity of products to be produced in each period of a nite time horizon, in order to meet the demand and optimize an objective function, for example, to minimize costs. In this thesis we address two di erent extensions of the standard lot sizing problem. In the rst part we consider the capacitated lot-sizing problem with multiple items, setup time and unrelated parallel machines and, in the second one, the capacitated lot sizing problem with multiple items and setup crossover. For the rst part of this thesis where we study the lot sizing problem with unrelated parallel machines, the aim is to apply di erent solution methods that use Lagrangian relaxation and Dantzig-Wolfe decomposition to obtain high quality lower bounds and develop Lagrangian heuristics to obtain good feasible solutions (upper bounds). Based on a strong reformulation of the problem as a shortest path problem and unlike in the traditional approach in which the linking constraints are the capacity constraints, we use the ow constraints, i.e. the demand constraints, as linking constraints. The aim of this approach is to obtain high quality lower bounds and for this we have used three di erent solution methods. In the rst one the Lagrangian relaxation is applied to the ow constraints. For the other two we solve the master problem applying solution methods that combine Lagrangian relaxation and Dantzig-Wolfe decomposition in a hybrid form. Two primal heuristics, based on transfers of production quantities, are used to generate feasible solutions. Computational experiments using data sets from the literature are presented and show that the solution methods produce lower bounds of excellent quality and competitive upper bounds, when compared with the bounds produced by other methods from the literature and by a high-performance MIP software...

Made available in DSpace on 2016-06-02T19:51:59Z (GMT). No. of bitstreams: 1 5161.pdf: 1938552 bytes, checksum: b2b5480af19f77bfa88f8903ab2a1b7e (MD5) Previous issue date: 2013-03-19 / Financiadora de Estudos e Projetos / Beverage factories have been trying to improve production planning and control to increase competitive advantages and market shares. In order to achieve such goals, the industries attempted to improve the process of meeting demands, manufacture larger product variety in less time, use less resources and considering the factory´s operating limit. This work considers a production planning problem which lies in the factories which manufactures non-alcoholic beverages fruit. The research problem is the lotscheduling of drinks, characterized by: finite planning horizon, multi-period, multimachine, capacity constraints, setup time and cost, special machine constraints (the machines must be cleaned after certain production time). An optimization approach based on mathematical modeling is proposed, considering different scenarios and using optimization softwares. The proposed models are variations of mixed-integer programming models well-known in the literature, such as the GLSPPL (General Lot Sizing and Scheduling Problem for Parallel Production Lines) and CLSP (Capacitated lot sizing problem). However, instead of considering parallel machines, different arrangements of machines are considered to obtain better representation of the production processes. In order to validate the models, we proposed an approach involving a case study in a beverage factory in the state of São Paulo. The solutions obtained by the models were compared with those used in practice. The results show that the proposed approach has good potential for practical use. / As indústrias de bebidas tem buscado melhorar o planejamento e o controle da produção para obter vantagens competitivas e melhorar suas posições no mercado. Para isso, tem procurado atender melhor à demanda, produzir uma variedade maior de produtos em períodos de tempo mais curtos, utilizando menos recursos e respeitando a capacidade instalada. Neste projeto de mestrado, considera-se um problema de programação da produção em fábricas de bebidas não alcoólicas à base de frutas. A questão investigada consiste na otimização da programação e dimensionamento de lotes de produção de bebidas, tendo como características principais: horizonte de planejamento finito, multi períodos, múltiplas máquinas, restrições de capacidade de produção, tempo e custo de preparação de máquinas e condições especiais de preparação (limpezas obrigatórias após certo período de produção) e preparação de quatro horas independente da sequência de produção. Para a questão em estudo, foi proposta uma abordagem de otimização baseada no desenvolvimento de modelos de programação matemática e resolução dos modelos por meio de softwares de otimização, considerando vários cenários. Os modelos propostos são modificações de modelos de programação linear inteira mista bem conhecidos na literatura, tais como o GLSPPL (General Lot Sizing and Scheduling Problem for Parallel Production Lines) e o CLSP (Capacitated lot sizing problem). Porém, ao invés de se considerar múltiplas máquinas em paralelo, os modelos propostos exploram outras possíveis configurações de máquinas para representar melhor os processos de produção envolvidos. A abordagem proposta foi validada por meio de um estudo de caso em uma fábrica de bebidas no interior de São Paulo, em que as soluções obtidas pelos modelos foram comparadas com as práticas utilizadas pela empresa. Os resultados mostram que a abordagem proposta tem bom potencial de aplicação prática.

Segundo uma pesquisa recente realizada junto ao setor de fundições, uma importante preocupação do setor é melhorar seu planejamento de produção. Um plano de produção em uma fundição envolve duas etapas interdependentes: a determinação das ligas a serem fundidas e dos lotes que serão produzidos. Neste trabalho, estudamos o problema de dimensionamento de lotes para fundições de pequeno porte, cujo objetivo é determinar um plano de produção de mínimo custo. Como sugerido na literatura, a heurística proposta trata as etapas do problema de forma hierárquica: inicialmente são definidas as ligas e, posteriormente, os lotes que são produzidos a partir delas. Para a solução do problema, propomos um algoritmo genético que explora um conjunto de possibilidades para a determinação das ligas e utiliza uma heurística baseada em relaxação lagrangiana para determinação dos itens a serem produzidos. Além disso, uma abordagem para o mesmo problema é proposta utilizando o problema da mochila para determinar os itens a serem produzidos. Bons resultados foram obtidos pelos métodos propostos / According to a recent research made by the foundry sector, one of the most concern of the industry is to improve its production planning. A foundry production plan involves two independent stages: the determination of alloys to be merged and the lots that will be produced. In this work, we studied the lot-sizing problem for small foundries, whose purpose is to determine a plan of minimum production cost. As suggested in the literature, the heuristic proposed addresses the problem stages in a hierarchical way: rst we dene the alloys and, subsequently, the lots that are produced from them. We propose a genetic algorithm that explores some possible sets of alloys produced and uses a Lagrangian heuristic to determine the items to be produced. Also, we propose one approach to the same problem that uses the knapsack problem to determine the items to be produced. Good results were obtained by the methods proposed