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

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

Neste trabalho, estudamos o problema de corte bidimensional multiperíodo com sobras aproveitáveis, que consiste em cortar objetos grandes visando a produção de um conjunto de itens menores. Supomos um horizonte de planejamento finito com uma quantidade finita de períodos entre os tempos inicial e final. Primeiramente consideramos uma versão determinística em que conhecemos, à priori, os itens solicitados em uma ordem de trabalho e o custo dos objetos a cada período. Algumas das sobras geradas durante o processo de corte dos itens solicitados em um período podem ser utilizadas como objetos no futuro. As sobras que podem ser usadas no futuro são denominadas sobras aproveitáveis. De forma geral, uma sobra é considerada aproveitável se possui dimensões iguais ou superiores as de algum item de uma lista pré-definida para o período. O objetivo é minimizar o custo total dos objetos utilizados para satisfazer a ordem de trabalho dos itens solicitados de todo o horizonte considerado. Havendo soluções com o mesmo custo, desejamos encontrar aquela que, no fim do horizonte de tempo considerado, maximize o valor das sobras aproveitáveis remanescentes. Apresentamos uma modelagem matemática do problema usando uma formulação em dois níveis, que é transformada em um modelo de programação linear inteira mista, devido às características do problema. Considerando a dificuldade em resolver o modelo desenvolvido, apresentamos uma proposta de uma abordagem heurística baseada em Programação Dinâmica Aproximada (PDA) para lidar com o problema proposto. Outras opções baseadas em estratégias do tipo horizonte rolante e relax-and-fix também são consideradas. Consideramos também o cenário onde não conhecemos de antemão os itens da ordem de trabalho e o custo dos objetos, mas temos informações das distribuições de probabilidade de ambos. Nesse caso, apresentamos uma abordagem baseada em programação dinâmica aproximada para estimar a melhor estratégia a ser seguida em cada período. Comparamos os resultados obtidos pela PDA com os resultados encontrados por um método guloso. Em cenários adequados, os resultados mostram que a PDA consegue soluções superiores ao método guloso. / In this research, we study the multi-period two-dimensional cutting problem with usable leftover, which consists of cutting objects to produce a set of items. We assume a finite planning horizon with a finite amount of periods between the initial and final times. First we consider a deterministic version in which we know, a priori, the set of ordered items and the cost of the objects at each period. Some of the leftovers generated during the cutting process of the ordered items in a period may be used as objects in the future. The leftovers that can be used in the future are called usable leftovers. In general, a leftover is considered usable if it has dimensions equal to or greater than that of some item from a predefined list for the period. The goal is to minimize the total cost of the objects used to cut the set of ordered items of the entire considered horizon. If there are solutions with the same cost, we wish to find one that, at the end of the considered time horizon, maximizes the value of the remaining usable leftovers. We present a mathematical model of the problem using a bilevel formulation, which is transformed into a mixed integer linear programming model, due to the characteristics of the problem. Considering the difficulty in solving the developed model, we propose a heuristic approach based on approximate dynamic programming (ADP) to deal with the proposed problem. Other options based on the rolling horizon and relax-and-fix strategies are also considered. We also consider the scenario where we do not know in advance the set of ordered items and the cost of the objects, but we have information about the probability distributions of both. In this case, we present an approach based on approximate dynamic programming to estimate the best strategy to be followed at each period. We compared the results obtained by the ADP with the results found by a greedy method. In suitable scenarios, the results show that the ADP achieves superior solutions to the greedy method.

