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

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

Production planning problems are of paramount importance within supply chain planning, supporting decisions on the transformation of raw materials into finished products. Lot sizing in production planning refers to the tactical/operational decisions related to the size and timing of production orders to satisfy a demand. The objectives of lot-sizing problems are generally economical-related, such as saving costs or increasing profits, though other aspects may be taken into account such as quality of the customer service and reduction of inventory levels. Lot-sizing problems are very common in production activities and an efficient planning of such activities gives the company a clear advantage over concurrent organizations. To that end it is required the consideration of realistic features of the industrial environment and product characteristics. By means of mathematical modelling, such considerations are crucial, though their inclusion results in more complex formulations. Although lot-sizing problems are well-known and largely studied, there is a lack of research in some real-world aspects. This thesis addresses two main characteristics at the lot-sizing context: (a) setup crossover; and (b) perishable products. The former allows the setup state of production line to be carried over between consecutive periods, even if the line is not yet ready for processing production orders. The latter characteristic considers that some products have fixed shelf-life and may spoil within the planning horizon, which clearly affects the production planning. Furthermore, two types of perishable products are considered, according to the duration of their lifetime: medium-term and short-term shelf-lives. The latter case is tighter than the former, implying more constrained production plans, even requiring an integration with other supply chain processes such as distribution planning. Research on stronger mathematical formulations and solution approaches for lot-sizing problems provides valuable tools for production planners. This thesis focuses on the development of mixed-integer linear programming (MILP) formulations for the lot-sizing problems considering the aforementioned features. Novel modelling techniques are introduced, such as the proposal of a disaggregated setup variable and the consideration of lot-sizing instead of batching decisions in the joint production and distribution planning problem. These formulations are subjected to computational experiments in state-of-the-art MILP-solvers. However, the inherent complexity of these problems may require problemdriven solution approaches. In this thesis, heuristic, metaheuristic and matheuristic (hybrid exact and heuristic) procedures are proposed. A lagrangean heuristic addresses the capacitated lot-sizing problem with setup carryover and perishable products. A novel dynamic programming procedure is used to achieve the optimal solution of the uncapacitated single-item lot-sizing problem with setup carryover and perishable item. A heuristic, a fix-and-optimize procedure and an adaptive large neighbourhood search approach are proposed for the operational integrated production and distribution planning. Computational results on generated set of instances based on the literature show that the proposed methods yields competitive performances against other literature approaches. / Problemas de planejamento da produção são de suma importância no planejamento da cadeia de suprimentos, dando suporte às decisões da transformação de matérias-primas em produtos acabados. O dimensionamento de lotes em planejamento de produção é definido pelas decisões tático-operacionais relacionadas com o tamanho das ordens de produção e quando fabricá-las para satisfazer a demanda. Os objetivos destes problemas são geralmente de cunho econômico, tais como a redução de custos ou o aumento de lucros, embora outros aspectos possam ser considerados, tais como a qualidade do serviço ao cliente e a redução dos níveis de estoque. Problemas de dimensionamento de lotes são muito comuns em atividades de produção e um planejamento eficaz de tais atividades, estabelece uma clara vantagem à empresa em relação à concorrência. Para este objetivo, é necessária a consideração de características realistas do ambiente industrial e do produto. Para a modelagem matemática do problema, estas considerações são cruciais, embora sua inclusão resulte em formulações mais complexas. Embora os problemas de dimensionamento de lotes sejam bem conhecidos e amplamente estudados, várias características reais importantes não foram estudadas. Esta tese aborda, no contexto de dimensionamento de lotes, duas características muito relevantes: (a) preservação da preparação total e parcial; e (b) produtos perecíveis. A primeira permite que o estado de preparação de uma linha de produção seja mantido entre dois períodos consecutivos, mesmo que a linha de produção ainda não esteja totalmente pronta para o processamento de ordens de produção. A ultima característica determina que alguns produtos tem prazo de validade fixo, menor ou igual do que o horizonte de planejamento, o que afeta o planejamento da produção. Além disso, de acordo com a duração de sua vida útil, foram considerados dois tipos de produtos perecíveis: produtos com tempo de vida de médio e curto prazo. O ultimo caso resulta em um problema mais apertado do que o anterior, o que implica em planos de produção mais restritos. Isto pode exigir uma integração com outros processos da cadeia de suprimentos, tais como o planejamento de distribuição dos produtos acabados. Pesquisas sobre formulações matemáticas mais fortes e abordagens de solução para problemas de dimensionamento de lotes fornecem ferramentas valiosas para os planejadores de produção. O foco da tese reside no desenvolvimento de formulações de programação linear inteiro-mistas (MILP) para os problemas de dimensionamento de lotes, considerando as características mencionadas anteriormente. Novas técnicas de modelagem foram introduzidas, como a proposta de variáveis de preparação desagregadas e a consideração de decisões de dimensionamento de lotes ao invés de decisões de agrupamento de ordens de produção no problema integrado de planejamento de produção e distribuição. Estas formulações foram submetidas a experimentos computacionais em MILP-solvers de ponta. No entanto, a complexidade inerente destes problemas pode exigir abordagens de solução orientadas ao problema. Nesta tese, abordagens heurísticas, metaheurísticas e matheurísticas (híbrido de métodos exatos e heurísticos) foram propostas para os problemas discutidos. Uma heurística lagrangeana aborda o problema de dimensionamento de lotes com restrições de capacidade, preservação da preparação total e produtos perecíveis. Um novo procedimento de programação dinâmica e utilizado para encontrar a solução ótima do problema de dimensionamento de lotes de um único produto perecível, sem restrições de capacidade e preservação da preparação total. Uma heurística, um procedimento x-and-optimize e uma abordagem por buscas adaptativas em grande vizinhanças são propostas para o problema integrado de planejamento de produção e distribuição. Resultados computacionais em conjuntos de instâncias geradas com base na literatura mostram que os métodos propostos obtiveram performances competitivas com relação a outras abordagens da literatura.

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

