Made available in DSpace on 2016-06-02T19:52:05Z (GMT). No. of bitstreams: 1 6045.pdf: 14667118 bytes, checksum: f13a2c0983ea271f2e60ed298b158806 (MD5) Previous issue date: 2014-05-26 / Agência Nacional de Petróleo / This work studies the ship routing and scheduling problem in oil transportation from offshore platforms to inland terminals. It is motivated by a real situation in a Brazilian oil company. Brazil is one of the world's greatest oil producers and has around 80% of its oil explored in offshore mode. Thus, transportation costs play an important role in achieving operational excellence, and the recent growth trends for oil exploration in Brazil has transformed its operations and demanded agile and effective decision support systems for addressing the oil sector dynamism. This work's goal consists in developing and applying an optimization-based approach using a mixed integer linear programming model in real decision-making situations, along with a solution method based on mathematical programming (MIP-heuristics) in order to solve the model, such as relax-and-fix. The proposed model is inspired in a problem formulation for pickup and delivery with time windows (PDPTW) and heterogeneous fleet, where costs incurred for fuel consumption and fleet contracts is the objective function to be minimized. The pickup and delivery pairs are predetermined and the model's main decision refers to ship allocation to these pairs compounding a route. Furthermore, some additional constraints are modeled and proposed, such as terminal access and platform mooring limitation according to ship types, as well as product blend incompatibility. The model was implemented in a modeling language along with an optimizarion software. Computational experiments with the model and the heuristics are presented for different data sets supplied by the case study company. These experiments show the potential benefits of this approach for finding good solutions for the problem as well as the dificulty in finding solutions for realistic instances due to its NP-hard characteristics. / Este trabalho estuda o problema de roteirização e programação de navios que realizam o escoamento de petróleo das plataformas marítimas para terminais terrestres, motivado por uma situação real de uma empresa brasileira da indústria petrolífera. O Brasil é um dos maiores produtores mundiais de petróleo, e cerca de 80% de seu petróleo é explorado no mar. Dentro deste contexto, os custos de transporte desempenham um papel importante na busca pela excelência operacional e as tendências de crescimento da exploração de petróleo no Brasil têm tornado as operações mais complexas e demandantes de sistemas de apoio à decisão ágeis e eficazes que contemplem o dinamismo do setor petrolífero. O objetivo deste trabalho consiste em desenvolver e aplicar uma abordagem de otimização baseada em um modelo de programação linear inteira mista em situações reais de tomada de decisão, em conjunto com métodos de solução baseados em programação matemática (MIP-Heuristics) para resolver o modelo, como relax-and-fix. O modelo proposto é inspirado em uma formulação de problemas de coleta e entrega com janelas de tempo (pickup and delivery with time windows PDPTW) e frota heterogênea, no qual busca-se minimizar os custos decorrentes do consumo de combustível dos navios e contratos de afretamento. O modelo é do tipo origem-destino, no qual os pares coleta/entrega são pré-determinados e a decisão do modelo refere-se à alocação de navios para os diferentes pares, compondo uma rota. Além disso, são propostas restrições adicionais que contemplam limitações de acesso a terminais e de atracação em plataformas de acordo com os tipos de navio, além da incompatibilidade de mistura de produtos, entre outros. O modelo foi implementado utilizando uma linguagem de modelagem em conjunto com um software de otimização. Experimentos computacionais com o modelo e as heurísticas são apresentados para diferentes conjuntos de dados fornecidos pela empresa e comprovam o potencial das abordagens para encontrar boas soluções para o problema, mas também suas dificuldades para encontrar soluções para exemplares de tamanho realista, por tratar-se de um problema NP-difícil do ponto de vista de teoria de complexidade.