Neste trabalho, estudamos o problema de corte bidimensional multiperíodo com sobras aproveitáveis, que consiste em cortar objetos grandes visando a produção de um conjunto de itens menores. Supomos um horizonte de planejamento finito com uma quantidade finita de períodos entre os tempos inicial e final. Primeiramente consideramos uma versão determinística em que conhecemos, à priori, os itens solicitados em uma ordem de trabalho e o custo dos objetos a cada período. Algumas das sobras geradas durante o processo de corte dos itens solicitados em um período podem ser utilizadas como objetos no futuro. As sobras que podem ser usadas no futuro são denominadas sobras aproveitáveis. De forma geral, uma sobra é considerada aproveitável se possui dimensões iguais ou superiores as de algum item de uma lista pré-definida para o período. O objetivo é minimizar o custo total dos objetos utilizados para satisfazer a ordem de trabalho dos itens solicitados de todo o horizonte considerado. Havendo soluções com o mesmo custo, desejamos encontrar aquela que, no fim do horizonte de tempo considerado, maximize o valor das sobras aproveitáveis remanescentes. Apresentamos uma modelagem matemática do problema usando uma formulação em dois níveis, que é transformada em um modelo de programação linear inteira mista, devido às características do problema. Considerando a dificuldade em resolver o modelo desenvolvido, apresentamos uma proposta de uma abordagem heurística baseada em Programação Dinâmica Aproximada (PDA) para lidar com o problema proposto. Outras opções baseadas em estratégias do tipo horizonte rolante e relax-and-fix também são consideradas. Consideramos também o cenário onde não conhecemos de antemão os itens da ordem de trabalho e o custo dos objetos, mas temos informações das distribuições de probabilidade de ambos. Nesse caso, apresentamos uma abordagem baseada em programação dinâmica aproximada para estimar a melhor estratégia a ser seguida em cada período. Comparamos os resultados obtidos pela PDA com os resultados encontrados por um método guloso. Em cenários adequados, os resultados mostram que a PDA consegue soluções superiores ao método guloso. / In this research, we study the multi-period two-dimensional cutting problem with usable leftover, which consists of cutting objects to produce a set of items. We assume a finite planning horizon with a finite amount of periods between the initial and final times. First we consider a deterministic version in which we know, a priori, the set of ordered items and the cost of the objects at each period. Some of the leftovers generated during the cutting process of the ordered items in a period may be used as objects in the future. The leftovers that can be used in the future are called usable leftovers. In general, a leftover is considered usable if it has dimensions equal to or greater than that of some item from a predefined list for the period. The goal is to minimize the total cost of the objects used to cut the set of ordered items of the entire considered horizon. If there are solutions with the same cost, we wish to find one that, at the end of the considered time horizon, maximizes the value of the remaining usable leftovers. We present a mathematical model of the problem using a bilevel formulation, which is transformed into a mixed integer linear programming model, due to the characteristics of the problem. Considering the difficulty in solving the developed model, we propose a heuristic approach based on approximate dynamic programming (ADP) to deal with the proposed problem. Other options based on the rolling horizon and relax-and-fix strategies are also considered. We also consider the scenario where we do not know in advance the set of ordered items and the cost of the objects, but we have information about the probability distributions of both. In this case, we present an approach based on approximate dynamic programming to estimate the best strategy to be followed at each period. We compared the results obtained by the ADP with the results found by a greedy method. In suitable scenarios, the results show that the ADP achieves superior solutions to the greedy method.

