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

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

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...

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

Orientador: Silvio Alexandre de Araujo / Banca: Maria do Socorro Nogueira Rangel / Banca: Pedro Munari / Banca: Mauricio Cardoso de Souza / Banca: Edson Luiz França Senne / Resumo: 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... / Abstract: 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... / Doutor

Made available in DSpace on 2014-06-11T19:22:18Z (GMT). No. of bitstreams: 0 Previous issue date: 2013-03-15Bitstream added on 2014-06-13T20:09:18Z : No. of bitstreams: 1 longhi_al_me_sjrp.pdf: 570095 bytes, checksum: 5a30b272ec5bfcb3379a569e16f72a50 (MD5) / Os problemas de dimensionamento de lotes e corte de estoque unidimensional têm importante papel em diversos setores industriais, tais como, fábricas de móveis tubulares e de papel, metalurgicas, entre outros e geralmente são tratados de maneira indepen-dente. Neste trabalho, abordamos os dois problemas de maneira integrada. Estudamos um modelo clássico do problema de dimensionamento de lotes, bem como, sua reformu-lação baseada no problema de caminho mínimo. Para o problema de corte de estoque unidimensional, foram estudados três diferentes modelos matemáticos propostos na lite-ratura. Apresentamos os modelos estudados de maneira integrada e fizemos um estudo computacional, utilizando dados gerados aleatoriamente, comparando os diferentes mo-delos para o problema integrado / The lot-sizing and the one-dimensional cutting-stock problems have an important role in the production sector, such as, tubular furniture and paper factories, metallurgi-cal, among others and generally are dealt independently. In this work, we approach both problems in an integrated way. We studied a classical model for lot sizing problem and its reformulation based on the shortest path problem. For the one-dimensional cutting stock problem, three different models proposed in the literature were studied. We present the studied models in an integrated way and we made a computacional study using randomly generated data, comparing the different models for the integrated problem

Made available in DSpace on 2014-06-11T19:22:18Z (GMT). No. of bitstreams: 0 Previous issue date: 2013-02-26Bitstream added on 2014-06-13T20:48:31Z : No. of bitstreams: 1 melega_gm_me_sjrp.pdf: 491033 bytes, checksum: 2ae4cff430e065db1faa96fe0c6d7304 (MD5) / Os problemas de dimensionamento de lotes consistem em determinar, em um horizonte de tempo finito, a quantidade de itens a serem produzidos para os quais há uma demanda a ser atendida e utiliza-se custos de produção, estoque e preparo. Este trabalho aborda o problema de dimensionamento de lotes em um ambiente constitíudo de várias plantas. Cada item pode ser produzido em qualquer planta é possível atender a demanda de uma determinada planta com produção proveniente de uma (ou várias outras) planta(s); para tanto, incorre-se um custo de transferência. Neste trabalho são propostas reformulações para o problema de dimensionamento de lotes com várias plantas, baseadas no problema do caminho mínimo (Shortest Path- SP) e no problema de localização de facilidades (Facility Location- FL). Alguns resultados computacionais são apresentados comparando a formulação original às reformulações apresentadas. Além disso, propôs-se, para uma das reformulações, um método de busca de limitantes inferiores, no qual a relaxação Lagrangiana é aplicada às restrições de demanda e o método do subgradiente é utilizado para atualizar os multiplicadores. A fim de verificar a qualidade dos limitantes obtidos, são apresentados experimentos computacionais com dados da literatura e estes são comparados aos obtidos com o pacote comercial CPLEX / The lot sizing problem consists of determining, in a finite time horizon, the quantity of items to be produced for which there are demands to be met and involve costs of produc-tion, inventory and setup. This work deals with the multi-plant lot sizing problem. Each item can be produced in any plant and the demand of a particular plant can be met using the production from another (or several other) plant(s); to do so, there is a transfer cost. We present reformulations for the classical problem, based on the shortest path problem (SP) and the facility location problem (FL). Some computational results are shown com-paring all formulations presented. Moreover, we propose, for one of the reformulations, a solution method to find lower bounds, where, the Lagrangian relaxation is applied to the demand constraints and the subgradient method is used to update the multipliers. Aiming to verify the quality of the lower bounds, we present computational experiments with data from literature and compare them to those obtained with commercial package CPLEX