Este trabalho trata o problema multi-estágios de programação da produção em ambientes Flow Shop com máquinas paralelas, apresentando um estágio de produção dominante (máquina única), no qual os tempos de preparação (setup) da máquina são assimétricos e dependentes da seqüência de execução das tarefas. Tal ambiente é constituído de k estágios de produção, com k = {4, 7}, divididos em três etapas assim definidas: na etapa um, o número de estágios de produção pode variar de um até cinco e cada estágio será constituído de m1 máquinas paralelas idênticas , com m1 &#8712 {2, 3, 4}, o que determina m1 flow shops paralelos. A etapa dois constitui o estágio dominante d, cuja localização oscila dependendo do número de estágios das etapas um e três. Por ultimo, a etapa três, semelhante à etapa um, possui m2 máquinas paralelas idênticas, onde m2 &#8712 {2, 3, 4} e m1 e m2 são gerados aleatoriamente. Todas as tarefas são processadas nas três etapas e o critério de desempenho é a otimização da duração total da programação (makespan) e também a análise do deslocamento do estágio dominante. A programação das tarefas é feita separadamente em cada uma das etapas. Na primeira etapa foi utilizado o método heurístico N&M para cada um dos m1 flow shops paralelos. Para segunda etapa foram desenvolvidos quatro regras e dois métodos heurísticos construtivos com base nos problemas do caixeiro viajante (TSP). Na última etapa, a alocação das tarefas é feita por ordem de chegada na máquina disponível ou com menor carga. Não foram encontrados na literatura trabalhos que retratassem ambientes dessa natureza, logo os métodos desenvolvidos foram comparados entre si. A experimentação computacional analisou os resultados obtidos por meio da porcentagem de sucesso de cada regra, desvio relativo entre os resultados de cada regra, deslocamento da posição do estágio dominante, influência das ordens de grandeza dos tempos de processamento e setup e tempo médio de computação. / This dissertation deals with problem multi-periods of production scheduling of the in Flow Shop environment with parallel machines, presenting a period of dominant production (single machine), in which the setup times for the processing of the jobs is asymmetric and sequence dependent on the execution of the jobs. Such environment is constituted by k periods of production, with k = {4, 7} divided in to three stages defined as: First stage: In stage one the number of production periods can vary from one to five, and each period will be constituted of m1 &#8712 {2, 3, 4} identical parallel machines, determining m1 parallel flow shops. Stage two - It constitutes the dominant period d, whose localization oscillates between the periods of stages one and three. Finally stage three it is similar to stage one, and has m2 &#8712 {2, 3, 4} identical parallel machines, where m1 and m2 Randomly generated. All the jobs are processed in the three stages and the objective is to optimize the total time to complete the scheduling (makespan) and also to analyze the displacement of the dominant period position. The scheduling of the jobs was performed separately in each of the stages. In the first stage the heuristic method N&M was used for each m1 parallel flow shops. In the second stage four constructive rules and two heuristic methods were developed based on traveling salesman problems (TSP). In the last stage the allocation of the jobs was performed according to the arrival time of the available machine or with lesser load. This type of work has not been found in literature; therefore the developed methods were compared among themselves. The statistics used in order to evaluate the heuristic performances were the percentage of success (in finding the best solution), relative deviation and average computational time. The displacement of the dominant period position as well as the influence of the relation of setup-times and processing-times, were also studied. The results of computational experience are discussed.

