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

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

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

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

Orientador: Silvio Alexandre de Araújo / Banca: Reinaldo Morabito Neto / Banca: Franklina Maria Bragion de Toledo / Resumo: Este trabalho consiste numa extensão do estudo de um problema de dimensionamento de lotes com custo de transporte feito por Norden e Velde [53], onde a produção dos itens é transportada, em paletes, para um armazém. O transporte é feito por uma empresa terceirizada sob um contrato com os seguintes custos pré-estabelecidos: um custo fixo de contrato, um custo para o transporte de um determinado volume de paletes e um custo adicional para paletes extras. O problema foi estendido, no presente trabalho, considerando restrições de capacidade e a possibilidade de atrasos no atendimento a demanda. Nosso objetivo é propor um modelo matemático para o problema estendido e desenvolver dois métodos heurísticos de resolução. Tais métodos são baseados em dois tipos de relaxação: relaxação Lagrangiana e relaxação Lagrangiana/Surrogate. Os resultados obtidos pelas heurísticas são comparados com os resultados obtidos pelo pacote de otimização CPLEX 10.0. Além disso, é feita uma comparação entre os métodos heurísticos. / Abstract: This work consist of an extension of a study of the capacitated lot-sizing problems with transportation cost by Norden and Velde [53], where the production of itens is transported into pallets to an warehouse. The transportation is executed by another company, under a contract with the following transportation cost established: a fixed contract cost, a transportation cost for determined quantity of pallets and an additional cost for extra pallets. The problem was extended, in this work, considering capacity constraint and backlogging. Our objective is to propose a mathematical model for the extended problem and to develop two heuristics methods of resolution. The methods are based on two types of relaxation: Lagrangian relaxation and Lagrangian/Surrogate relaxation. The results obtained by heuristics are compared with the results obtained by CPLEX 10.0. Furthermore, a comparison between the heuristics is made. / Mestre

Submitted by Luciana Ferreira (lucgeral@gmail.com) on 2018-04-18T11:03:43Z No. of bitstreams: 2 Dissertação - Ana Paula Vieira Marques - 2018.pdf: 8336756 bytes, checksum: e01a3359bb2bff1e677a274a436cd060 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2018-04-18T11:17:54Z (GMT) No. of bitstreams: 2 Dissertação - Ana Paula Vieira Marques - 2018.pdf: 8336756 bytes, checksum: e01a3359bb2bff1e677a274a436cd060 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2018-04-18T11:17:54Z (GMT). No. of bitstreams: 2 Dissertação - Ana Paula Vieira Marques - 2018.pdf: 8336756 bytes, checksum: e01a3359bb2bff1e677a274a436cd060 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2018-03-26 / In this research, we try to identify some of the legal implications and geographical unfoldings in the production of urban space in the city of Uberlândia (MG), due to the implementation of the irregular settlement Marielza Distric. This study addresses the role of the urban government, its actions, legal limitations and the responsibility regarding the occurrence of clandestine or irregular settlements, as well as the action of a particular urban developer. There are three chapters, in which the theme is analyzed. The first chapter deals with the production of urban space, presenting a brief discussion of theories and problems of production and appropriation of the capitalist urban space, highlighting the growth of urbanization in Brazil and the population of Uberlândia (MG) and the legislation on the use and urban land access. In the second chapter we try to analyze the role of local power, real estate speculation and the challenges of urban space production in Uberlândia (MG), passing through issues such as the unequal appropriation of urban space, the social cost of implementing irregular or clandestine settlements and the performance of landowners and real estate agents. Lastly, the third chapter presents Marielza district in itself, where one seeks to know the current reality of the residents and a little of the history of the neighborhood. / Nessa pesquisa, busca-se identificar algumas das implicações e desdobramentos jurídicos e geográficos na produção do espaço urbano, na cidade de Uberlândia (MG), decorrente da implantação do loteamento irregular Vila Marielza. O estudo aborda o papel do Estado, sua atuação e limitações legais e responsabilidade quanto ao surgimento de loteamentos clandestinos ou irregulares, bem como a atuação do loteador. São três capítulos, nos quais a temática é analisada. O primeiro capítulo trata da produção do espaço urbano, apresentando uma breve discussão das teorias e problemas da produção e apropriação do espaço urbano capitalista, destacando o crescimento da urbanização no Brasil e populacional de Uberlândia (MG) e a legislação sobre uso e parcelamento do solo urbano. No segundo capítulo procura-se analisar o papel do Poder Municipal, a especulação imobiliária e os desafios da produção do espaço urbano em Uberlândia (MG), perpassando por questões como a apropriação desigual do espaço urbano, o custo social da implantação de loteamentos irregulares ou clandestinos e a atuação dos proprietários da terra e dos agentes imobiliários. Por fim, o último capítulo apresenta o loteamento propriamente dito, onde se busca conhecer a realidade atual dos moradores e um pouco da história do bairro.

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.

Chen, Jiayi. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2009. / Includes bibliographical references (p. 86-94). / Abstract also in Chinese. / Abstract --- p.i / Acknowledgement --- p.iv / Introduction --- p.1 / Chapter 1.1 --- Introduction to the Capacitated Lot Sizing (CLS )problem --- p.1 / Chapter 1.2 --- Our contributions --- p.2 / Chapter 1.3 --- Organization of the thesis --- p.4 / Literature Review --- p.5 / Chapter 2.1 --- Research in CLS problem --- p.5 / Chapter 2.1.1 --- Reviews in CLS problems --- p.8 / Chapter 2.1.2 --- Approaches and methods to solve the traditional CLS problems --- p.9 / Chapter 2.1.3 --- Research on Fixed-Charge-Transportation-typed models for CLS problems --- p.13 / Chapter 2.2 --- Research in Genetic Algorithm (GA) --- p.15 / Chapter 2.3 --- Conclusion --- p.17 / Problem Description and Formulation --- p.18 / Chapter 3.1 --- The formulation --- p.18 / Chapter 3.2 --- Comparison with the traditional formulation --- p.24 / Chapter 3.3 --- Conclusion --- p.28 / Description of the Heuristic --- p.29 / Chapter 4.1 --- Initialization --- p.32 / Chapter 4.1.1 --- Setup string generation --- p.32 / Chapter 4.1.2 --- Transportation problem --- p.35 / Chapter 4.1.3 --- Consistency test --- p.47 / Chapter 4.2 --- Selection --- p.50 / Chapter 4.3 --- Crossover --- p.50 / Chapter 4.4 --- Mutation --- p.52 / Chapter 4.5 --- Evaluation --- p.53 / Chapter 4.6 --- Termination --- p.54 / Chapter 4.7 --- Conclusion --- p.54 / Design of Experiments and Computational Results --- p.56 / Chapter 5.1 --- Design of experiments --- p.57 / Chapter 5.2 --- Discussion of lower bound procedures --- p.63 / Chapter 5.3 --- Computational results --- p.65 / Chapter 5.3.1 --- CLS problems with setup times --- p.65 / Chapter 5.3.2 --- CLS problems without setup times --- p.77 / Chapter 5.4 --- Conclusion --- p.82 / Conclusion --- p.83 / Bibliography --- p.86