Esta tese aborda um problema de dimensionamento e sequenciamento de lotes de produção baseado em uma indústria alimentícia brasileira que opera por meio de diversas linhas de produção heterogêneas. Nesse ambiente produtivo, as linhas de produção compartilham recursos escassos, tais como, trabalhadores e máquinas e devem ser montadas (ativadas) em cada período produtivo, respeitando-se a capacidade disponível de cada recurso necessário para ativação das mesmas. Modelos de programação matemática inteira mista são propostos para representação do problema, bem como diversos métodos heurísticos de solução, compreendendo procedimentos construtivos e de melhoramento baseados na formulação matemática do problema e heurísticas lagrangianas. São propostas heurísticas do tipo relax-and-fix explorando diversas partições das variáveis binárias dos modelos e uma heurística baseada na decomposição do modelo para construção de soluções. Procedimentos do tipo fix-and-optimize e matheuristics do tipo iterative MIP-based neighbourhood search são propostas para o melhoramento das soluções iniciais obtidas pelos procedimentos construtivos. Testes computacionais são realizados com instâncias geradas aleatoriamente e mostram que os métodos propostos são capazes de oferecer melhores soluções do que o algoritmo Branch-and-Cut de um resolvedor comercial para instâncias de médio e grande porte. / This doctoral dissertation addresses the simultaneous lot sizing and scheduling problem in a real world production environment where production lines share scarce production resources. Due to the lack of resources, the production lines cannot operate all simultaneously and they need to be assembled in each period respecting the capacity constraints of the resources. This dissertation presents mixed integer programming models to deal with the problem as well as various heuristic approaches: constructive and improvement procedures based on the mathematical formulation of the problem and lagrangian heuristics. Relax-and-fix heuristics exploring some partitions of the set of binary variables of a model and a decomposition based heuristic are proposed to construct solutions. Fix-and-optimize heuristics and iterative MIP-based neighbourhood search matheuristics are proposed to improvement solutions obtained by constructive procedures. Computational tests are performed with randomly instances and show that the proposed methods can find better solutions than the Branch-and-Cut algorithm of a commercial solver for medium and large size instances.

Esta tese aborda um problema de dimensionamento e sequenciamento de lotes de produção baseado em uma indústria alimentícia brasileira que opera por meio de diversas linhas de produção heterogêneas. Nesse ambiente produtivo, as linhas de produção compartilham recursos escassos, tais como, trabalhadores e máquinas e devem ser montadas (ativadas) em cada período produtivo, respeitando-se a capacidade disponível de cada recurso necessário para ativação das mesmas. Modelos de programação matemática inteira mista são propostos para representação do problema, bem como diversos métodos heurísticos de solução, compreendendo procedimentos construtivos e de melhoramento baseados na formulação matemática do problema e heurísticas lagrangianas. São propostas heurísticas do tipo relax-and-fix explorando diversas partições das variáveis binárias dos modelos e uma heurística baseada na decomposição do modelo para construção de soluções. Procedimentos do tipo fix-and-optimize e matheuristics do tipo iterative MIP-based neighbourhood search são propostas para o melhoramento das soluções iniciais obtidas pelos procedimentos construtivos. Testes computacionais são realizados com instâncias geradas aleatoriamente e mostram que os métodos propostos são capazes de oferecer melhores soluções do que o algoritmo Branch-and-Cut de um resolvedor comercial para instâncias de médio e grande porte. / This doctoral dissertation addresses the simultaneous lot sizing and scheduling problem in a real world production environment where production lines share scarce production resources. Due to the lack of resources, the production lines cannot operate all simultaneously and they need to be assembled in each period respecting the capacity constraints of the resources. This dissertation presents mixed integer programming models to deal with the problem as well as various heuristic approaches: constructive and improvement procedures based on the mathematical formulation of the problem and lagrangian heuristics. Relax-and-fix heuristics exploring some partitions of the set of binary variables of a model and a decomposition based heuristic are proposed to construct solutions. Fix-and-optimize heuristics and iterative MIP-based neighbourhood search matheuristics are proposed to improvement solutions obtained by constructive procedures. Computational tests are performed with randomly instances and show that the proposed methods can find better solutions than the Branch-and-Cut algorithm of a commercial solver for medium and large size instances.

