O problema de dimensionamento e sequenciamento de lotes vem sendo extensivamente estudado por pesquisadores da área de Pesquisa Operacional e há uma tendência de que tais trabalhos passem a cada vez mais integrar aspectos reais dos processos produtivos. Entretanto, percebe-se que os estudos conduzidos em alguns setores industriais negligenciam importantes restrições tecnológicos dos processos de produção e isso afasta esses trabalhos de Pesquisa Operacional de uma aplicação efetiva, como é o caso da indústria de embalagens de vidro. Neste contexto, propõe-se um modelo de programação inteira mista e um método de solução para o problema de dimensionamento e sequenciamentos de lotes na indústria de embalagens de vidro, sendo que este trabalho diferencia-se dos demais existentes na literatura por agregar restrições tecnológicas específicas desse processo produtivo. O modelo proposto, denominado CLSD-GCST, foi amplamente validado com base em um conjunto de testes com 40 instâncias de um problema real de uma grande empresa do setor no pacote comercial IBM ILOG CPLEX Optimization Studio Versão 12.5. A validação do modelo incluiu ainda uma análise de ganhos potenciais para o negócio de baseada no modelo SCOR. Já o método de solução proposto consiste em uma metaheurística de Busca em Vizinhança Variável (VNS) e se mostrou promissor para a solução do problema estudado, proporcionando resultados de qualidade em um baixo tempo computacional. Além disso, o VNS superou o Branch-and-Cut do CPLEX para grandes instâncias, nas quais o pacote comercial encontrou dificuldades. Por fim, o VNS proposto também foi validado por meio da análise de testes computacionais e suas principais características foram avaliadas sistematicamente, gerando um conjunto de informações que pode direcionar a utilização e, até mesmo, a evolução desse método em pesquisas futuras. / Lot sizing and scheduling problem has been extensively studied by Operations Research scientists and there is a tendency of incorporating more production processes real aspects in these researches. However, it can be noticed that studies conducted in some industrial sectors neglect important production process technological constraints and it keeps the Operations Research works away from an effective application, as happens with the glass containers industry. In this context, a mixed integer programming model and a solution method were proposed for glass containers industry lot sizing and scheduling problem, the main difference between this work and the others in literature is the inclusion of process specific technological constraints. The proposed model, named CLSD-GCST, was widely validated by a set of tests performed with 40 instances from a large company real problem using the commercial package IBM ILOG CPLEX Optimization Studio Version 12.5. The model validation also included a potential business earnings analysis based on SCOR framework. About the proposed solution method, it consists of a Variable Neighborhood Search (VNS) metaheuristic and it proved to be promising for the studied problem solution, providing good quality results in low computational time. Moreover, VNS overcame the CPLEX Branch-and-Cut for large instances, in which the commercial package found difficulties. Lastly, the proposed VNS was validated by means of computational tests analysis and its main characteristics were systematically evaluated, generating an information set that may direct this method application and even its evolution in future researches.

Nesta tese é abordado o problema da mochila compartimentada e o problema de corte de estoque unidimensional acoplado ao problema dimensionamento de lotes. Para o problema da mochila compartimentada é apresentada a versão unidimensional e proposta a versão bidimensional, denominados como problema da mochila compartimentada unidimensional e problema da mochila compartimentada bidimensional, respectivamente. Para o problema de corte de estoque acoplado ao dimensionamento de lotes são apresentadas três variações: uma máquina para produzir um tipo de objeto; uma máquina para produzir vários tipos de objetos; múltiplas máquinas para produzir vários tipos de objetos. Algumas formulações matemáticas de programação inteira e inteira-mista, decomposições dos problemas em problema mestre e subproblemas e heurísticas baseadas no método geração de colunas são propostas para os problemas da mochila compartimenta e o problema acoplado. Em específico, para o problema acoplado são aplicadas decomposições Dantzig-Wolfe, que podem ser por período, por máquina ou por período e máquina. Além disso, uma heurística baseada em grafo E/OU é proposta para o problema da mochila compartimentada bidimensional / In this thesis we present the constrained compartmentalized knapsack problem and the one dimensional cutting stock problem integrated with the capacitated lot sizing problem. For the constrained compartmentalized knapsack problem, the one dimensional version is presented and the two dimensional version is proposed, called one-dimensional compartmentalized knapsack problem and two-dimensional compartmentalized knapsack problem, respectively. For the cutting stock problem integrated with the capacitated lot sizing problem three variations are considered: one machine to produce one type of object; one machine to produce multiple types of objects; multiple machines to produce multiple types of objects. Some integer and mixed programming formulations, decompositions of the problems in master problem and subproblems and heuristics based on column generation method are proposed for the compartmentalized knapsack problem and the cutting stock problem integrated with the capacitated lot sizing problem. In particular, the period, the machine, and the period and machine Dantzig- Wolfe decompositions are applied for the integrated problem. Moreover, a heuristic based on the graph AND/OR is proposed for the two-dimensional compartmentalized knapsack problem. Computational results show that these mathematical formulations and methods provide good solutions

