[pt] A principal contribuição desta tese consiste no desenvolvimento de uma heurística híbrida, robusta e eficiente, para o problema de empacotamento unidimensional. A heurística proposta utiliza os seguintes componentes: limites inferiores e superiores do número de caixas; reduções; abordagem dual para a obtenção de soluções iniciais; heurísticas para redistribuição dos pesos; e busca tabu. O outro objetivo desta tese é a aplicação desta heurística para a solução do problema de escalonamento em processadores paralelos idênticos. São apresentados resultados computacionais obtidos sobre centenas de problemas testes da literatura. / [en] We propose in this work a hybrid improvement procedure for the bin packing problem. This heuristic has several components: lower and upper bounds; reductions, construction of initial solutions by reference to the dual problem;heuristics for load redistribution based on dominance, differencing, and unbalancing; and tabu search. We also investigate the application of this hybrid heuristic to the problem of task scheduling on identical parallel processors. Computational results on hundreds of benchmark test problem are presented.

[pt] O desenvolvimento de metaheurísticas paralelas autonômicas para serem executadas eficientemente em ambientes de grid é o objetivo desta tese. A aplicação paralela deve ser capaz de se auto-adaptar às mudanças que ocorrem dinamicamente no ambiente, sem que o usuário precise interferir diretamente no código da mesma. Para isso, a metaheurística autonômica deve ser vista como uma aplicação com dois níveis independentes: middleware e estratégia. O middleware é responsável por gerenciar todo o ambiente de execução, de acordo com as características da aplicação. A estratégia hierárquica distribuída permite a cooperação entre todos os processos envolvidos, sem degradar o desempenho da aplicação devido ao aumento da comunicação entre processos. Para validar esta proposta foram desenvolvidas duas implementações paralelas de metaheurísticas, uma para o problema do torneio com viagens espelhado e a outra para o problema da árvore geradora de custo mínimo com restrição de diâmetro. Para ambos os problemas, as implementações desenvolvidas foram testadas no ambiente grid Sinergia, formado por máquinas localizadas em três diferentes cidades do Estado do Rio de Janeiro. As parelizações foram capazes de melhorar, para várias instâncias, os melhores resultados conhecidos na literatura. / [en] The development of autonomic parallel metaheuristics to be efficiently executed in computational grid is the challenge of this thesis. The parallel application must be able to self-adjust to the changes that occur dynamically in the environment, without the user needing to interfere directly in the code of the application. For this, the autonomic metaheuristic should be seen as an application on two independent levels: middleware and strategy. The middleware is responsible for managing the entire execution environment, according to the characteristics of the application. The distributed hierarchical strategy enables the cooperation between all processes involved, without degrading the performance of the application due to increased communication between processes. To validate this proposal, two parallel implementations of metaheuristics were developed, one for the mirrored traveling tournament problem and the other for the diameter constrained minimum spanning tree problem. For both problems, the developed implementations were tested in the grid Synergy environment, formed by machines located in three different cities in the state of Rio de Janeiro. The paralelizations improved, for several instances, the best known results in the literature.