[pt] Este estudo apresenta um modelo de programação inteira mista para a roteirização de navios com controle de estoque nos portos para a movimentação de múltiplos produtos com uma frota heterogênea. O modelo contempla a possibilidade de transformação de produtos dentro de navios, o que representa uma flexibilidade para o modelo optar por qual produto utilizar para atender um cliente com demanda com qualidade flexível. Esta habilidade não foi encontrada em nenhum outro estudo. Ele também combina o atendimento de demandas obrigatórias com opcionais. O modelo então é aplicado em um caso real de movimentação de derivados escuros de petróleo em uma empresa de petróleo brasileira, cujo modelo atual utilizado apresenta problemas que dificultam seu uso. Devido ao longo tempo que leva para obter a solução ótima para estes tipos de modelos, são utilizadas as matheurísticas de relax-and-fix e fix-and-optimize para obter soluções boas em um tempo reduzido. São apresentados experimentos computacionais em uma série de cenários para validar a qualidade das soluções encontradas pelos métodos propostos, testando diferentes configurações e discretizações de tempo. Os resultados apresentados comprovam a superioridade dos métodos em comparação com o modelo matemático puro. O modelo proposto apresentou grande potencial de substituir o modelo atual da empresa e para alcançar a melhoria pretendida na programação dos navios. / [en] This dissertation presents a mixed integer program model to solve a ship routing and scheduling with stock control in ports, also known as maritime inventory routing. This model considers a heterogeneous fleet, carrying multiples products. It also has the ability to transform one product into another inside ships. This aspect allows the model to choose which product it wishes to deliver to a client with a less restrict quality specification in his demand. No model presented in other studies has this capability. Another possibility covered by this model is to combine mandatory demands with optional ones. The model is applied to a real case of maritime transportation of dirty oil products in a Brazilian oil company, whose current model has a series of small problems that hinders its use. Due to the long time it takes to get the optimal solution, the relax-and-fix and fix-andoptimize heuristics are used to get good solutions in a reduced time. With the use of computational experiments in a series of scenarios, it has proved the quality of the solutions found by the proposed methods, testing different configurations and discretizations of time. The results presented prove the superiority of the methods in comparison to the pure mathematical model. The proposed model has shown great potential to replace the current one and to achieve the improvement for the ship routing intended by the company.

O presente trabalho trata do problema integrado de dimensionamento e sequenciamento de lotes de produção. O processo de dimensionar e sequenciar lotes de produção consiste em determinar quanto produzir de cada produto e a sequência de produção desses lotes em cada máquina a cada período a fim de atender a uma demanda prevista sob as condições e capacidades operacionais existentes. O caso estudado nesse trabalho aborda o cenário de uma empresa de grande porte da indústria de bens de consumo de higiene pessoal, um mercado bastante concorrido no qual o bom nível de serviço de atendimento e a gestão de custos mostram-se essenciais na competição pelos clientes. Nessa empresa, existe um ambiente operacional complexo, composto por máquinas distintas em paralelo com capacidade limitada de produção cujos tempos de preparação (setup) são dependentes da sequência de produção, além de uma restrição de capacidade de armazenagem dos produtos fabricados, característica não encontrada na literatura existente. Os clientes permitem que ocorram atrasos de atendimento da demanda, porém isso é extremamente indesejável. Esse tipo de problema é NP-difícil, sendo geralmente tratado na literatura por heurísticas. Nesse trabalho, elaboramos nove diferentes estratégias de resolução baseadas na heurística relax-and-fix. O objetivo é, não somente resolver um problema real complexo, como também avaliar se o modo de articionamento e a sequência de resolução dos subproblemas influencia no desempenho da heurística. Os testes computacionais foram conduzidos em instâncias geradas aleatoriamente e em casos reais. Os resultados mostraram um bom desempenho e robustez da abordagem proposta. Técnicas alternativas foram aplicadas na estratégia com os melhores resultados para potencializar seu desempenho. / This work adresses the integrated lot sizing and scheduling problem. The process of lot sizing and scheduling consists of determining how much to produce of each product and the scheduling of these lots in each machine in order to meet the demand under existing restrictions and operational capabilities. The case studied in this work describes the scenario of a big company in the industry of consumer goods for personal hygiene, a very competitive market in which the good service level for customers and the cost management show up in the competition for the clients. In this company, there is a complex operational environment, composed of distinct parallel machines with limited production capacity and sequence dependente setup times. There is also a limited finished goods storage capacity, a characteristic not found in the existing literature. Backordering is allowed but it is extremely undesirable. This problem is NP-hard and it has been treated by heuristics in the literature. In this work, we developed nine different solving strategies based on the relax-and-fix heuristics. The aim of this approach is not only to solve a complex real problem but also assess whether the form of partitioning and the sequence of solving the subproblems influences the performance of the relax-and-fix heuristics. The computational experiments were conducted on ramdomly generated instances and real problems. The results showed the good performance and the robustness of the proposed approach. Alternative techniques were applied in the strategy with the best results in the previous tests to enhance its performance.