O problema de dimensionamento e sequenciamento de lotes vem sendo extensivamente estudado por pesquisadores da área de Pesquisa Operacional e há uma tendência de que tais trabalhos passem a cada vez mais integrar aspectos reais dos processos produtivos. Entretanto, percebe-se que os estudos conduzidos em alguns setores industriais negligenciam importantes restrições tecnológicos dos processos de produção e isso afasta esses trabalhos de Pesquisa Operacional de uma aplicação efetiva, como é o caso da indústria de embalagens de vidro. Neste contexto, propõe-se um modelo de programação inteira mista e um método de solução para o problema de dimensionamento e sequenciamentos de lotes na indústria de embalagens de vidro, sendo que este trabalho diferencia-se dos demais existentes na literatura por agregar restrições tecnológicas específicas desse processo produtivo. O modelo proposto, denominado CLSD-GCST, foi amplamente validado com base em um conjunto de testes com 40 instâncias de um problema real de uma grande empresa do setor no pacote comercial IBM ILOG CPLEX Optimization Studio Versão 12.5. A validação do modelo incluiu ainda uma análise de ganhos potenciais para o negócio de baseada no modelo SCOR. Já o método de solução proposto consiste em uma metaheurística de Busca em Vizinhança Variável (VNS) e se mostrou promissor para a solução do problema estudado, proporcionando resultados de qualidade em um baixo tempo computacional. Além disso, o VNS superou o Branch-and-Cut do CPLEX para grandes instâncias, nas quais o pacote comercial encontrou dificuldades. Por fim, o VNS proposto também foi validado por meio da análise de testes computacionais e suas principais características foram avaliadas sistematicamente, gerando um conjunto de informações que pode direcionar a utilização e, até mesmo, a evolução desse método em pesquisas futuras. / Lot sizing and scheduling problem has been extensively studied by Operations Research scientists and there is a tendency of incorporating more production processes real aspects in these researches. However, it can be noticed that studies conducted in some industrial sectors neglect important production process technological constraints and it keeps the Operations Research works away from an effective application, as happens with the glass containers industry. In this context, a mixed integer programming model and a solution method were proposed for glass containers industry lot sizing and scheduling problem, the main difference between this work and the others in literature is the inclusion of process specific technological constraints. The proposed model, named CLSD-GCST, was widely validated by a set of tests performed with 40 instances from a large company real problem using the commercial package IBM ILOG CPLEX Optimization Studio Version 12.5. The model validation also included a potential business earnings analysis based on SCOR framework. About the proposed solution method, it consists of a Variable Neighborhood Search (VNS) metaheuristic and it proved to be promising for the studied problem solution, providing good quality results in low computational time. Moreover, VNS overcame the CPLEX Branch-and-Cut for large instances, in which the commercial package found difficulties. Lastly, the proposed VNS was validated by means of computational tests analysis and its main characteristics were systematically evaluated, generating an information set that may direct this method application and even its evolution in future researches.