O problema do sequenciamento da produção diz respeito à alocação das tarefas nas máquinas em um ambiente de fabricação, o qual vem sendo amplamente estudado. O sequenciamento pode variar em tamanho e complexidade dependendo do tipo de ambiente onde ele é aplicado, do número e tipos de restrições tecnológicas e da função objetivo do problema. A utilização de métodos de decisão para a solução de problemas de sequenciamento na indústria depende de modelos que sejam capazes de oferecer soluções para os problemas reais, que geralmente envolvem diversas restrições, os quais devem ser considerados simultaneamente. No presente trabalho o problema de sequenciamento da produção em ambientes flow shop permutacionais, com bloqueio com buffer zero, e com tempos de setup dependente da sequência e da máquina, com o objetivo de minimização do makespan é estudado, sendo este considerado um problema NP-Completo. O problema é pouco explorado na literatura. No presente trabalho é apresentado um procedimento de cálculo para o makespan e três métodos de solução para o problema: quatro limitantes inferiores para o procedimento Branch-and-Bound; quatro modelos MILP, sendo dois deles adaptados; e 28 modelos heurísticos construtivos adaptados para o problema. Os métodos desenvolvidos baseiam-se em propriedades matemáticas do problema que são apresentadas neste trabalho como limitante inferior e limitante superior. Dentre todos os modelos MILP, o modelo adaptado RBZBS1 obteve os melhores resultados para os problemas menores e o modelo desenvolvido TNZBS1 obteve os melhores desvios relativos médios do makespan para os problemas maiores, que não foram resolvidos dentro do limite de tempo computacional estipulado. O limitante inferior para o Branch-and-Bound LBTN2 foi melhor que os demais tanto no tempo computacional e no número de nós explorados como também no número de problemas não resolvidos e no desvio relativo médio do makespan. Foi realizado uma comparação entre o melhor modelo MILP e o melhor limitante inferior para o Branch-and-Bound, sendo que o último obteve melhores resultados para os problemas testados. Entre os métodos heurísticos adaptados, o PF foi o que obteve, de uma forma geral, os melhores resultados em todas as fases. / Production scheduling is defined as a problem of allocating jobs in machines in a production environment and it has been largely studied. The scheduling can vary in difficulty and complexity depending on the environment, the variety and types of technological restraints and the objective function of the problem. The use of decision making methods to solve scheduling problems in the industry needs models that are capable to solve real problems, that usually involve a big variety of restraints that have to be simultaneously studied. At the present work the scheduling problem in a permutational flow shop environment, considering blocking with zero buffer, and sequence and machine dependent setup times, with the objective of minimizing makespan is studied, which is considered a NP-Complete problem and little explored in literature. The work presents a calculation procedure for the makespan and three solution methods for the problem: four lower bounds for the Branch-and-Bound procedure; four MILP models, two of which are adapted; and 28 constructive heuristic methods adapted to the problem. The methods developed are based on mathematical properties of the problem that are presented in this work as a lower bound and an upper bound. Among all the MILP models, the adapted model RBZBS1 was the one to obtain the best results for the smaller problems, and the developed model TNZBS1 obtained the smallest mean relative deviation of the makespan for the bigger problems that were not solved within the specified computational time limit. The lower bound for the Branch-and-Bound LBTN2 obtained smaller computational times and number of explored nodes as well as the number of unsolved problems and the mean relative deviation for the makespan than all other lower bounds. Also, a comparison among the best MILP model and the best lower bound for the Branch-and-Bound was performed, being that the last obtained better results for the tested problems. Among the adapted heuristic methods, the PF heuristic was the one that obtained, in general, the better results in all phases.