Submitted by JACKELINE DEL CARMEN HUACCHA NEYRA null (jacky_157_93@hotmail.com) on 2017-03-24T15:38:11Z No. of bitstreams: 1 dissertação jackeline.pdf: 1416143 bytes, checksum: 3865afc18803fe4e45d315a9ee3afaf9 (MD5) / Approved for entry into archive by Luiz Galeffi (luizgaleffi@gmail.com) on 2017-03-24T18:02:08Z (GMT) No. of bitstreams: 1 huacchaneyra_jc_me_sjrp.pdf: 1416143 bytes, checksum: 3865afc18803fe4e45d315a9ee3afaf9 (MD5) / Made available in DSpace on 2017-03-24T18:02:08Z (GMT). No. of bitstreams: 1 huacchaneyra_jc_me_sjrp.pdf: 1416143 bytes, checksum: 3865afc18803fe4e45d315a9ee3afaf9 (MD5) Previous issue date: 2017-03-13 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / Os problemas de dimensionamento de lotes consistem em determinar a quantidade de itens que devem ser produzidos em todos os períodos de um horizonte de planejamento. Em geral, são considerados custos de produção, preparação de máquina e de manutenção de estoque. Neste trabalho estuda-se uma extensão do problema de dimensionamento de lotes com restrição de capacidade que considera tempos de preparação, preparação carryover e crossover, em que se tem uma única máquina, único estágio, multi-itens e big-bucket (CLSP-SCC). Novas formulações para o CLSP-SCC são apresentadas e evitam a necessidade de definir novas variáveis binárias para modelar a preparação crossover. Também são propostas restrições de quebra de simetria para formulações propostas na literatura. São provadas as relações teóricas que existem entre cada uma destas formulações estudadas. Além disso, é proposta uma heurística híbrida que combina as heurísticas Relax-and-Fix e Fix-and-Optimize (RF-FO), em que a heurística Relax-and-Fix é usada para obter uma solução inicial e a heurística Fix-and-Optimize melhora essa solução. Por fim, apresentam-se os resultados computacionais e conclui-se que os resultados obtidos melhoram significativamente quando comparam-se a formulação clássica com as formulações sem preparação carryover. Compara-se também os resultados da heurística com os do pacote computacional CPLEX e, quando ambos são limitados ao mesmo tempo computacional, a heurística RF-FO obtém melhores resultados. / Lot-Sizing Problems consist of determining the quantity of items to be produced in each period of a planning horizon. In general, production, setup and inventory costs are considered. In this work an extension of the Capacitated Lot-Sizing Problem is studied, which considers setup times, Setup Carryover and Setup Crossover, single machine, single level, multi items, multi periods and big-bucket (CLSP-SCC). New formulations to the CLSP-SCC are presented and avoid the necessity of defining new extra binary variables to model the setup crossover. Furthermore, symmetry breaking constraints are proposed for formulations from the literature. The theoretical relations between the studied formulations are proved. A Relax-and-Fix and Fixand-Optimize (RF-FO) hybrid heuristic is proposed, in which the Relax-and-Fix helps to find an initial solution and the Fix-and-Optimize improves it. Computational results are presented and the obtained results improve significantly when comparing the classical formulation with the formulation without setup carryover. Finally, the results obtained by the RF-FO heuristic and the computational package CPLEX are compared and, when they both are limited to the same computational time, the RF-FO heuristic obtains better results.