O planejamento da produção em indústrias moveleiras de pequeno porte é comumente constituído por decisões referentes ao volume de produção e à política de estoque, com o objetivo de minimizar o desperdício de material, os atrasos e as horas-extras utilizadas ao longo do horizonte de planejamento. Administrar tais decisões de uma maneira tratável e eficiente é, em geral, um desafio, especialmente considerando a natureza incerta dos dados. Nessa tese, são desenvolvidos modelos de otimização para apoiar tais decisões no contexto do problema combinado de dimensionamento de lotes e corte de estoque sob incertezas que surge em indústrias moveleiras. Para lidar com as incertezas dos dados, são investigadas duas metodologias: programação estocástica e otimização robusta. Dessa maneira, são propostos modelos de programação estocástica de dois estágios com recurso, assim como modelos estocásticos robustos que incorporam aversão ao risco. A motivação em também desenvolver modelos baseados em otimização robusta é considerar casos práticos em que não há uma descrição probabilística explícita dos dados de entrada, assim como evitar trabalhar com numerosos cenários, o que pode tornar o modelo estocástico computacionalmente intratável. Os experimentos numéricos baseados em exemplares reais de uma empresa moveleira de pequeno porte mostram que as soluções obtidas pelos modelos de programação estocástica fornecem planos de produção robustos e que o (a) decisor (a) pode designar suas preferências em relação ao risco aos modelos, assim como controlar o tradeoff entre o custo total esperado e a robustez da solução. Em relação aos resultados dos modelos de otimização robusta, são obtidos alguns insights entre os chamados budgets de incerteza, as taxas de atendimento da demanda e os valores ótimos. Além disso, evidências numéricas indicam que budgets de incerteza menos conservadores resultam em níveis de serviço razoáveis com baixos custos globais, enquanto a abordagem de pior caso gera, relativamente, boas taxas de atendimento da demanda, mas com custos globais elevados / Production planning procedures in small-size furniture companies commonly consist of decisions with respect to production level and inventory policy, while attempting to minimize trim-loss, backlogging and overtime usage throughout the planning horizon. Managing these decisions in a tractable and efficient way is often a challenge, especially when the uncertainty of data is taken into account. In this thesis, we develop optimization models to support these decisions in the context of the combined lot-sizing and cutting-stock problem that arises in furniture companies. To deal with data uncertainty, we investigate two methodologies: stochastic programming and robust optimization. In the former case, we propose two-stage stochastic programming models with recourse, as well as robust stochastic models to incorporate risk-aversion. In the latter case, our motivation to investigate robust optimization models is the lack of an explicit probabilistic description of the input data. Furthermore, we want to avoid dealing with a large number of scenarios, which typically lead to computationally intractable stochastic programming models. Numerical experiments based on real data from a small-size furniture plant show that the solutions of the stochastic programming models provide robust production plans so that the decision-maker can assign his or her risk preferences to the model and control the tradeoff between the expected total cost and solution robustness. Regarding the results from the robust optimization models, we provide some insights into the relationship among budgets of uncertainty, fill rates and optimal values. Moreover, numerical evidence indicate that less conservative budgets of uncertainty result in reasonable service levels with cheaper global costs, while worst case deterministic approaches lead to relatively good fill rates, but with prohibitive global costs

O problema de dimensionamento de lotes, objeto desse estudo, considera um ambiente composto por múltiplas plantas independentes, múltiplos itens e múltiplos períodos. O ambiente de produção tem capacidade limitada e as plantas podem produzir os mesmos itens. Cada planta tem uma demanda própria e é permitida a transferência de lotes entre as plantas, o que envolve um certo custo. Este problema tem como caso particular o de dimensionamento de lotes com máquinas paralelas. O objetivo desta dissertação é propor uma heurística baseada na meta-heurística GRASP (Greedy Randomized Adaptive Search Procedures). Além disso, uma estratégia path relinking foi incorporada ao GRASP como uma fase de melhoria do algoritmo. Para verificar a eficiência da heurística proposta, os seus resultados são comparados aos da literatura tanto no caso de máquinas paralelas quanto no de múltiplas plantas. Como resultado, o problema de múltiplas plantas obteve melhores resultados quando comparado aos da heurística da literatura. Com relação ao problema de máquinas paralelas, a heurística proposta se mostrou competitiva / The lot sizing problem, which is the aim of this study, considers an environment consisting of multiple independent plants, multiple items and multiple periods. The production environment has limited capacity and the plants can produce the same items. Each plant has its own demand and the lot transfers between the plants are permitted, which involves a certain cost. This problem has as a particular case the parallel machines lot sizing problem. The objective of this dissertation is to propose a heuristic based on the GRASP (Greedy Randomized Adaptive Search Procedures). Furthermore, a path relinking phase is embedded in the GRASP to obtain better performance. To verify the efficiency of the proposed heuristic, its results were compared with the literature as for the multi-plant as for parallel machines problem. Computational tests showed that the proposed heuristic performed better than other literature heuristic concerning the multiplant problem. Concerning the parallel machines, the heuristic is competitive