Um importante problema de programação da produção surge em indústrias de papel integrando o problema de planejamento em múltiplas máquinas paralelas com o problema de corte. O problema de dimensionamento de lotes deve determinar a quantidade de jumbos (bobinas grandes de papel) de diferentes tipos de papel a serem produzidos em cada máquina. Estes jumbos são então cortados para atender a demanda de itens (bobinas menores de papel). O planejamento, que minimiza custos de produção e preparação, deve produzir jumbos (cada máquina produz jumbos de larguras diferentes) que diminuam a perda no processo de corte. Por outro lado, o melhor número de jumbos do ponto de vista de minimizar a perda no processo de corte pode acarretar em altos custos de preparação. Ambos são problemas de otimização combinatória não trivial, o que tem motivado extensas pesquisas nas últimas décadas, entretanto, essa combinação não é bem explorada na literatura. Neste trabalho, são propostos um modelo de otimização integrado e métodos heurísticos de solução. Foram realizados experimentos computacionais com o intuito de analisar o desempenho dos métodos propostos e os resultados apresentaram- se bastante satisfatórios, significando que tais métodos são apropriados para tratar o problema integrado. / An important production programming problem arises in paper industries coupling mul- tiple machine scheduling with cutting stock. From machine scheduling the problem of determining the quantity of jumbos (large rolls of paper) of different types of paper to be produced in each machine arises. These jumbos are then cut to meet the demand for items (smaller rolls of paper). Scheduling that minimizes setups and production costs may produce jumbos (each machine produces jumbos of a specific width) which may increase waste in the cutting process. On the other hand, the best number of jumbos in the point of view of minimizing waste in the cutting process may lead to high setup costs. Both problems are non-trivial combinatorial optimization problems, which have motivated ex- tensive research in the last decades, however their combination is not well explored in the literature. In this work, a coupled optimization modelling and heuristic solution methods are proposed. Computational experiments are devised in order to analyze the performance of the methods and the results had been presented sufficiently satisfactory, meaning that such methods are appropriate to deal with the integrated problem.

Um importante problema de programação da produção surge em indústrias de papel integrando o problema de planejamento em múltiplas máquinas paralelas com o problema de corte. O problema de dimensionamento de lotes deve determinar a quantidade de jumbos (bobinas grandes de papel) de diferentes tipos de papel a serem produzidos em cada máquina. Estes jumbos são então cortados para atender a demanda de itens (bobinas menores de papel). O planejamento, que minimiza custos de produção e preparação, deve produzir jumbos (cada máquina produz jumbos de larguras diferentes) que diminuam a perda no processo de corte. Por outro lado, o melhor número de jumbos do ponto de vista de minimizar a perda no processo de corte pode acarretar em altos custos de preparação. Ambos são problemas de otimização combinatória não trivial, o que tem motivado extensas pesquisas nas últimas décadas, entretanto, essa combinação não é bem explorada na literatura. Neste trabalho, são propostos um modelo de otimização integrado e métodos heurísticos de solução. Foram realizados experimentos computacionais com o intuito de analisar o desempenho dos métodos propostos e os resultados apresentaram- se bastante satisfatórios, significando que tais métodos são apropriados para tratar o problema integrado. / An important production programming problem arises in paper industries coupling mul- tiple machine scheduling with cutting stock. From machine scheduling the problem of determining the quantity of jumbos (large rolls of paper) of different types of paper to be produced in each machine arises. These jumbos are then cut to meet the demand for items (smaller rolls of paper). Scheduling that minimizes setups and production costs may produce jumbos (each machine produces jumbos of a specific width) which may increase waste in the cutting process. On the other hand, the best number of jumbos in the point of view of minimizing waste in the cutting process may lead to high setup costs. Both problems are non-trivial combinatorial optimization problems, which have motivated ex- tensive research in the last decades, however their combination is not well explored in the literature. In this work, a coupled optimization modelling and heuristic solution methods are proposed. Computational experiments are devised in order to analyze the performance of the methods and the results had been presented sufficiently satisfactory, meaning that such methods are appropriate to deal with the integrated problem.