Nesta dissertação abordamos o problema de dimensionamento e sequenciamento de lotes com aceitação de pedidos. As demandas dos clientes são agregadas em pedidos, os quais podem ou não ser aceitos e devem ser entregues dentro de uma janela de tempo. Os itens são perecíveis e podem permanecer no estoque somente por um tempo determinado (shelf-life). O objetivo do problema é maximizar a receita gerada pelo atendimento dos pedidos, descontando os custos de estoque e das preparações da máquina. Para tratar o problema são propostas formulações matemáticas e abordagens heurísticas contendo uma etapa construtiva seguida por uma heurística de melhoramento. Testes computacionais foram realizados e os resultados obtidos foram analisados. As heurísticas obtiveram desempenho superior ao branch-and-cut do solver de otimização na obtenção de soluções de boa qualidade, no limite de tempo estabelecido. / In this dissertation, we approach the lot sizing and scheduling problem with order acceptance. Customers demands are aggregated into orders, which may or may not be accepted and must be delivered within a time window. The items are perishable and can remain in inventory only for a limited time (shelf-life). The aim of the problem is profit maximizing generated by orders acceptance, discounting inventory and machine setups costs. To deal with this problem math formulations, constructive and improvement heuristics were proposed. Computational tests were performed and the results obtained were analyzed. The heuristics obtained superior performance then branch-and-cut of the optimization solver obtaining good quality solutions within the established time limit.

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.

Made available in DSpace on 2016-05-17T16:51:22Z (GMT). No. of bitstreams: 0 Previous issue date: 2015-08-14. Added 1 bitstream(s) on 2016-05-17T16:54:57Z : No. of bitstreams: 1 000863325_20170814.pdf: 1379523 bytes, checksum: db1556043273e4889e27702a2bf223ce (MD5) Bitstreams deleted on 2017-08-18T12:37:07Z: 000863325_20170814.pdf,. Added 1 bitstream(s) on 2017-08-18T12:37:52Z : No. of bitstreams: 1 000863325.pdf: 2314226 bytes, checksum: 152290accc1d5181a771e05181b739cf (MD5) / Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP) / A Pesquisa Operacional se tornou uma aliada de diversos problemas reais, principalmente de problemas da indústria, cujo objetivo é minimizar seus custos. Um dos problemas de muitos gestores é determinar quanto produzir, quando produzir e em que ordem produzir. Para responder essas três perguntas simultaneamente é têm-se que resolver o problema integrado de dimensionamento de lotes e sequenciamento da produção. O presente trabalho vem trazer modelos matemáticos que podem ser adaptados em diversos estudos de casos para responder a questão tríplice: quanto, quando e em que ordem, tudo isso, minimizando os custos de estoque, atraso e troca. A tese responde a seguinte pergunta, até então uma lacuna na literatura, entre os modelos que integram dimensionamento e sequenciamento da produção, qual é o melhor? Cinco modelos foram propostos e estudados do ponto de vista teórico e computacional para então descobrir o melhor. A construção dos modelos foi baseada no artigo de Oncam et al. (2009) que apresenta resultados teóricos e computacionais para mostrar qual o melhor modelo para o problema do caixeiro viajante. Esperava-se que os resultados fossem similares. Porém, o melhor modelo para o problema integrado de dimensionamento de lotes e sequenciamento da produção é diferente do melhor modelo para o problema do caixeiro viajante / Operational Research has become an ally of several real problems, especially problems of industry, whose objective is to minimize their costs. One of the problems of many managers is to determine how much to produce, when to produce and in what order produce. To answer these three questions simultaneously simply solve the integrated problem of lot sizing and sequencing of production. This work presents mathematical models that can be adapted in several case studies to answer the threefold question: how much, when and in what order, all while minimizing inventory costs, delay and return. This thesis is interested on the question, What is the best model for the integrate lot sizing and scheduling problem?. ItWere proposed five models and theys were studied in the theoretical and computational viewpoint. All models was based in the travelling salesman problem (TSP). And the results show that the integrate lot sizing and scheduling problem based in the TSP isn't the same model for the TSP / FAPESP: 2010/19006-0

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