Neste trabalho apresentamos dois modelos de otimização e um método heurístico de solução para tratar um problema de comprovação fiscal em exportações de commodities no Brasil. Dos modelos de otimização, um foi desenvolvido baseado no Problema de Dimensionamento de Lotes e outro no Problema da Mochila. O governo brasileiro estimula as exportações no país através de alguns benefícios fiscais, alguns desses, sendo possíveis através da comprovação fiscal das exportações de mercadorias acompanhadas de notas fiscais de tipo de operação de fim específico para a exportação. Os benefícios deixam de ser concedidos a partir da perda do prazo da comprovação fiscal da nota fiscal, que é realizado utilizando a Declaração Única de Exportação (DU-E). Cada nota fiscal possui uma data de emissão, dias de isenção fiscal, o percentual da alíquota de ICMS cobrado dependendo do estado emissor, os itens e suas quantidades. As decisões visam estabelecer as combinações de quais notas fiscais devem ser comprovadas em cada embarque de produtos para o mercado exterior, obedecendo às suas datas de isenção de modo a minimizar os impostos pagos devido aos vencimentos dos prazos de despachos das notas. Os resultados obtidos por meio do modelo matemático mostram que a política otimizada de embarque dos produtos das notas fiscais apresenta uma redução dos custos em aproximadamente 39% em determinadas situações. / In this paper we present two optimization models and a heuristic method to deal with a problem of export tax on Brazilian commodities. Regarding the optimization models, one was developed based on the lot-sizing problem and an other on the knapsack problem. The Brazilian government encourages local exportation through tax benefits, some of them being possible by the taxation of exported goods being accompanied by invoices of an operation type that is specific for the purpose of the export. These benefits cease to be granted as a result of exceeding the tax invoice verification period, which is granted using the Single Export Declaration (DU-E). Each invoice has a date issue, days of tax exemption, the percentage of the ICMS tax rate charged depending on the issuing state, the items and their quantities. The decisions aim to establish the combinations of which invoices must be presented for each shipment of products to the foreign market, obeying their exemption dates in order to minimize the taxes paid due the maturity of the delivery times on the documents. The results obtained using the mathematical model show that the optimized shipping policy for invoiced products presents a 39% reduction in costs in certain situations.

Timing of ordering of inventory items is of very great importance in Materials Requirement Planning. Uncertainties in timing can have an adverse effect on the system performance. Most often the lead time variation contribute to timing uncertainties; and their effects are reflected in added costs. Lead time error effects are investigated in this thesis. The study attempts to estimate the effects through some relevant costs, and their variations across the lot sizing rules. The hypotheses for this study are 1) Between any two lot sizing rules, there will be a significant difference in error coats due to combined effect of purchased lead time error and manufacturing lead time errors; 2) Relative cost performance of lot sizing rules in MRP is influenced by the lead time errors; 3) There will be a difference in error cost between lot for l o t rule and least total cost rule even with single source of lead time variation. To carry out the study a MRP programme was developed, in FORTRAN 77 with provisions to include the lot sizing rules while exploding the structure. The lot sizing rules used in the study are Lot for Lot, Silver and Meal heuristics, Wagner-Whitin algorithm, Least total cost, Least unit cost and Part Period balancing. A simulation model is developed using GPSS/PC, to test the hypotheses. An hypothetical production situation with three end items, each with a different product structure is designed. In addition, a master production schedule and a job shop are also structured. Appropriate distributions are assumed for both manufacturing lead times and purchase lead times. These provide the stochastic variables in the simulation experiments. A series of experiments were carried out with the model to investigate into the variations of costs amongst lot sizing rules. Results of the simulation experiments prove that there are costs associated with lead time errors in MRP. These error costs vary significantly with different lot sizing rules. It is also found that the resultant error costs vary significantly even with a single source of lead time variation. Least unit cost rule gives the beat performance having least error costs. Lot for Lot rule has shown the worst performance amongst the lot sizing rules considered. Other interesting results have emerged out of the study.