[pt] Problemas de Programação de Horários (PPHs) tem sido amplamente estudados, dada a sua importância prática e teórica. A maioria das variações do problema pertence µa classe NP-Difícil. Em geral, trata-se da alocação de recursos materiais e humanos no espaço e no tempo, visando a otimização de um conjunto de objetivos definidos. Na Programação de Horários de Cursos Universitários, por exemplo, o objetivo pode ser a satisfação do corpo docente e o desempenho acadêmico dos alunos. Nos últimos anos, as formulações de PPHs propostas pela International Timetabling Competition (ITC) tem sido bastante utilizadas, sendo notável a predominância de métodos baseados em busca local e metaeurísticas entre as abordagens propostas recentemente. Este trabalho tem como objetivo propor algoritmos para o Problema de Programação de Horários Pós-Matrícula da ITC, focando principalmente em métodos heurísticos baseados em Programação Matemática. Entre os modelos de Programação Linear Inteira Mista que propomos para este problema, destaca-se o modelo baseado na Formulação de Representantes Assimétricos para o Problema de Coloração de Grafos. Abordamos a aplicação da heurística de Local Branching e propomos um esquema de resolução por Geração de Colunas, como forma de viabilizar o tratamento dos modelos propostos, uma vez que a complexidade de tais modelos representa um desafio para os resolvedores de Programação Linear Inteira Mista atualmente disponíveis. / [en] Timetabling Problems have been widely studied, given its practical and theorical relevance. Most of its variations belong to the NP-Hard class of problems. In general, it is about allocation of material and human resources in time and space, aiming to optimize some set of defined objetives. In University Course Timetabling, for example, the objective might be the satisfaction of professors and the academic performance of students. In the last years, the formulations for timetabling problems proposed by the In- ternational Timetabling Competition (ITC) have been widely adopted. The predominance of meta-heuristics and local search-based methods is remark- able among the recently proposed approaches. The objetive of this thesis is to propose algorithms for the Post Enrolment-based Course Timetabling Problem of the ITC, focusing on Mathematical Programming-based heuris- tic methods. Among the Mixed Integer Linear Programming models that we propose for this problem, we highlight the one based on the Asymetric Representatives Formulation for the Graph Coloring Problem. We explore the application of the Local Branching heuristic and we propose a Column Generation solution procedure, as an attempt to handle the proposed models, given that the complexity of such models poses a challenge for currently available Mixed Integer Linear Programming solvers.

[pt] A otimização em esportes é uma área que reúne diversas aplicações relacionadas ao planejamento e gestão de atividades esportivas. Diversas técnicas de otimização combinatória têm sido aplicadas, por exemplo, à  construção de tabelas de torneios e à  análise do desempenho de equipes em competições. Um problema que surge no contexto da organização de competições esportivas consiste na determinação de quais árbitros atuarão em cada partida de um determinado torneio. Diversas regras devem ser observadas no processo de atribuição de árbitros, que em geral envolve também a consideração de vários objetivos. Esta tese tem como objetivo principal apresentar um estudo sobre um problema de atribuição de árbitros, comum a várias ligas esportivas amadoras. Demonstra-se que a versão de decisão do problema estudado é um problema NP-completo. Considera-se inicialmente duas variantes mono-objetivo do PAA, que diferem uma da outra pela função objetivo adotada. Propõe-se modelos de programação linear inteira que permitem uma abordagem exata para a resolução de instâncias de pequeno e médio portes. Com o intuito de tratar instâncias de tamanho real, propõe-se também abordagens aproximadas de resolução baseadas na metaheurí­stica Iterated Local Search (ILS). Uma vez que o PAA tem origem em aplicações reais, ligadas a processos de tomada de decisões, é natural que envolva a consideração de diversos objetivos, muitas vezes em conflito. Tal fato motivou a investigação do uso de técnicas de otimização multi-critério que possam ser utilizadas na construção de um sistema de suporte a decisão e aplicadas a uma variante bi-objetivo do PAA, que considera simultaneamente as duas funções objetivo utilizadas nas variantes mono-objetivo estudadas. Abordagens de resolução exata e aproximada para esta variante bi-objetivo são propostas e seus resultados discutidos. / [en] Optimization in sports is a field of increasing interest. Combinatorial optimization techniques have been applied e.g. to game scheduling and playoff elimination. A problem that arises in competition management is the assignment of referees to games already scheduled. There are a number of rules and objectives that should be taken into account when referees are assigned to games. We address two mono-objective versions of a Referee Assignment Problem (RAP) common to many amateur leagues of sports such as soccer, baseball, and basketball. The problem is formulated by integer programming and its decision version is proved to be NP-complete. To tackle real-life large instances of the RAP, we propose a three-phase heuristic approach based on a constructive procedure, a repair heuristic to make solutions feasible, and a local search heuristic to improve feasible solutions, based on the metaheuristic iterated local search. Numerical results on realistic instances are presented and discussed. This work also investigates the solution of a bi-objective version of the RAP, which combines both objective functions used in the mono-objective versions. Exact and heuristic approaches are proposed to solve this bi-objective version and its computational results are discussed.