O problema do sequenciamento da produção diz respeito à alocação das tarefas nas máquinas em um ambiente de fabricação, o qual vem sendo amplamente estudado. O sequenciamento pode variar em tamanho e complexidade dependendo do tipo de ambiente onde ele é aplicado, do número e tipos de restrições tecnológicas e da função objetivo do problema. A utilização de métodos de decisão para a solução de problemas de sequenciamento na indústria depende de modelos que sejam capazes de oferecer soluções para os problemas reais, que geralmente envolvem diversas restrições, os quais devem ser considerados simultaneamente. No presente trabalho o problema de sequenciamento da produção em ambientes flow shop permutacionais, com bloqueio com buffer zero, e com tempos de setup dependente da sequência e da máquina, com o objetivo de minimização do makespan é estudado, sendo este considerado um problema NP-Completo. O problema é pouco explorado na literatura. No presente trabalho é apresentado um procedimento de cálculo para o makespan e três métodos de solução para o problema: quatro limitantes inferiores para o procedimento Branch-and-Bound; quatro modelos MILP, sendo dois deles adaptados; e 28 modelos heurísticos construtivos adaptados para o problema. Os métodos desenvolvidos baseiam-se em propriedades matemáticas do problema que são apresentadas neste trabalho como limitante inferior e limitante superior. Dentre todos os modelos MILP, o modelo adaptado RBZBS1 obteve os melhores resultados para os problemas menores e o modelo desenvolvido TNZBS1 obteve os melhores desvios relativos médios do makespan para os problemas maiores, que não foram resolvidos dentro do limite de tempo computacional estipulado. O limitante inferior para o Branch-and-Bound LBTN2 foi melhor que os demais tanto no tempo computacional e no número de nós explorados como também no número de problemas não resolvidos e no desvio relativo médio do makespan. Foi realizado uma comparação entre o melhor modelo MILP e o melhor limitante inferior para o Branch-and-Bound, sendo que o último obteve melhores resultados para os problemas testados. Entre os métodos heurísticos adaptados, o PF foi o que obteve, de uma forma geral, os melhores resultados em todas as fases. / Production scheduling is defined as a problem of allocating jobs in machines in a production environment and it has been largely studied. The scheduling can vary in difficulty and complexity depending on the environment, the variety and types of technological restraints and the objective function of the problem. The use of decision making methods to solve scheduling problems in the industry needs models that are capable to solve real problems, that usually involve a big variety of restraints that have to be simultaneously studied. At the present work the scheduling problem in a permutational flow shop environment, considering blocking with zero buffer, and sequence and machine dependent setup times, with the objective of minimizing makespan is studied, which is considered a NP-Complete problem and little explored in literature. The work presents a calculation procedure for the makespan and three solution methods for the problem: four lower bounds for the Branch-and-Bound procedure; four MILP models, two of which are adapted; and 28 constructive heuristic methods adapted to the problem. The methods developed are based on mathematical properties of the problem that are presented in this work as a lower bound and an upper bound. Among all the MILP models, the adapted model RBZBS1 was the one to obtain the best results for the smaller problems, and the developed model TNZBS1 obtained the smallest mean relative deviation of the makespan for the bigger problems that were not solved within the specified computational time limit. The lower bound for the Branch-and-Bound LBTN2 obtained smaller computational times and number of explored nodes as well as the number of unsolved problems and the mean relative deviation for the makespan than all other lower bounds. Also, a comparison among the best MILP model and the best lower bound for the Branch-and-Bound was performed, being that the last obtained better results for the tested problems. Among the adapted heuristic methods, the PF heuristic was the one that obtained, in general, the better results in all phases.