Orientador: Silvio Alexandre de Araujo / Banca: Marcos Nereu Arenales / Banca: Maria do Socorro Nogueira Rangel / Resumo: Os problemas de dimensionamento de lotes e corte de estoque unidimensional têm importante papel em diversos setores industriais, tais como, fábricas de móveis tubulares e de papel, metalurgicas, entre outros e geralmente são tratados de maneira indepen-dente. Neste trabalho, abordamos os dois problemas de maneira integrada. Estudamos um modelo clássico do problema de dimensionamento de lotes, bem como, sua reformu-lação baseada no problema de caminho mínimo. Para o problema de corte de estoque unidimensional, foram estudados três diferentes modelos matemáticos propostos na lite-ratura. Apresentamos os modelos estudados de maneira integrada e fizemos um estudo computacional, utilizando dados gerados aleatoriamente, comparando os diferentes mo-delos para o problema integrado / Abstract: The lot-sizing and the one-dimensional cutting-stock problems have an important role in the production sector, such as, tubular furniture and paper factories, metallurgi-cal, among others and generally are dealt independently. In this work, we approach both problems in an integrated way. We studied a classical model for lot sizing problem and its reformulation based on the shortest path problem. For the one-dimensional cutting stock problem, three different models proposed in the literature were studied. We present the studied models in an integrated way and we made a computacional study using randomly generated data, comparing the different models for the integrated problem / Mestre

Orientador: Adriana Cristina Cherri Nicola / Banca: Silvio Alexandre de Araujo / Banca: Sonia Cristina Poltroniere Silva / Resumo: Este trabalho aborda o Problema de Redimensionamento de Lotes (PRL) capacitado, com múltiplos produtos e máquinas paralelas. O redimensionamento de lotes é uma variação do problema de dimensionamento de lotes que pode ser identificado em sistemas produtivos com elevada taxa de interrupções, como quebras, refugos, entre outros, fazendo com que o plano de produção seja prejudicado, necessitando de atualizações a medida que ocorrem as interrupções. São considerados três parâmetros de interrupção: manutenção corretiva, mão de obra insuficiente e indisponibilidade de matéria-prima. É permitido o atendimento da demanda nos períodos com atrasos e utilização de hora extra. O problema tem por objetivo minimizar os custos de preparação, estoque, atraso e hora extra. Baseado em um modelo matemático proposto na literatura para resolver problemas de dimensionamento de lotes, um modelo matemático para representar o PRL foi proposto. O PRL foi formulado como um problema de programação linear inteira mista (PLIM) e resolvido através do método exato branch and bound. Testes computacionais foram realizados com exemplares adaptados da literatura e abrangem os três parâmetros de interrupção / Abstract: This work approaches the capacitated Lot Resizing Problem (LRP) with multi-products and parallel machines. The lot resizing problem is a lot sizing problem variation which can be identified in productive systems with high rate of interruptions, as breaks, refuse, and others, impairing the planning production and making update needed as soon as interruptions happens. Three parameters for interruption were considered: corrective maintenance, insufficient man power and unavailability of raw material. Demand can be performed with back-orders and overtime requests. This work has the objective of minimize inventory holding costs, back-orders, setup and overtime costs. Based on a mathematical model proposed in the literature to solve the lot sizing problem, a mathematical model to represent the LRP was proposed. The LRP was formulated as a mixed integer problem and solved by branch and bound exact method. Computational experiments were performed with adapted literature instances embracing the three parameters of interruption / Mestre

Made available in DSpace on 2014-06-11T19:26:56Z (GMT). No. of bitstreams: 0 Previous issue date: 2008-02-27Bitstream added on 2014-06-13T19:47:35Z : No. of bitstreams: 1 santos_smpg_me_sjrp.pdf: 975189 bytes, checksum: 365d7872dbad44341fdaa7290f787b15 (MD5) / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / Neste trabalho estudamos o processo produtivo de uma fábrica de móveis característica do Pólo Moveleiro de Votuporanga/SP e propomos um modelo de otimização inteira mista para o processo de produção desta fábrica acoplando o Problema de Dimensionamento de Lotes (PDL) com o Problema de Corte de Estoque (PCE) Bidimensional. O modelo considera vários itens (produtos finais), horizonte rolante de planejamento, sendo que somente o período inicial é programado detalhadamente em relação às restrições de atendimento à demanda por peças e de capacidade das máquinas. Dois conjuntos de padrões de corte são utilizados, aqueles preferidos pela empresa e um conjunto de padrões tabuleiros compostos, e visa a utilização da capacidade total de corte da máquina seccionadora. Testes computacionais fazendo várias comparações foram realizados e mostram a eficiência da abordagem quando o problema é resolvido de forma integrada e quando o conjunto de padrões de corte tabuleiros compostos é utilizado. / In this work we studied the production process of a furniture company located in Votuporanga/SP and we propose a mixed-integer optimization model for the furniture industry production process, integrating the Lot Sizing Problem with the Cutting Stock Problem. The mathematical model considers multi items (final products) in a rolling horizon basis, where only the initial period is detailed with respect to the pieces demanded and capacity machines constraints. Two cutting pattern sets are used, the industry preferred cutting patterns and a set of composed checkerboard patterns, and aims at using the total capacity of the saw machine use. Computational tests with multiple comparisons show the approach effectiveness when the problem is solved in an integrated form and when the composed checkerboard patterns set is used.