[pt] O problema de Districting-and-routing é um problema estratégico no qual porções geográficas devem ser agregadas em regiões de entrega, e cada região de entrega possui um custo de roteamento estimado. Seu objetivo é de minimizar esses custos, além de garantir a divisão da região em distritos. A simulação para obter uma boa aproximação é muito custosa computacionalmente, enquanto mecanismos como buscas locais exigem que esse cálculo seja feito de forma muito eficiente, tornando essa estratégia de aproximação inviável para uma solução metaheurística. Grande parte das soluções existentes para esse problema utilizam de formulas de aproximação contínua para mensurar os custos de roteamento, funções essas que são rápidas de serem calculadas porém cometem erros significativos. Em contraste, propomos uma Rede Neural em Grafo (Graph Neural Network - GNN) que é usada como oráculo por um algoritmo de otimização. Nossos experimentos computacionais executados com dados de cidades do Reino Unido mostram que a GNN é capaz de produzir previsões de custos mais precisas em tempo computacional aceitável. O uso desse estimator na busca local impacta positivamente a qualidade das soluções, levando a uma economia de 10,35 por cento no custo de entrega estimado em relação a função Beardwood, que é comumente usada nesse cenários, e ganhos similares em comparação com outros métodos de aproximação. / [en] The districting-and-routing problem is a strategic problem in which basic geographical units (e.g., zip codes) should be aggregated into delivery regions, and each delivery region is characterized by a routing cost estimated over an extended planning horizon. The objective is to minimize the expected routing costs while ensuring regional separability through the definition of the districts. Repeatedly simulating routing costs on a set of scenarios while searching for good districts can be computationally intensive, so existing solution approaches for this problem rely on approximation functions. In contrast, we propose to rely on a graph neural network (GNN) trained on a set of demand scenarios, which is then used within an optimization approach to infer routing costs while solving the districting problem. Our computational experiments on various metropolitan areas show that the GNN produces accurate cost predictions. Moreover, using this better estimator during the search positively impacts the quality of the districting solutions and leads to 10.35 percent delivery-cost savings over the commonly-used Beardwood estimator and similar gains compared to other approximation methods.

[pt] Seja G= (V, E) um grafo não-orientado com custos não- negativos em suas arestas e D um conjunto de pares origem - destino. Um 2-caminho entre nós (s,t)é um caminho de s a t formado por , no máximo, 2 arestas. O problema de síntese de redes com 2-caminhos (2PNDP) consiste em encontrar um subconjunto de arestas com custo mínimo que contenha um 2- caminho entre as extremidades dea cada para origem- destino pertencente a D. Apicações deste problema encontram-se no projeto de redes de comunicação, onde caminhos com poucas arestas são desejáveis para garantir alta confiabilidade e pequenos atrasos. A metaheurística GRASP é um processo multipartida para resolver problemas combinatórios, cujas iterações consistem de duas fases, uma fase de construção e outra de busca local. O algoritmo retorna a melhor solução encontrada depois de um número determinado de iterações.Aplica-se a técnica de reconexão por caminhos ao final de cada iteração GRASP para melhorar a qualidade das soluções. Implementações paralelas de metaheurística são muito robustas. A maior parte das implementações paralelas da metaheurística GRASP segue uma estratégia do tipo independente , baseada na distribuição balanceada das iterações pelos processadores. No caso de estratégias colaboradtivas, os processadores trocam e compartilham informações coletadas ao longo da trajetória que cada um deles investiga. Neta tese são desenvolvidas heurísticas seqüenciais e paralelas para 2PNDP. São analisadas variantes e combinações de GRASP e reconexão por caminhos , comparando-se os resultados obtidos pelos algoritmos descritos na literatura. Heurísticas GRASP paralelas com reconexão por caminhos são avaliadas e comparadas para verificar qual o papel que a colaboração entre os processadores desempenha na qualidade das soluções e nos tempos de processamento. Procura-se também estudar a melhor maneira de desenvolver implementações paralelas , para se utilizar da melhor forma possível os recursos computacionais e reduzir conflitos de memória e comunicação. / [en] Let G = ( V, E) be a connected undirected graph , where V is the set of nodes and E denotes the set of edges. A 2- path between nodes (s,t)is a sequence of a most two edges connecting them. Given a non-negative weight function associated with edges of G and a set D of origin- destination pairs of nodes, the 2-path network design problem (2PNDP) consists in finding a minimum weighted subset of edges containing a 2-path between the extremities of every origin-destination pair in D. Applications can be found in the design of communication networks , in which paths with few edges are sought to enforce high reliability and small delays. The GRASP metaheuristic is a multistart process , in which each iteration consists of two phases : construction and local search. The best solution found after a fixed number of iterations is returned. Path- relinking is applied as an attempt to improve the solutions found at the of each GRASP iteration. Parallel implementations of metaheuistics ara very robust. Typical parallelizations of GRASP correspond to multiple-walk independent-thread strategies, based on the balanced distribuiton of the iterations over the processors. In the case of multiple-walk cooperative-thread strategies, the processors exchange and share information collected along the trajectories that they investigate. In this thesis, sequential and parallel heuristics are developed for 2PNDP. Variants and combinations of GRASP with path-relinking are analysed by comparing the results of the proposed algorithms with those obtained by others algoritms described in the literature. Parallel GRASP with pathrelinking heuristcs are compared to investigate the influence of the cooperation among processors in terms of solution quality and processing time. We also explore different strategies to optimize the parallel implementations, to make better use of the computational resources and to reduce communication and memory conflicts.