O problema de planejamento da produção integrado ao problema de corte de estoque surge em várias indústrias de manufatura, tais como indústria de papel, móveis, aço entre outras, e consiste em um problema de otimização combinatória bastante complexo, devido ao fato de integrar dois problemas conhecidos na literatura de difícil resolução. As aplicações práticas deste problema vêm aumentando em muitas empresas que buscam tornar seus processos produtivos mais eficientes. Neste trabalho, estudamos o problema de otimização integrado que surge em pequenas indústrias de móveis, em que placas de MDF disponíveis em estoque devem ser cortadas em itens menores, de diversos tamanhos e quantidades para comporem os produtos demandados. O modelo matemático de otimização linear inteiro proposto permite que alguns produtos sejam antecipados e estocados. Essa antecipação da produção aumenta os custos de estoque, porém com o aumento da demanda de peças é possível gerar padrões de corte melhores e diminuir os custos com a perda de material. Consideramos no modelo dois tipos de variáveis de antecipação, uma de estoque convencional para atender uma demanda em carteira e outra para aproveitar a produção e atender uma demanda prevista, chamada variável oportunista. A função objetivo consiste em minimizar os custos dos processos de produção e de corte. Para resolver a relaxação linear deste problema, propomos um método lagrangiano e utilizamos a estratégia de horizonte rolante. Alguns testes computacionais são realizados e os resultados apresentados / The integrated problem of cutting stock and production planning arises in a several manufacturing industries, such as paper, furniture, steel among others, and it is a complex combinatorial optimization problem, due to the fact that it integrates two well-known NP problems of the literature. The real world applications of this problem have increased in many industries that search for more efficient production process. In this work, we studied an integrated optimization problem that arises in small furniture industries, where MDF boards available in inventory must be cut into enough quantities of items to compose demanded finish-goods. The model of integer linear optimization proposed allows anticipating some products and keeping them in inventory. This production anticipation makes increase the inventory costs, although makes it possible to determine better cutting patterns and decreases the costs of the cutting process. We consider in the model two types of anticipation variables, the first one to the ordinary inventory to meet ordered products and an other one, called chance variables, to meet a forecasting demand. The objective function is to minimize the costs of production process and waste of material. To solve a linear relaxation of this problem, we proposed lagrangian approach and used a rolling horizon strategy. Some computational tests are performed and results shown

A presente pesquisa considera o problema de programação de uma frota de embarcações de lançamentos de dutos, conhecidas como Pipe Layer Support Vessel (PLSVs), as quais fazem parte da frota de apoio marítimo de uma operação offshore. As embarcações do tipo PLSVs são responsáveis pelas tarefas de lançamento de dutos submarinos, que escoam a produção dos poços de petróleo, e pela interligação destes dutos à infraestrutura submarina. A programação da frota deve atender uma demanda de serviço conhecida, em um horizonte de médio prazo, respeitando restrições operacionais, visando minimizar o atraso ponderado total das tarefas ou evitar que existam atrasos. Foi desenvolvido um método para estimar o valor da solução ótima do problema, baseado na técnica de relaxação Lagrangiana, e um conjunto de heurísticas para gerar soluções viáveis para o problema. / This research considers the problem of scheduling a fleet of specialized vessels used for launching pipes and connecting them to the subsea infrastructure, in an offshore oil production environment. The Pipe Layer Support Vessels (PLSV) must be scheduled such that the demand is fully attended within the planning horizon, observing other operational constraints, with the purpose of minimizing the total weighted tardiness. The solution method is based on constructive and local search heuristics. Bounds on the optimal solution were derived by a Lagrangean relaxation algorithm.