Made available in DSpace on 2016-06-02T19:50:00Z (GMT). No. of bitstreams: 1 TeseFinal_DeisemaraFerreira.pdf: 1960239 bytes, checksum: 9677bb9eaf4478a7877a607e864d55a2 (MD5) Previous issue date: 2006-12-13 / The object of this study is the integrated problem of lot sizing and scheduling of the soft drink production. Such problem consists of deciding how much to produce of each drink and in each period and in which sequence, in order to satisfy the demand and to minimize the costs of storage, backlogging and changeover. The set up times of the machines are sequencedependent, consequently the production scheduling is complex. The problem is capacitated, multi-item, with changeover times and costs dependent of the sequence. In this study we propose three mixed integer optimization models and solution approaches to solve the problem. The models are based in cases studies of a large soft drink facility, and a small facility. We developed relax and fix heuristics to solve de models. The results show that the proposed strategies are competitive when we compare with solutions of the facilities. / O objeto deste trabalho é o problema integrado de dimensionamento de lotes e sequenciamento da produção de bebidas, tais como refrigerantes, sucos, chás, águas, etc. Tal problema consiste em decidir os tamanhos dos lotes de produção de cada bebida e qual a sequência de produção de cada lote em cada período, de maneira a satisfazer a demanda e minimizar os custos de estoque, atraso e trocas. Os tempos de limpeza das máquinas neste tipo de produção são dependentes do sequenciamento, o que dificulta a programação da produção. Este é um problema capacitado, multi-item, multi-máquinas, com tempos e custos de troca dependentes da sequência. Na presente tese são propostos três modelos de otimização inteira mista e diferentes abordagens de solução para tratar o problema. Os modelos são baseados em estudos de caso realizados nos processos industriais de fábricas de bebidas de pequeno, médio e grande porte. As abordagens aplicam, entre outras, heurísticas do tipo relax and fix, e o método Branch and Cut para resolver os modelos. Uma linguagem de modelagem e um software específico de resolução são utilizados. Os resultados foram satisfatórios e mostram que as abordagens são capazes de produzir soluções melhores que as soluções das empresas.

Made available in DSpace on 2016-06-02T19:50:15Z (GMT). No. of bitstreams: 1 4224.pdf: 4088163 bytes, checksum: f36f82cf58386b4174743eccaa446df4 (MD5) Previous issue date: 2011-02-12 / The number of successful applications that use optimization models has followed the evolution of the computers, as much in hardware, with more powerful machines, as in software, with more intelligent algorithms. Due to importance of the modeling as a decision support tool, much effort has been made to mathematically describe systems of interest and devise techniques for solving such models. This work presents a detailed description of the operations involved in production planning and control of the electrofused grain industry and proposes the use of exact and heuristic methods to support decisions in such activities, particularly in production scheduling. Several visits were made to companies in this sector and a case study was carried out one of these companies in order to formulate alternatives to increase productivity and improve customer service. Optimizing the production scheduling of electrofused grains is not a simple task mainly because of the scale of the equipment setup times, the diversity of the products, and the narrow orders due dates. Based on the case study, mixed linear programming models that combine known models of process selection and single-stage lot sizing were developed, and a constructive heuristic, local search variants, and a GRASP algorithm were proposed to solve one of the models. Computational results with a real instance and randomly generated instance sets show that the exact methods as well as the heuristics can produce as good or better production scheduling than the ones currently employed by the studied company / O número de aplicações bem sucedidas que utilizam modelos de otimização têm acompanhado a evolução dos computadores, tanto em hardware, com máquinas mais poderosas, como em software, com algoritmos mais inteligentes. Devido à importância da modelagem como ferramenta de apoio à tomada de decisão, muitos trabalhos que exploram formas de representação de problemas e técnicas de solução de modelos vêm sendo desenvolvidos. Este trabalho apresenta uma descrição detalhada das operações envolvidas no planejamento e controle da produção na indústria de grãos eletrofundidos e propõe o uso de modelos e métodos exatos e heurísticos para apoio à tomada de decisões nesta atividade, em particular, na programação da produção. Várias visitas foram realizadas a empresas do setor, e em uma dessas empresas foi empreendido um estudo de caso com o objetivo de formular alternativas para aumento da produtividade e a melhoria do nível de serviço aos clientes. Otimizar a programação da produção de grãos eletrofundidos não é uma tarefa simples, principalmente devido à grandeza dos tempos de preparação dos equipamentos, à diversidade de produtos e às limitações dos prazos de entrega da carteira de pedidos. Com base no estudo de caso, modelos de programação linear inteira mista que combinam modelos clássicos de seleção de processos e dimensionamento de lotes monoestágio foram desenvolvidos, e uma heurística construtiva, duas variantes de busca local, e um algoritmo GRASP foram propostos para resolver um dos modelos. Resultados computacionais com uma instância real e conjuntos de instâncias geradas aleatoriamente indicam que tanto os métodos exatos como heurísticos propostos são capazes de gerar programações da produção tão boas ou melhores do que as atualmente empregadas pela empresa estudada