[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] O problema de sequenciamento de tarefas e troca de ferramentas (job sequencing and tool switching problem - SSP) tem sido extensivamente estudado na área de pesquisa operacional, devido à sua relevância prática e interesse metodológico. Dada uma máquina que pode carregar uma quantidade limitada de ferramentas simultaneamente e um número de tarefas que requerem um subconjunto das ferramentas disponíveis, o SSP procura uma sequência de tarefas que minimize o número total de trocas de ferramentas na máquina. Para resolver este problema, é proposta uma busca genética híbrida simples e efetiva baseada em uma representação de solução genérica, um operador de decodificação sob medida, buscas locais eficientes e técnicas de gerenciamento de diversidade. Para orientar a busca, um objetivo secundário desenvolvido para tratar empates é introduzido. Essas técnicas permitem explorar soluções estruturalmente distintas e escapar de ótimos locais. Conforme apresentado nos experimentos computacionais em instâncias clássicas, o algoritmo proposto supera significativamente todas as abordagens anteriores, mesmo sendo de fácil entendimento e implementação. Por fim, resultados obtidos em um novo conjunto de instâncias maiores são reportados para estimular futuras pesquisas e análises comparativas. / [en] The job sequencing and tool switching problem (SSP) has been extensively studied in the field of operations research, due to its practical relevance and methodological interest. Given a machine that can load a limited amount of tools simultaneously and a number of jobs that require a subset of the available tools, the SSP seeks a job sequence that minimizes the number of tool switches in the machine. To solve this problem, we propose a simple and efficient hybrid genetic search based on a generic solution representation, a tailored decoding operator, efficient local searches and diversity management techniques. To guide the search, we introduce a secondary objective designed to break ties. These techniques allow to explore structurally different solutions and escape local optima. As shown in our computational experiments on classical benchmark instances, our algorithm significantly outperforms all previous approaches while remaining simple to apprehend and easy to implement. We finally report results on a new set of larger instances to stimulate future research and comparative analyses.