Made available in DSpace on 2016-06-02T19:50:17Z (GMT). No. of bitstreams: 1 TeseLKO.pdf: 834201 bytes, checksum: 994d7b70c6b1001f9dec962fafc8b72e (MD5) Previous issue date: 2004-12-13 / Universidade Federal de Sao Carlos / The purpose of this work is to develop exact methods, based on Lagrangean and Surrogate relaxation, with good performance to solve the manufacturer s pallet loading problem. This problem consists of orthogonally arranging the maximum number of rectangles of sizes (l,w) and (w,l) into a larger rectangle (L,W) without overlapping. Such methods involve a tree search procedure of branch and bound type and they use, in each node of the branch and bound tree, bounds derived from Lagrangean and/or Surrogate relaxations of a 0-1 linear programming formulation. Subgradient optimization algorithms are used to optimize such bounds. Problem reduction tests and Lagrangean and Surrogate heuristics are also applied in the subgradient optimization to obtain good feasible solution. Computational experiments were performed with instances from the literature and also real instances obtained from a carrier. The results show that the methods are able to solve these instances, on average, more quickly than other exact methods, including the software GAMS/CPLEX. / O objetivo deste trabalho é desenvolver métodos exatos, baseados em relaxação Lagrangiana e Surrogate, com bom desempenho para resolver o problema de carregamento de paletes do produtor. Tal problema consiste em arranjar ortogonalmente e sem sobreposição o máximo número de retângulos de dimensões ( , ) l w ou ( , ) w l sobre um retângulo maior ( , ) L W . Tais métodos exatos são procedimentos de busca em árvore do tipo branch and bound que, em cada nó, utilizam limitantes derivados de relaxações Lagrangiana e/ou Surrogate de uma formulação de programação linear 0 1 − . Algoritmos de otimização do subgradiente são usados para otimizar estes limitantes. São aplicados ainda testes de redução do problema e heurísticas Lagrangiana e Surrogate na otimização do subgradiente para obter boas soluções factíveis. Testes computacionais foram realizados utilizando exemplos da literatura e exemplos reais, obtidos de uma transportadora. Os resultados mostram que os métodos são capazes de resolvê-los, em média, mais rapidamente do que outros métodos exatos, incluindo o software GAMS/CPLEX.

A presente pesquisa considera o problema de programação de uma frota de embarcações de lançamentos de dutos, conhecidas como Pipe Layer Support Vessel (PLSVs), as quais fazem parte da frota de apoio marítimo de uma operação offshore. As embarcações do tipo PLSVs são responsáveis pelas tarefas de lançamento de dutos submarinos, que escoam a produção dos poços de petróleo, e pela interligação destes dutos à infraestrutura submarina. A programação da frota deve atender uma demanda de serviço conhecida, em um horizonte de médio prazo, respeitando restrições operacionais, visando minimizar o atraso ponderado total das tarefas ou evitar que existam atrasos. Foi desenvolvido um método para estimar o valor da solução ótima do problema, baseado na técnica de relaxação Lagrangiana, e um conjunto de heurísticas para gerar soluções viáveis para o problema. / This research considers the problem of scheduling a fleet of specialized vessels used for launching pipes and connecting them to the subsea infrastructure, in an offshore oil production environment. The Pipe Layer Support Vessels (PLSV) must be scheduled such that the demand is fully attended within the planning horizon, observing other operational constraints, with the purpose of minimizing the total weighted tardiness. The solution method is based on constructive and local search heuristics. Bounds on the optimal solution were derived by a Lagrangean relaxation algorithm.

O problema de planejamento da produção integrado ao problema de corte de estoque surge em várias indústrias de manufatura, tais como indústria de papel, móveis, aço entre outras, e consiste em um problema de otimização combinatória bastante complexo, devido ao fato de integrar dois problemas conhecidos na literatura de difícil resolução. As aplicações práticas deste problema vêm aumentando em muitas empresas que buscam tornar seus processos produtivos mais eficientes. Neste trabalho, estudamos o problema de otimização integrado que surge em pequenas indústrias de móveis, em que placas de MDF disponíveis em estoque devem ser cortadas em itens menores, de diversos tamanhos e quantidades para comporem os produtos demandados. O modelo matemático de otimização linear inteiro proposto permite que alguns produtos sejam antecipados e estocados. Essa antecipação da produção aumenta os custos de estoque, porém com o aumento da demanda de peças é possível gerar padrões de corte melhores e diminuir os custos com a perda de material. Consideramos no modelo dois tipos de variáveis de antecipação, uma de estoque convencional para atender uma demanda em carteira e outra para aproveitar a produção e atender uma demanda prevista, chamada variável oportunista. A função objetivo consiste em minimizar os custos dos processos de produção e de corte. Para resolver a relaxação linear deste problema, propomos um método lagrangiano e utilizamos a estratégia de horizonte rolante. Alguns testes computacionais são realizados e os resultados apresentados / The integrated problem of cutting stock and production planning arises in a several manufacturing industries, such as paper, furniture, steel among others, and it is a complex combinatorial optimization problem, due to the fact that it integrates two well-known NP problems of the literature. The real world applications of this problem have increased in many industries that search for more efficient production process. In this work, we studied an integrated optimization problem that arises in small furniture industries, where MDF boards available in inventory must be cut into enough quantities of items to compose demanded finish-goods. The model of integer linear optimization proposed allows anticipating some products and keeping them in inventory. This production anticipation makes increase the inventory costs, although makes it possible to determine better cutting patterns and decreases the costs of the cutting process. We consider in the model two types of anticipation variables, the first one to the ordinary inventory to meet ordered products and an other one, called chance variables, to meet a forecasting demand. The objective function is to minimize the costs of production process and waste of material. To solve a linear relaxation of this problem, we proposed lagrangian approach and used a rolling horizon strategy. Some computational tests are performed and results shown