Made available in DSpace on 2016-06-02T19:50:20Z (GMT). No. of bitstreams: 1 5182.pdf: 6075915 bytes, checksum: 91596b4ab6b9108e05799c5f3c87831d (MD5) Previous issue date: 2013-05-17 / Financiadora de Estudos e Projetos / The object of this study are combined problems of the Vehicle Routing Problem and the Container Loading Problem, recently addressed as Integrated Vehicle Routing and Loading Problems. In these problems, the objective is to optimize simultaneously the planning of the vehicles routes and the arrangement of the cargo inside them, while considering a series of practical constraints from both vehicle routing and container loading. The objectives of this study are: (i) to study the integration between the Vehicle Routing Problem and the Container Loading Problem; (ii) to develop mathematical programming models to represent Integrated Vehicle Routing and Loading Problems; (iii) to develop and implement heuristics and metaheuristics to solve some of these problems; (iv) to analyze and compare the performance of the proposed models, by means of modeling languages and optimization solvers, as well as the heuristic methods, when solving instances from the literature and real-world situations. Besides being hard and relatively less studied problems, the main reason for this study is that with effective solution methods for optimizing the vehicle routing and the cargo loading, operational and tactical decisions could be made with more reliability, accuracy, quickness and with less uncertainty in real situations, besides of an improved use of the staff tasked to load and unload the cargo. On the other hand, these methods can also be usefull to reduce fixed and variable costs in a company that might use them. Computational experiments with some of the proposed models were performed with an optimization software and randomly generated instances. The results show that the models are consistent and properly represent the practical situations treated, although this approach (in its current version) is limited to solve to optimality only problems of moderate size, that is, situations with few customers, few vehicles, and mainly with a relatively reduced number of possible positions to load the boxes. This has motivated the development of heuristic and metaheuristic methods to solve more realistic vehicle routing and loading problems. The algorithms are based on the combination of classical heuristics from both the vehicle routing and container loading literatures, as well as two metaheuristic strategies, and their use in more elaborate procedures. Although these approaches cannot assure optimal solutions for the respective problems, they are relatively simple, fast enough to solve real instances, flexible enough to include practical considerations, and normally assure relatively good solutions in acceptable computational times in practice. Computational experiments were performed with these methods considering instances based on the vehicle routing literature and actual customers orders, as well as instances based on a real-world situation where the problem occurs. / O objeto de estudo deste trabalho são problemas combinados do Problema de Roteamento de Veículos com o Problema de Carregamento de Contêineres, tratados mais recentemente na literatura como Problemas Integrados de Roteamento e Carregamento de Veículos. Nestes problemas, genericamente, busca-se otimizar simultaneamente o planejamento dos roteiros dos veículos e o arranjo da carga dentro dos mesmos, respeitando-se uma série de considerações práticas que advêm tanto do Problema de Roteamento de Veículos como do Problema de Carregamento de Contêineres. Os objetivos deste trabalho são: (i) estudar a integração do Problema de Roteamento de Veículos com o Problema de Carregamento de Contêineres; (ii) desenvolver modelos de programação matemática para representar Problemas Integrados de Roteamento e Carregamento de Veículos; (iii) desenvolver e implementar métodos heurísticos e meta-heurísticos para resolver alguns destes problemas; (iv) analisar e comparar o desempenho da solução dos modelos, via linguagens de modelagem e aplicativos de otimização, e dos métodos heurísticos desenvolvidos ao resolver exemplos baseados na literatura e em situações reais em que este problema ocorre. Além de serem problemas difíceis e relativamente pouco estudados, a principal justificativa para o estudo destes problemas é que, com métodos de solução eficazes para a otimização do roteamento dos veículos e do carregamento das cargas, decisões operacionais e táticas podem ser tomadas com maior segurança, acurácia, rapidez e menor incerteza em situações reais, além de possibilitar um melhor desempenho do pessoal encarregado da montagem e descarregamento da carga. Por outro lado, estes métodos também podem ser úteis na redução de custos fixos e variáveis de uma empresa que venha a utilizá-los. Experimentos computacionais com alguns dos modelos propostos foram realizados utilizando um aplicativo de otimização e aplicados a exemplos gerados aleatoriamente. Estes resultados mostram que os modelos são coerentes e representam adequadamente as situações tratadas, embora esta abordagem (na sua versão atual) esteja limitada a resolver otimamente apenas problemas de tamanho bem moderado, isto é, em que haja poucos clientes, poucos veículos, e que o número de possíveis posições para se arranjar as caixas dentro de cada veículo seja relativamente pequeno. Isso motivou o desenvolvimento de métodos heurísticos e meta-heurísticos para resolver problemas mais realistas de roteamento e carregamento de veículos. Os algoritmos são baseados na combinação de heurísticas clássicas das literaturas de Roteamento de Veículos e de Carregamento de Contêineres, bem como em duas estratégias meta-heurísticas, e no uso delas em procedimentos mais elaborados. Embora não haja garantias de que as soluções obtidas para os respectivos problemas sejam ótimas, tratam-se de heurísticas relativamente simples, suficientemente rápidas para resolver problemas reais, razoavelmente flexíveis para incorporar aspectos práticos, e que normalmente garantem soluções relativamente boas em tempos computacionais aceitáveis na prática. Experimentos computacionais foram realizados com estes métodos considerando exemplos baseados na literatura de Roteamento de Veículos e em pedidos reais de cargas, bem como exemplos baseados em um caso real em que o problema ocorre.