Em diversas indústrias de manufatura (por exemplo, papeleira, moveleira, metalúrgica, têxtil) as decisões do dimensionamento de lotes interagem com outras decisões do planejamento e programação da produção, tais como, a distribuição, o processo de corte, entre outros. Porém, usualmente, essas decisões são tratadas de forma isolada, reduzindo o espaço de soluções e a interdependência entre as decisões, elevando assim os custos totais. Nesta tese, estudamos o processo produtivo de indústrias de móveis de pequeno porte, que consiste em cortar placas grandes disponíveis em estoque para obter diversos tipos de peças que são processadas posteriormente em outros estágios e equipamentos com capacidades limitadas para, finalmente, comporem os produtos demandados. Os problemas de dimensionamento de lotes e corte de estoque são acoplados em um modelo de otimização linear inteiro cujo objetivo é minimizar os custos de produção, estoque de produtos, preparação de máquinas e perda de matéria-prima. Esse modelo mostra o compromisso existente entre antecipar ou não a fabricação de certos produtos aumentando os custos de estoque, mas reduzindo a perda de matéria-prima ao obter melhores combinações entre as peças. O impacto da incerteza da demanda (composta pela carteira de pedidos e mais uma quantidade extra estimada) foi amortizado pela estratégia de horizonte de planejamento rolante e por variáveis de decisão que representam uma produção extra para a demanda esperada no melhor momento, visando a minimização dos custos totais. Dois métodos heurísticos são desenvolvidos para resolver uma simplificação do modelo matemático proposto, o qual possui um alto grau de complexidade. Os experimentos computacionais realizados com exemplares gerados a partir de dados reais coletados em uma indústria de móveis de pequeno porte, uma análise dos resultados, as conclusões e perspectivas para este trabalho são apresentados / In the many manufacturing industries (e.g., paper industry, furniture, steel, textile), lot-sizing decisions generally arise together with other decisions of planning production, such as distribution, cutting, scheduling and others. However, usually, these decisions are dealt with separately, which reduce the solution space and break dependence on decisions, increasing the total costs. In this thesis, we study the production process that arises in small scale furniture industries, which consists basically of cutting large plates available in stock into several thicknesses to obtain different types of pieces required to manufacture lots of ordered products. The cutting and drilling machines are possibly bottlenecks and their capacities have to be taken into account. The lot-sizing and cutting stock problems are coupled with each other in a large scale linear integer optimization model, whose objective function consists in minimizing different costs simultaneously, production, inventory, raw material waste and setup costs. The proposed model captures the tradeoff between making inventory and reducing losses. The impact of the uncertainty of the demand, which is composed with ordered and forecasting products) was smoothed down by a rolling horizon strategy and by new decision variables that represent extra production to meet forecasting demands at the best moment, aiming at total cost minimization. Two heuristic methods are proposed to solve relaxation of the mathematical model. Randomly generated instances based on real world life data were used for the computational experiments for empirical analyses of the model and the proposed solution methods