Submitted by GISLAINE MARA MELEGA null (gis_laine_m@hotmail.com) on 2017-03-27T18:20:11Z No. of bitstreams: 1 TESE_Gislaine Melega_Matemática.pdf: 2710288 bytes, checksum: 9c3a4e388e7584cf0423182dcfdcced8 (MD5) / Approved for entry into archive by Luiz Galeffi (luizgaleffi@gmail.com) on 2017-03-29T19:23:05Z (GMT) No. of bitstreams: 1 melega_gm_dr_sjrp.pdf: 2710288 bytes, checksum: 9c3a4e388e7584cf0423182dcfdcced8 (MD5) / Made available in DSpace on 2017-03-29T19:23:05Z (GMT). No. of bitstreams: 1 melega_gm_dr_sjrp.pdf: 2710288 bytes, checksum: 9c3a4e388e7584cf0423182dcfdcced8 (MD5) Previous issue date: 2017-02-21 / Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP) / 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 para este tipo de problema, com três níveis e vários períodos, é estudado a partir do desenvolvimento de métodos de solução considerando abordagens que superam as dificuldades do problema, que consistem no alto número de padrões de corte, estruturas em vários níveis (multiestágios) e variáveis binárias de preparo. Os métodos de solução propostos para o problema GILSCS são baseados em duas abordagens conhecidas da literatura, usadas com sucesso para resolver os problemas separadamente, que são o procedimento de geração de colunas e heurísticas de decomposição do tipo relax-and-fix. Estas estratégias e suas variações são combinadas à um pacote de otimização em um estudo computacional com dados gerados aleatoriamente. Uma revisão da literatura, em termos de métodos de solução, para o problema integrado também é apresentada. Outras contribuições desta tese consistem em propor diferentes modelos matemáticos para o problema integrado, combinando modelos alternativos para cada um dos problemas separadamente. Neste estudo, o objetivo é comparar e avaliar, com um extensivo estudo computacional, a qualidade e o impacto das diferentes formulações. O outro trabalho trata de uma aplicação do problema integrado em um indústria de móveis de pequeno porte, em que restrições específicas do ambiente industrial são abordadas, como estoque de segurança e ciclos da serra. A solução obtida pelo modelo proposto é comparada com uma simulação da prática da empresa. / 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 development of solution approaches that overcome the difficulties of the problem, which are the high number of cutting patterns, multi-level structures and the binary values of the setup variables. The solution methods proposed to the GILSCS problem are based on two known strategies from the literature which are used successfully to solve the problems separately, which are the column generation procedure and decomposition heuristics based on relax-and-fix procedure. These strategies and their variations are combined into an optimization package in a computational study with randomly generated data. A literature review, in terms of solution methods, to the integrated problem, is also presented. Other contributions of this thesis consist of proposing different mathematical models for the integrated problem combining alternative models for each one of the problems separately. In this study, the aim is to compare and evaluate, with an extensive computational study, the quality and the impact of these dfifferent formulations. Another study is an application of the integrated problem in a small furniture factory, in which specific constraints related to the industrial environment are addressed, such as, safety stock level constraints and saw cycles constraints. The solution obtained from the proposed model is compared to a simulation of the common practice in the company. / FAPESP: 2012/20631-2

[pt] O problema de roteamento de navios com gestão de estoques (conhecido pelo termo em inglês Maritime inventory routing ou MIR) representa um problema prático de logística onde o transportador da carga também é responsável pela manutenção dos estoques do produto transportado nos portos de carga e descarga. Esta tese estuda um caso real do problema MIR. Um conjunto de testes é apresentado de modo a comparar diferentes formulações matemáticas da literatura, a fim de encontrar aquela mais aderente ao problema real. Em função da complexidade computacional do problema, é apresentada uma abordagem heurística que consegue encontrar soluções similares e reduz consideravelmente o tempo computacional quando comparadas com as formulações baseadas em PLIM. No entanto, problemas reais são muito influenciados por aspectos incertos. Sendo assim, é apresentada uma abordagem robusta para a otimização do problema MIR, que considera incerteza no tempo de estadia do navio nos portos. A abordagem apresentada produz soluções para diferentes níveis de robustez. Em outras palavras, considera o risco de variação no tempo de estadia do navio em um porto durante uma operação de carga ou descarga. Assim, é capaz de determinar a probabilidade de inviabilidade da solução encontrada para cada nível de robustez oferecido, além do impacto no custo de transporte à medida que soluções mais robustas são apresentadas. Esta abordagem oferece ao tomador de decisão a medida do trade-off entre robustez e custo de transporte. Desta forma, o mesmo pode determinar qual o nível de conservadorismo irá adotar em sua programação de navios e quanto isto irá impactar o custo de transporte. Os experimentos apresentados identificaram que, aumentos sutís no nível de robustez (com pequeno impacto no custo de transporte) podem reduzir consideravelmente a probabilidade de inviabilidade de uma solução. / [en] Maritime inventory routing (MIR) problem is an academic name for a practical logistic problem that represents the routing or scheduling of vessels to carry product(s) between ports. Meanwhile, the product(s) inventory levels in these ports must remain between operational bounds during the entire planning horizon. This thesis focus on how to support decision on a real-life MIR problem faced by a Brazilian petroleum company. To do so, we structure a set of tests to compare different formulation from literature and identify which is more adherent to real problem. Due to computational complexity of the problem, we present an heuristic approach that provides reasonably good solutions when compared to deterministic mixed integer linear programming (MILP) formulations and reduces considerably the computational time of solving real-life instances. However, uncertainty events have great impact in the ship scheduling planning. Therefore, we propose a robust optimization approach that considers uncertainty in the time spent at ports in each ship visit. Our approach is able to determine the probability of infeasibility and the impact in the objective function for each level of robustness, helping to measure the uncertain aversion of the decision maker. Our experiments identified that, for a certain instance, varying the level of robustness one may reduce the probability of infeasibility from 87 per cent (of deterministic solution) to 2 per cent and it represents an increase in the transportation costs of about 13 per cent.