[pt] Empresas de exploração de petróleo e gás offshore frequentemente precisam lidar com problemas relacionados ao uso eficiente de seus recursos. Neste trabalho, abordamos um problema de programação de navios associado à logística offshore de petróleo e gás – O Problema de Programação de Embarcações do tipo Pipe-Laying support Vessel (PLSVSP). Essas embarcações são especialmente projetadas para realizar conexões de dutos entre poços de petróleo submarinos e plataformas de produção. A conexão de dutos é a última etapa a ser executada para permitir a drenagem do óleo e iniciar a produção em um poço. No PLSVSP, o objetivo é antecipar a conclusão de poços mais produtivos. O problema pode ser visto como uma variante de um problema de programação de lotes com máquinas paralelas idênticas e tempos de configuração não antecipados por família para minimizar o total weighted completion time. Nessa analogia, embarcações são as máquinas, poços são as tarefas e lotes são as viagens executadas por PLSVs, definindo quais poços devem ser conectados a cada saída do porto. Foram desenvolvidas diversas abordagens de otimização para resolver as variantes determinística e estocástica do problema. Para a variante determinística, desenvolvemos métodos híbridos e uma metaheurística capazes de melhorar as soluções desenvolvidas por formulações MIP puras e lidar com o PLSVSP. Para a variante estocástica, foi desenvolvida uma simheurística utilizando simulação de Monte Carlo incorporada, considerando incertezas nas durações das conexões e nas datas de chegada dos oleodutos no porto. Os resultados mostram uma melhora significativa no custo das soluções quando lidam com incertezas em comparação com soluções geradas por um método determinístico. O uso da simulação em uma estrutura metaheurística mostrou-se uma abordagem promissora, capaz de lidar com o problema estocástico, com pouco esforço computacional extra necessário. / [en] Offshore oil and gas exploration companies frequently need to deal with problems related to the efficient use of their resources. In this work, we address a ship scheduling problem associated with offshore oil and gas logistics – The Pipe Laying Support Vessel Scheduling Problem (PLSVSP). These vessels are specially designed to perform pipeline connections between sub-sea oil wells and production platforms. The connections are the last step to be performed to allow the oil draining, starting production in a well. The PLSVSP objective is to anticipate the completion of the most productive wells. The problem can be seen as a variant of a batch scheduling problem with identical parallel machines and non-anticipatory family setup times to minimize the total weighted completion time. In this analogy, vessels are machines, wells are jobs, and batches are voyages executed by PLSVs, defining which wells to connect each time it leaves the port. We developed several optimization approaches to solve the deterministic and stochastic variants of the problem. For the deterministic problem, we developed hybrid methods and a metaheuristic that outperformed the pure MIP formulations, being practical to deal with the PLSVSP. A simheuristic using embedded Monte Carlo simulation was developed for the stochastic variant of the problem, considering uncertainties in the connection duration and the arrival dates of pipelines at the port. The results show a significant improvement in the solutions dealing with uncertainties compared to solutions generated by a deterministic method. The use of simulation within a metaheuristic framework proved to be a promising approach, being able to deal with the stochastic problem, with little extra computational effort required.

[pt] GRASP (Greedy Randomized Adaptive Search Procedure)é uma metaeurística de partidas múltiplas usada para obter soluções para problemas de otimização combinatória. Nesse trabalho. A metaheurística GRASP tem sido usada para obter soluções de qualidade para muitos problemas de otimização combinatória. Nesse trabalho é proposta uma metodologia para análise do comportamento da metaheurística GRASP. Também são propostas estratégias de hibridização com o religamento de caminhos. Essas estratégias foram desenvolvidas para o problema de atribuição de três índices (AP3) e para o problema de escalonamento de tarefas conhecido na literatura como job-shop schedulling problem (JSP) e são analisadas de acordo com a metodologia proposta. A metodologia para análise do comportamento do método GRASP pode ser usada para prever a partir da versão seqüencial do algoritmo, como a qualidade da solução do algoritmo implementado em paralelo irá variar. Os algoritmos GRASPs desenvolvidos para AP3 e para JSP foram paralelizados e os resultados são comparados aos resultados obtidos usando a metodologia proposta. / [en] GRASP (Greedy Randomized Adaptive Search Procedure) is a multi-start metaheuristic for combinatorial optimization problems. GRASP has been used to find quality solutions of several combinatorial optimization problems. In this work we describe a methodology for analysis of GRASP. Hybrid strategies of GRASP with path relinking are also proposed. These strategies are studied for the 3-index assignment problem (AP3) and for the job-shop schedulling problem (JSP) and are analyzed according to the methodology proposed. The methodology for analysis of GRASP is used to predict qualitatively how the quality of the solution varies in a parallel independent GRASP, using the data of the GRASP sequential version as input. The GRASPs for the AP3 and for the JSP are parallelized and the computational results are compared to the results obtained using the methodology proposed.