[pt] A exploração e produção de petróleo do Pré-sal ocorre em regiões de águas ultra profundas, com condições complexas de instalação e operação de equipamentos. A interligação dos poços, última etapa que antecede o início da operação de produção, é realizada por embarcações de alto custo, especialmente equipadas para este fim, conhecidas como PLSVs (Pipe Laying Support Vessels). Esta dissertação visa o desenvolvimento de um modelo de programação matemática capaz de alocar e sequenciar as atividades de interligação de poços submarinos em embarcações PLSV, de forma a maximizar a produção de óleo acumulada durante o horizonte de planejamento. Para tanto, foi utilizado como base um problema real enfrentado pela Petrobras, que permitiu estender a abordagem clássica baseada em máquinas paralelas, com a adição de novas restrições. Para tornar a otimização viável, foi criado um método de resolução que utiliza o conceito de blocos de atividades. Visando reduzir a complexidade de resolução, foram realizados testes utilizando apenas blocos compostos por atividades de poços próximos entre si. Tais estratégias se mostraram eficazes e o modelo foi capaz de gerar soluções de execução viável e de qualidade até 21,5 por cento superiores em produção de óleo quando comparadas à solução contruída pelos especialistas do problema. / [en] Pre-salt oil exploration and production occurs in ultra-deep water regions, with complex conditions of equipament installation and operation. The wells connections, last stage before the production phase, is carried out by high-cost vessels, specially equipped for this purpose, known as PLSVs (Pipe Laying Support Vessels). This dissertation aims to develop a mathematical programming model to assign and schedule a PLSV fleet, in order to maximize the oil production during the planning horizon. For this purpose, a real problem faced by Petrobras was used, which allowed to extend the classic parallel machine approach, adding new constraints to the problem. To make the optimization feasible, a resolution method was created using the activities blocks concept. In order to reduce the resolution complexity, tests were performed using blocks composed by activities of wells close to each other. These strategies were effective, generating solutions with quality up to 21.5 percent higher (in oil production) when compared to the solution built by the problem specialists.

[pt] Este trabalho tem como objetivo propor uma metaheurística Iterated Local Search para minimizar o tempo de término ponderado de jobs em problemas de escalonamento de máquinas idênticas paralelas. O objetivo secundário do trabalho é propor uma solução prática para um problema real da companhia estudada em questão. A motivação para o trabalho consiste em uma aplicação prática na indústria de óleo e gás, onde os navios PLSV realizam operações em poços de forma ordenada e visando a antecipação dos poços de petróleo mais produtivos. As características do problema, tais quais: elegibilidade entre navio e operações, tempos de setup relativos à família de atividades, associações entre operações e poços e setups que dependem da chegada de material se adequam a modelagem baseada em escalonamento de máquinas paralelas idênticas. No trabalho uma introdução à respeito do tema é apresentada, em seguida é feita uma revisão da literatura sobre problemas de máquinas paralelas idênticas, a formulação matemática com a descrição do problema é apresentada, a metodologia contemplando representação da solução, heuristica construtiva, vizinhanças exploradas, busca local e Iterated Local Search é exposta, por fim são apresentados os resultados do método e as conclusões sobre o trabalho. / [en] This work objective is to propose an Iterated Local Search metaheuristic to minimize the weighted completion time of jobs on identical parallel machines scheduling problems. The secondary objective of this work is to propose a practical solution to the real problem of the studied company. The motivation of this work consists on a practical application in the Oil and Gas industry, where the PLSV vessels perform ordered operations in a set of wells aiming to maximize the oil production. The characteristics of the problem such as: eligibility between vessels and operations, setup times related to the family of activities, association between operations and wells and setup times depending on the material arrival fit well the identical parallel machine schedule modelling. In this work, an introduction about the theme is presented, followed by a literature review on identical parallel machine scheduling problems, the mathematical formulation with the problem description is presented, the methodology, including the solution representation, constructive heuristic, neighborhood structures, local search and Iterated Local Search is exposed, at last, the method results and conclusions of the work are summarized.

[pt] A dissertação aborda um problema real de reprogramação de uma frota de embarcações do tipo PLSV (Pipe Laying Support Vessel), responsáveis pelas interligações de poços petrolíferos submarinos. O cronograma de curto prazo dessas embarcações está sujeito à inúmeras incertezas inerentes às operações realizadas, acarretando em ociosidade nas embarcações ou postergações na produção de petróleo, que podem resultar em prejuízo de milhões de reais. Uma metaheurística ILS (Iterated Local Search) é proposta para atender a frequente demanda por reprogramações dos PLSVs. O método é composto de uma fase inicial de viabilização, para tratar potenciais inconsistências nas programações. Na sequência, iterativamente, são realizadas perturbações na solução por meio de movimentos de swap e aplicada uma busca local baseada na vizinhança insert, a fim de fugir de ótimos locais e encontrar soluções que aprimorem o cronograma. Foram feitos experimentos com diferentes parâmetros e critérios do ILS, sendo definidas duas abordagens aplicadas a dez instâncias oriundas de uma programação real de PLSVs. A partir de uma função de avaliação, capaz de medir o impacto operacional na programação, o ILS proporcionou uma melhoria média nos cronogramas acima de 91 por cento, quando comparados aos cronogramas originais. As soluções foram obtidas em um tempo computacional médio de 30 minutos, aderente ao processo da companhia. Em função dos resultados alcançados, o método provou ser uma boa base para uma ferramenta de apoio à decisão para a reprogramação dos PLSVs. / [en] This dissertation addresses a real-life rescheduling problem of a Pipe Laying Support Vessels (PLSVs) fleet, in charge of subsea oil wells interconnections. The short-term schedule of these vessels is subject to uncertainties inherent to its operations, resulting in ships idleness or delays in oil production, which may lead to losses of millions of Brazilian Reais. A method based on the ILS (Iterated Local Search) metaheuristic is proposed to meet the frequent demand of PLSVs rescheduling. The first step of this method aims to find a feasible initial solution from an incoming schedule with potencial inconsistencies. The following steps consists in, iteratively, performing a perturbation on a solution through swap movements and applying a local search based on the insertion neighborhood, in order to escape from local optimal and find better solutions. Extensive preliminary experiments were conducted considering different ILS parameters setups. The two most performing setups were selected and applied to ten instances of a real PLSV schedule. Taking into account an objective function that measures the operational impact on schedules, the ILS provided an average improvement above 91 percent in schedules when compared to the original planning. These solutions were obtained in an average computational time of 30 minutes, which fits in the company process. The obtained results showed that the proposed method might be a basis for a decision support tool for the PLSVs rescheduling problem.