Submitted by Aelson Maciera (aelsoncm@terra.com.br) on 2017-09-26T19:15:52Z No. of bitstreams: 1 DissCDAC.pdf: 10114021 bytes, checksum: b3e4f52846924539caadab8587fe2250 (MD5) / Approved for entry into archive by Ronildo Prado (bco.producao.intelectual@gmail.com) on 2018-01-26T18:36:20Z (GMT) No. of bitstreams: 1 DissCDAC.pdf: 10114021 bytes, checksum: b3e4f52846924539caadab8587fe2250 (MD5) / Approved for entry into archive by Ronildo Prado (bco.producao.intelectual@gmail.com) on 2018-01-26T18:36:39Z (GMT) No. of bitstreams: 1 DissCDAC.pdf: 10114021 bytes, checksum: b3e4f52846924539caadab8587fe2250 (MD5) / Made available in DSpace on 2018-01-26T18:42:45Z (GMT). No. of bitstreams: 1 DissCDAC.pdf: 10114021 bytes, checksum: b3e4f52846924539caadab8587fe2250 (MD5) Previous issue date: 2017-03-10 / Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) / This work aims at treating the Dynamic Vehicle Allocation Problem (DVAP) in the context of the Brazilian Freight Transportation system. The problem consists of allocating empty vehicles to different terminals so as to attend the demand of freight transport during a predetermined planning horizon while maximizing the profit from these services. These type of decisions arise in customized freight transport services and in between-terminals operations of consolidation freight services. Given the size of the resulting models of real life problems confronted by third party logistics operators are large for using exact solution methods, heuristic methods have been used for giving good quality solution at the expense of optimality guarantee. In this context, the objective of this work is to contribute with solution methods that provide optimality guarantee or quality solution certificates for treating large-scale problems in reasonable computational times. The methods utilized are lagrangean relaxation, using subgradient optimization, and DantzigWolfe decomposition together with a lagrangian heuristic and factibilization method, respectively. Computational experiments are presented and analyzed for randomly generated instances and real-world instances from a brasilian freight operator. The latter method shows great potential for treating large-scale problems. / Este trabalho aborda o problema de Alocação Dinâmica de Veículos (PADV) no contexto de Transporte Rodoviário de Carga. O problema envolve alocar veículos de carga para atender a demanda de transporte de carga prevista entre terminais durante um horizonte de tempo multiperíodos e finito. O objetivo e maximizar o lucro gerado pelos serviços completados. Este tipo de decisões surge nos serviços de transporte de carga de lotação e na parcela de transporte de transferência dos serviços de transporte de carga consolidada. Dado que o tamanho dos problemas que enfrentam as transportadoras logísticas sÃo consideravelmente grandes parase resolver com métodos exatos em tempos computacionais aceitáveis, tem-se utilizado métodos heurísticos para dar boas soluções sem garantia de otimalidade mas em tempos toleráveis a estes problemas. Neste contexto, pretende-se contribuir com métodos de solução que proporcionem garantia de otimalidade e/ou boas soluções aproximadas, acompanhadas de certificados de otimalidade ou de qualidade de solução, para tratar problemas de porte em tempos razoáveis. Os métodos propostos estao baseados em relaxação lagrangiana, utilizando o método de otimização do subgradiente, e na decomposto de Dantzig Wolfe, utilizando a técnica de geração de colunas, além de heurísticas lagrangianas e de factibilização acopladas nestes métodos. Experimentos computacionais usando instâncias geradas aleatoriamente e baseados em dados reais de transportadoras brasileiras sao apresentados e analisados, para as duas abordagens, mostrando seus potenciais de aplicação pratica, principalmente para problemas de grande porte.