O presente trabalho trata do problema integrado de dimensionamento e sequenciamento de lotes de produção. O processo de dimensionar e sequenciar lotes de produção consiste em determinar quanto produzir de cada produto e a sequência de produção desses lotes em cada máquina a cada período a fim de atender a uma demanda prevista sob as condições e capacidades operacionais existentes. O caso estudado nesse trabalho aborda o cenário de uma empresa de grande porte da indústria de bens de consumo de higiene pessoal, um mercado bastante concorrido no qual o bom nível de serviço de atendimento e a gestão de custos mostram-se essenciais na competição pelos clientes. Nessa empresa, existe um ambiente operacional complexo, composto por máquinas distintas em paralelo com capacidade limitada de produção cujos tempos de preparação (setup) são dependentes da sequência de produção, além de uma restrição de capacidade de armazenagem dos produtos fabricados, característica não encontrada na literatura existente. Os clientes permitem que ocorram atrasos de atendimento da demanda, porém isso é extremamente indesejável. Esse tipo de problema é NP-difícil, sendo geralmente tratado na literatura por heurísticas. Nesse trabalho, elaboramos nove diferentes estratégias de resolução baseadas na heurística relax-and-fix. O objetivo é, não somente resolver um problema real complexo, como também avaliar se o modo de articionamento e a sequência de resolução dos subproblemas influencia no desempenho da heurística. Os testes computacionais foram conduzidos em instâncias geradas aleatoriamente e em casos reais. Os resultados mostraram um bom desempenho e robustez da abordagem proposta. Técnicas alternativas foram aplicadas na estratégia com os melhores resultados para potencializar seu desempenho. / This work adresses the integrated lot sizing and scheduling problem. The process of lot sizing and scheduling consists of determining how much to produce of each product and the scheduling of these lots in each machine in order to meet the demand under existing restrictions and operational capabilities. The case studied in this work describes the scenario of a big company in the industry of consumer goods for personal hygiene, a very competitive market in which the good service level for customers and the cost management show up in the competition for the clients. In this company, there is a complex operational environment, composed of distinct parallel machines with limited production capacity and sequence dependente setup times. There is also a limited finished goods storage capacity, a characteristic not found in the existing literature. Backordering is allowed but it is extremely undesirable. This problem is NP-hard and it has been treated by heuristics in the literature. In this work, we developed nine different solving strategies based on the relax-and-fix heuristics. The aim of this approach is not only to solve a complex real problem but also assess whether the form of partitioning and the sequence of solving the subproblems influences the performance of the relax-and-fix heuristics. The computational experiments were conducted on ramdomly generated instances and real problems. The results showed the good performance and the robustness of the proposed approach. Alternative techniques were applied in the strategy with the best results in the previous tests to enhance its performance.