Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro Tecnológico. Programa de Pós-Graduação em Ciência da Computação. / Made available in DSpace on 2013-07-16T01:31:20Z (GMT). No. of bitstreams: 1 223154.pdf: 452480 bytes, checksum: 32034bdd69509f5e45a87f49f8215540 (MD5) / A busca por soluções de problemas envolvendo otimização combinatorial tem sido motivo de estudos e pesquisas há muito tempo. Grande parte dos métodos propostos para a resolução de problemas desse tipo, que buscam soluções ótimas, está baseada em técnicas conhecidas como branch-and-bounds. Entretanto, o principal problema desse tipo de abordagem consiste no esforço computacional exigido. O tempo de computação necessário para a determinação de uma solução pode atingir níveis impraticáveis, tornando-os muitas vezes inviáveis em aplicações práticas. Como alternativa, atualmente, diversos métodos de aproximação estão sendo propostos. São abordagens que buscam soluções aceitáveis, próximas às soluções ótimas, porém, com tempos de processamento viáveis. Como exemplos típicos dessa abordagem podem ser citados os algoritmos das Formigas, Genéticos, Simulated Anneling, etc. Nesta dissertação é apresentado um novo algoritmo de aproximação que poderá ser empregado em problemas dessa natureza. Basicamente, o que está sendo proposto é a utilização do algoritmo Simulated Annealing em sua forma original, combinado com os operadores crossovers dos Algoritmos Genéticos. Além da hibridização dos algoritmos aludidos, também é explorada neste trabalho a potencialidade da paralelização dos mesmos em um ambiente multiprocessado. Na implementação e nos testes do modelo proposto foi utilizado o clássico Problema do Caixeiro Viajante que é um dos representantes desta classe de problema de otimização combinatorial, mais utilizados como benchmark.

Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro Tecnológico. Programa de Pós-Graduação em Engenharia Elétrica. / Made available in DSpace on 2013-07-16T01:35:46Z (GMT). No. of bitstreams: 1 223414.pdf: 3157424 bytes, checksum: 9aa3342abef55c59abdda0259106f8e7 (MD5)

Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro Tecnológico. Programa de Pós-Graduação em Engenharia Mecânica / Made available in DSpace on 2012-10-26T08:18:36Z (GMT). No. of bitstreams: 1 300010.pdf: 1213613 bytes, checksum: fd89006e1d3f2117ffd5b86d1fd46fed (MD5) / Este trabalho apresenta uma abordagem sobre otimização topológica estrutural. Neste estudo, formula-se o problema de minimização de massa com restrição de falha material local baseada em níveis de tensão. Esta restrição é imposta utilizando uma abordagem baseada na técnica Lagrangeano Aumentado, onde as restrições são incorporadas à função objetivo através de uma sequência de problemas de penalização. A sequência de atualização dos parâmetros de Lagrange conduz, na convergência, à satisfação das condições de Karush-Kuhn-Tucker (KKT) do problema original. Para o controle da topologia utiliza-se o método level set, cuja fronteira é implicitamente representada pelas curvas de níveis de uma função escalar, conhecida como função level set. A sequência minimizante é obtida atualizando a fronteira segundo uma direção de gradiente da função objetivo. Esta direção é obtida mediante análise de sensibilidade à mudança de forma, fornecendo um campo de velocidade que permite a atualização da fronteira através da solução do problema de Hamilton-Jacobi, definida sobre um domínio de referência fixo. Vários exemplos numéricos são apresentados a fim de verificar o comportamento da metodologia proposta, incluindo exemplos nos quais as soluções analíticas são conhecidas a priori / This work presents an approach to structural topology optimization. In this study the problem of mass minimization is formulated under local material failure constraint based on stress levels. This constraint is imposed using an approach based on Augmented Lagrangian technique in such a way that the constraints are incorporated into the objective function by penalization. The convergence of the updating sequence of the Lagrange parameters corresponds to the satisfaction of the Karush-Kuhn-Tucker conditions of the original problem. The level set method is used to control the domain topology whose boundary is represented implicitly by level curves of a higher dimensional scalar function. The minimizing sequence is achieved by updating the body boundary using a gradient direction of the objective function. This is obtained through shape sensitivity analysis, providing a velocity field that updates the boundary by the solution of the Hamilton-Jacobi partial differential equation embedded in a fixed domain. Some numerical examples are shown in order to verify the behavior of the proposed technique, including examples in which the analytical solution is known a priori

GOMES, R. F. de S. Aplicação da metaheurística tabu search na otimização de rotas de manutenção preventiva em campo. 2011. 108 f. Dissertação (Mestrado em Logística e Pesquisa Operacional) - Pró-Reitoria de Pesquisa e Pós-Graduação, Universidade Federal do Ceará, Fortaleza, 2011. / Submitted by Marlene Sousa (mmarlene@ufc.br) on 2012-10-26T14:32:46Z No. of bitstreams: 1 2011_dis_rfdesgomes.pdf: 1695034 bytes, checksum: cf3b9a4b04cd64169ae948a6d6884458 (MD5) / Approved for entry into archive by Marlene Sousa(mmarlene@ufc.br) on 2012-10-26T17:04:37Z (GMT) No. of bitstreams: 1 2011_dis_rfdesgomes.pdf: 1695034 bytes, checksum: cf3b9a4b04cd64169ae948a6d6884458 (MD5) / Made available in DSpace on 2012-10-26T17:04:37Z (GMT). No. of bitstreams: 1 2011_dis_rfdesgomes.pdf: 1695034 bytes, checksum: cf3b9a4b04cd64169ae948a6d6884458 (MD5) Previous issue date: 2011-12-09 / The aim of this paper was to propose an application based on the Metaheuristic Tabu Search (TS) to be used on FIELD PREVENTIVE MAINTENANCE SERVICES (FPMS) in order to get more logistics efficiency by routing maintenance sectors. Unlike services performed in industry, where all systems, machines and equipment are located practically in the same location, maintenance services in the field require an additional component directly related to cost, which refers to exactly offset between the base unit and jobsite. Services in the field can be considered a variation of the Travelling Salesman Problem (TSP) and its different approaches, like the DTRP (Dynamic Travelling Repairman Problem) proposed by Bertsimas and Van Ryzin. There is a huge demand for maintenance in the field, demonstrating its relevance: elevators, escalators, electronic devices for home-security, IT hardware support and others. The method was designed, implemented and tested in problems of the TSP-LIBRARY ranging from 17 up to 280 points. Good solutions were found in a acceptable processing time. The input data can be made by geographical coordinates or 2D-coordinates. For a real-world application, it was considered an Elevator Company and the results were also efficient, greatly reducing transportation cost and logistics used in the operation. / O objetivo deste trabalho foi propor uma aplicação baseada na metaheurística Busca Tabu (TS) para ser utilizada em serviços de manutenção preventiva em campo (FPMS) a fim de obter maior eficiência logística, através do roteamento de setores de manutenção. Ao contrário dos serviços realizados na indústria, onde todos os sistemas, máquinas e equipamentos estão localizados praticamente no mesmo local, serviços de manutenção em campo requerem um componente adicional diretamente relacionado ao custo, que se refere exatamente a diferença entre a unidade de base e local de trabalho. Serviços em campo podem ser considerados uma variação do Problema do Caixeiro Viajante (PCV) e suas diferentes abordagens, como o Problema Dinâmico do Reparador Viajante (DTRP - Dynamic Travelling Repairman Problem) proposto por Bertsimas e Van Ryzin. Em situações práticas do dia-a-dia existe uma enorme demanda por serviços de manutenção a serem realizados em campo, demonstrando sua relevância: elevadores, escadas rolantes, aparelhos segurança eletrônica residencial, suporte de TI à hardwares, entre outros. O método foi implementado e testado em problemas da biblioteca TSP-LIBRARY variando de 17 a 280 pontos. Boas soluções foram encontradas em um tempo de processamento aceitável. O input do problema leva em consideração duas formas: coordenadas geográficas ou coordenadas cartesianas. Para uma aplicação prática do mundo real, foi considerada uma empresa de manutenção em elevadores e os resultados também foram eficientes, reduzindo bastante os custos de transporte e a logística empregada na operação.

Rodrigues, A. B. Alocação de recursos de rádio para sistemas sc-fdma baseado em relaxamento e programação linear. 2016. 73 f. Dissertação (Mestrado em Engenharia Elétrica e da Computação) - Campus de Sobral, Universidade Federal do Ceará, Sobral, 2016. / Submitted by Programa de Pós-Graduação Engenharia Elétrica e de Computação (secretaria_ppgeec@sobral.ufc.br) on 2017-03-06T21:14:14Z No. of bitstreams: 1 2016_dis_abrodrigues.pdf: 1200876 bytes, checksum: 65bf4b1452b81c2dd6e5c26b0ab5bbc4 (MD5) / Approved for entry into archive by Ana Márcia Sousa (marciasousa@ufc.br) on 2017-03-07T11:23:43Z (GMT) No. of bitstreams: 1 2016_dis_abrodrigues.pdf: 1200876 bytes, checksum: 65bf4b1452b81c2dd6e5c26b0ab5bbc4 (MD5) / Made available in DSpace on 2017-03-07T11:23:43Z (GMT). No. of bitstreams: 1 2016_dis_abrodrigues.pdf: 1200876 bytes, checksum: 65bf4b1452b81c2dd6e5c26b0ab5bbc4 (MD5) Previous issue date: 2017-03 / In this work, we study the maximization problem of the sum of the weighted data rates in the wireless system’s uplink that uses SC-FDMA. The SC-FDMA multiple access scheme was adopted in the LTE uplink especially because it eases the power amplifier design in the mobile terminals. However, SC-FDMA presents an important restriction in radio resource allocation that is not present in OFDMA that was adopted in the LTE downlink: the resource adjacency or contiguity. With the resource adjacency constraint, the blocks of frequency resources assigned to each mobile terminal should be adjacent in the frequency domain. From the resource allocation point of view, this new constraint not only makes ineffective all previous resource allocation solutions proposed for OFDMA but also turns the problems even more harder in terms of computational complexity. In this work, we study the total data rate maximization problem in uplink SC-FDMA systems. Firstly, we discuss about the optimal solution of the problem that can be obtained through the use of integer optimization techniques. Motivated by the high computational complexity of this solution, we propose an alternative solution based on integer optimization relaxation and application of linear programming. The simulation results show that our proposed scheme is able to achieve the optimal solution in 55% (at least) of the simulations with a much lower computational complexity. For the cases where the solution obtained by continuous linear programming is not integer, the study proposes an algorithm that obtains an integer solution through rounding techniques. We also present a performance analysis comparing the algorithm developed with algorithms present in the literature. / Neste trabalho, estudamos o problema de maximização do somatório das taxas de dados ponderadas no enlace reverso de um sistema sem fio que emprega Single Carrier - Frequency Division Multiple Access (SC-FDMA). O esquema de múltiplo acesso SC-FDMA apresenta uma importante restrição quanto a alocação de recursos que não está presente em sistemas Orthogonal Frequency Division Multiple Access (OFDMA) (esquema utilizado no enlace direto de sistemas Long Term Evolution (LTE)): a contiguidade ou adjacência de blocos de recursos na frequência. A restrição de adjacência implica que a alocação dos blocos de recursos a cada terminal móvel deve ser feita de forma contígua na frequência. Na ótica de alocação de recursos em redes móveis, essa nova restrição não só inviabiliza o uso das soluções desenvolvidas para OFDMA encontradas na literatura, mas também torna o problema bem mais desafiador do ponto de vista matemático e computacional. Primeiramente, nós discutimos sobre a solução ótima desse problema que pode ser obtida através de programação inteira. Motivado pela alta complexidade computacional desta solução, propomos o uso de técnicas de relaxamento do problema de otimização inteiro e aplicação de programação linear (contínua). Através de simulações computacionais, demonstramos que o esquema proposto é capaz de encontrar a solução ótima em pelo menos 55% das simulações realizadas com uma complexidade computacional muito menor. Para os casos em que a solução obtida pela programação linear contínua não é inteira, o estudo propõe um algoritmo que obtém uma solução inteira através de técnicas de arredondamento. Apresentamos também uma análise de desempenho comparando o algoritmo desenvolvido com algoritmos presentes na literatura.

Submitted by Marco Antônio de Ramos Chagas (mchagas@ufv.br) on 2017-08-22T12:50:56Z No. of bitstreams: 1 texto completo.pdf: 2002096 bytes, checksum: 846f5e7b160234fc5880c038b656d3f6 (MD5) / Made available in DSpace on 2017-08-22T12:50:56Z (GMT). No. of bitstreams: 1 texto completo.pdf: 2002096 bytes, checksum: 846f5e7b160234fc5880c038b656d3f6 (MD5) Previous issue date: 2017-03-07 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Este trabalho aborda o problema de flow shop scheduling não permutacional com trabalhadores heterogêneos (FSNPTH). Sendo este classificado como um problema multicomponente, uma vez que, combina dois problemas no qual o resultado de um afeta o outro. O FSNPTH é composto por dois problemas clássicos de otimização combinatória: alocação de trabalhadores em máquinas e o flow shop scheduling não permutacional (FSNP). O problema consiste em alocar trabalhadores hete- rogêneos em máquinas dispostas em série, na qual a heterogeneidade se dá pelo tempo gasto pelo trabalhador ao operar uma máquina. A alocação dos trabalha- dores definem os tempos de execução das tarefas do problema de FSNP. O objetivo do problema de FSNPTH é minimizar o tempo máximo de conclusão das tarefas, conhecido como makespan. Para resolve-lo, inicialmente é proposto a aplicação do método Proximity Search (PS) para tentar determinar soluções ótimas para o pro- blema utilizando o modelo de programação linear inteira mista 0-1 (PLIM). Esse método consiste em substituir a função objetivo por uma função de proximidade e adicionar uma restrição de corte no modelo. Iterativamente o novo modelo é resolvido e a restrição de corte é atualizada. Isso garante que PS limite o espaço de busca e identifique as soluções ótimas. Foram desenvolvidas três versões do PS denotadas por P S 1 , P S 2 e P S 2RIN S . Dado que o problema pertence à classe NP-Difícil e é considerado de difícil resolução de maneira exata, foram desenvolvi- dos dois algoritmos híbridos, VNS-IG e TS-IG, a fim de obter soluções de forma aproximada de alta qualidade em baixo tempo computacional. Esses algoritmos combinam as meta-heurísticas Variable Neighborhood Search (VNS) e Busca Tabu (TB, do inglês Tabu Search) com o Iterated Greedy (IG). Experimentos computa- cionais e análises estatísticas foram realizados a fim de comparar o desempenho das versões do PS e dos algoritmos propostos. De acordo com os experimentos computacionais, as versões do PS obtiveram melhorias na qualidade da solução obtida e redução no tempo computacional se comparado a resolução do modelo matemático pelo solver IBM ILOG CPLEX. Além disso os experimentos realiza- dos mostram que algoritmos propostos são significativamente superiores ao melhor algoritmo da literatura (Scatter Search) em relação a dois fatores: qualidade das soluções e tempo de execução. / The current work addresses the non-permutation flow shop scheduling problem with heterogeneous workers (Het-FSSP), which is defined as a multicomponent problem, since it combines two problems where the result of one affects the other. Het-FSSP consists of two classical combinatorial optimization problems: machine worker allocation and non-permutation flow shop scheduling (NPFSS). The pro- blem is to allocate heterogeneous workers in machines arranged in series, in which the heterogeneity is due to the time spent by the worker when operating a ma- chine. The allocation of workers defines the periods of execution of the jobs of the NPFSS problem. The goal of the Het-FSSP problem is to minimize the maximum job completion time, which is known as makespan. In order to solve this problem, it is initially proposed to apply the Proximity Search (PS) method to try to de- termine optimal solutions for the problem using mixed integer programing (MIP) model. This method consists of replacing the objective function with a proximity function and adding a cut-off constraint on the model. Then, by iteration, the new model is resolved and the cut restriction is updated. This ensures that PS limits the search space and identifies optimal solutions. Three PS versions denoted by P S 1 , P S 2 and P S 2RIN S have been developed. Since the problem belongs to the NP-Difficult class and is considered to be difficult to solve exactly, two hybrid algorithms, VNS-IG and TS-IG, were developed in order to obtain approximate solutions of high quality in low computational time. These algorithms combine the meta-heuristics Variable Neighborhood Search (VNS) and Tabu Search (TS) with Iterated Greedy (IG). Computational experiments and statistical analyzes were performed in order to compare the performance of PS versions and the proposed algorithms. The computational experiments results suggest that the PS versions acquired improvements in the quality of the solution obtained and also reduced computational time spent compared to the resolution of the mathematical model by the IBM ILOG CPLEX solver. In addition, the experiments performed have shown that the proposed algorithms are significantly superior to the best algorithm found in the literature (Scatter Search) in relation to two factors: solution quality and execution time.

BEZERRA FILHO, P. T. F. Proposição de um controlador de cargas inteligente considerando custo energético e conforto baseado em programação linear inteira. 2016. 91 f. Dissertação (Mestrado em Engenharia de Teleinformática) – Centro de Tecnologia, Universidade Federal do Ceará, Fortaleza, 2016. / Submitted by Hohana Sanders (hohanasanders@hotmail.com) on 2016-10-04T13:03:49Z No. of bitstreams: 1 2016_dis_ptcbezerrafilho.pdf: 4165062 bytes, checksum: ac31e3293fa7040f35499a83614b5d4c (MD5) / Rejected by Marlene Sousa (mmarlene@ufc.br), reason: Substituir arquivo on 2016-11-01T12:39:19Z (GMT) / Submitted by Hohana Sanders (hohanasanders@hotmail.com) on 2016-11-01T12:45:59Z No. of bitstreams: 1 2016_dis_ptfbezerrafilho.pdf: 4165062 bytes, checksum: ac31e3293fa7040f35499a83614b5d4c (MD5) / Approved for entry into archive by Marlene Sousa (mmarlene@ufc.br) on 2016-11-01T12:48:36Z (GMT) No. of bitstreams: 1 2016_dis_ptfbezerrafilho.pdf: 4165062 bytes, checksum: ac31e3293fa7040f35499a83614b5d4c (MD5) / Made available in DSpace on 2016-11-01T12:48:37Z (GMT). No. of bitstreams: 1 2016_dis_ptfbezerrafilho.pdf: 4165062 bytes, checksum: ac31e3293fa7040f35499a83614b5d4c (MD5) Previous issue date: 2016-07-20 / Energy efficiency is a vital subject for the world. In the years to come it is expected that residences and industries will become smart consumers and the grid will be used more efficiently, easing the investment needs in the expansion of power grid. A smart home controller can help the residential consumers to achieve economic savings by moving the start of each load to times of low tariff. A negative effect not yet studied is the impact on the customer comfort of such controller. In this master thesis the comfort problem will be mathematically described as a integer programming optimization problem and it will be demonstrated by computer simulations that it is possible to achieve high levels of economic saving without a great impact on the user comfort level by making the controller optimize a combination of both objective functions. / Eficiência energética é um assunto de vital importância no âmbito nacional e internacional. Espera-se que nos próximos anos residências e indústrias tornem-se consumidores inteligentes, utilizando a rede de energia elétrica de forma mais eficiente, amenizando as necessidades de investimento na expansão da rede elétrica. Um controlador de cargas inteligente pode ser utilizado em residências para alcançar economia energética, movendo o horário de início das cargas para momentos de menor consumo da rede, com tarifas reduzidas. Um efeito negativo ainda não estudado é o impacto no conforto dos consumidores deste tipo de controlador. Neste trabalho os problemas de eficiência energética e conforto dos consumidores são descritos como problemas de otimização utilizando programação linear inteira. É mostrado através de simulações computacionais que é possível obter altos níveis de economia energética sem causar grandes impactos no nível de conforto dos usuários, ao fazer o controlador otimizar uma combinação das duas funções objetivo.

FERREIRA, Mardson da Silva. Problema do arranjo linear mínimo. 2016. 69 f. Dissertação (Mestrado em Ciência da Computação)-Universidade Federal do Ceará, Fortaleza, 2016. / Submitted by Anderson Silva Pereira (anderson.pereiraaa@gmail.com) on 2017-01-10T20:22:09Z No. of bitstreams: 1 2016_dis_msferreira.pdf: 1134504 bytes, checksum: 8ad24fa36a9ff4306ff861c7a5b40f12 (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2017-01-11T15:39:52Z (GMT) No. of bitstreams: 1 2016_dis_msferreira.pdf: 1134504 bytes, checksum: 8ad24fa36a9ff4306ff861c7a5b40f12 (MD5) / Made available in DSpace on 2017-01-11T15:39:52Z (GMT). No. of bitstreams: 1 2016_dis_msferreira.pdf: 1134504 bytes, checksum: 8ad24fa36a9ff4306ff861c7a5b40f12 (MD5) Previous issue date: 2016 / Let G = (V, E) be a simple and undirected graph of set of vertices V and set of edges E. Given an assignment of distinct labels in {1, · · · , |V |} to the vertices of G, for every edge uv ∈ E, we define its weight as the absolute difference of labels given to its end nodes. The minimum linear arrangement problem (MinLA) consists in finding a labeling of the vertices of G such that the sum of the weights of its edges is minimized. MinLA is an NP-Hard problem whose corresponding polyhedron has a factorial number of extreme points. In this work, we investigate a recent quadratic model for the MinLA presenting O(|V |² ) variables and O(|V |² ) constraints. This model has the smallest number of variables and constraints among all models in the literature for the problem. We present some theoretical results for the quadratic model, and show how to obtain a mixed linear model whose optimal solution is the same of the quadratic one. We also present valid inequalities for the proposed models. We discuss two heuristics for the problem and propose a column generation algorithm and a specialized Branch and Bound for MinLA. Computational experiments show that the new quadratic and mixed linear models performed better than existing ones in the literature for new and benchmark instances of this problem. / Seja G = (V, E) um grafo simples e não orientado de conjunto de vértices V e conjunto de arestas E. Dada uma atribuição de rótulos distintos em {1, · · · , |V |} aos vértices de G, para cada aresta uv ∈ E, definimos seu peso como sendo a diferença absoluta entre os rótulos atribuídos às suas extremidades. O problema do arranjo linear mínimo (MinLA) é encontrar uma rotulação dos vértices de G de modo que a soma dos pesos de suas arestas seja mínima. MinLA é um problema NP-Difícil cujo poliedro correspondente tem um número fatorial de pontos extremos. Neste trabalho, investigamos um recente modelo quadrático para o MinLA com O(|V |² ) variáveis e O(|V |² ) restrições. Esse modelo apresenta o menor número de variáveis e restrições dentre todos os modelos da literatura para o problema. Apresentamos alguns resultados teóricos para o modelo quadrático, bem como mostramos como obter um modelo linear misto cuja solução ótima é a mesma do modelo quadrático. Propomos igualmente desigualdades válidas para os modelos propostos. Apresentamos duas heurísticas para o problema. Implementamos um algoritmo de geração de colunas e um Branch and Bound especializado. Experimentos computacionais mostram que o novo modelo teve desempenho superior aos demais modelos conhecidos.

Submitted by Reginaldo Soares de Freitas (reginaldo.freitas@ufv.br) on 2016-04-27T09:48:38Z No. of bitstreams: 1 texto completo.pdf: 1187966 bytes, checksum: 9ba7c5ee8c3eafbfbcf97aa8cf96eae5 (MD5) / Made available in DSpace on 2016-04-27T09:48:38Z (GMT). No. of bitstreams: 1 texto completo.pdf: 1187966 bytes, checksum: 9ba7c5ee8c3eafbfbcf97aa8cf96eae5 (MD5) Previous issue date: 2015-12-10 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Este trabalho aborda o problema de sequenciamento de tarefas em máquinas parale- las não-relacionadas considerando restrições de precedência entre as tarefas e tempos de preparação dependentes da sequência e da máquina. Este problema tem como objetivo minimizar o tempo máximo de conclusão do sequenciamento, conhecido como makespan. Em problemas que consideram restrições de precedência, nenhuma tarefa pode iniciar seu processamento sem que todas as suas tarefas predecessoras tenham sido concluídas. Para resolver este problema foram desenvolvidos três mo- delos de programação linear inteira mista (PLIM), denotados por Modelo 1, Modelo 2 e Modelo 3. Em seguida, sete heurísticas construtivas foram desenvolvidas, deno- tadas por HC1 a HC7, as quais se diferenciam pelas regras de prioridade utilizadas. Neste trabalho também é implementado o método chamado Proximity Search (PS), que tenta determinar soluções ótimas para o problema. O método PS precisa de uma solução inicial e de um modelo base de PLIM. Neste método a função objetivo do modelo é substituída por uma função de proximidade e o conjunto de soluções viáveis é reduzido através da adição de cortes. A ideia é, iterativamente, resolver o modelo com a tentativa de melhorar a solução corrente. Foram desenvolvidas três versões do PS denotadas por P S1, P S2 e P S2RIN S . Neste trabalho também foram desenvolvidos algoritmos baseados em meta-heurísticas a fim de resolver o problema de forma aproximada. Primeiramente, foram desenvolvidas duas buscas locais denotadas por BL1 e BL2 baseadas na estratégia de inserção por vizinhança. Em seguida, foram implementadas duas meta-heurísticas: GRASP (Greedy Ran- domized Adaptive Search) e IG (Iterated Greedy). Experimentos computacionais e análises estatísticas foram realizados a fim de comparar o desempenho dos modelos, das versões do P S e das heurísticas propostas. De acordo com os experimentos, o Modelo 1 apresentou-se mais eficiente na qualidade das soluções obtidas e a heurís- tica HC7 mostrou-se mais eficiente na geração de uma solução razoavelmente boa. Além disso, as versões do PS obtiveram melhorias na qualidade da solução obtida e redução no tempo computacional gasto se comparado ao Modelo 1. Em seguida, o IG obteve desempenho significativamente melhor que o GRASP e o PS em relação à qualidade da solução final e a velocidade com que a solução corrente é melhorada. / In this work we address the scheduling problem in unrelated parallel machine with precedence constraints between the jobs and sequence-dependent and machine- dependent setup times. The objective of this problem is to minimize the maximum completion time of sequence, called makespan. The precedence constraints force a job not to be started before all its predecessors are finished. To solve this problem, we developed three models of mixed integer programming (MIP), denoted by Model 1, Model 2 and Model 3. Next, seven constructive heuristics were developed, deno- ted by HC1 to HC7, which differ in the priority rules. Also in this work, a method called Proximity Search (PS) is implemented, which tries to find optimal solutions to the problem. The method requires an initial solution and a MILP-based model. In this method, the objective function of the model is replaced by a proximity func- tion and the set of feasible solutions is reduced by the addition of cuts. The idea is to iteratively solve the model trying to improve the current solution. We deve- loped three versions of the P S denoted by P S1, P S2 and P S2RIN S . In addition, we developed algorithms based on metaheuristics to solve the problem approxima- tely. First, were developed two local searches denoted by BL1 and BL2 based on the insertion neighborhood. Next, were implemented two metaheuristics: GRASP (Greedy Randomized Adaptive Search) and IG (Iterated Greedy). Computational experiments and statistical analyzes were performed in order to compare the per- formance of models, PS versions and heuristics. According to the experiments, the Model 1 is more efficient in the quality of solutions and the HC7 heuristic is more efficient in generating a reasonably good solution. In addition, the versions of the PS obtained improvements in the quality of the obtained solution and reduction in computational time spent compared to Model 1. Then, the IG obtained significantly better performance than the GRASP and PS in relation to the quality of the final solution and the speed with which the current solution is improved.

Submitted by Marco Antônio de Ramos Chagas (mchagas@ufv.br) on 2016-09-13T12:57:14Z No. of bitstreams: 1 texto completo.pdf: 716367 bytes, checksum: 3555ebb07d86905dcc01ee33b9bc59f9 (MD5) / Made available in DSpace on 2016-09-13T12:57:14Z (GMT). No. of bitstreams: 1 texto completo.pdf: 716367 bytes, checksum: 3555ebb07d86905dcc01ee33b9bc59f9 (MD5) Previous issue date: 2016-02-26 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / A cada dia mais dados são gerados das mais diversas fontes. A extração de conheci- mento das bases de dados torna-se cada vez mais desafiadora, visto que os processos utilizados não são triviais. O agrupamento de dados usa técnicas que são capa- zes de trabalhar com dados pouco conhecidos de forma não supervisionada. Essas técnicas dividem os dados em grupos tentando capturar a estrutura presente nos dados para obter um conhecimento que servirá de ponto inicial para seu estudo. Poucos algoritmos de agrupamentos conseguem trabalhar em um contexto escalá- vel. Um dos algoritmos mais influentes no agrupamento é o k -médias, que possui complexidade linear e duas fases bem distintas, facilmente adaptada para modelos escaláveis. Porém, k -médias possui limitações, como sensibilidade à inicialização e especificação do número de grupos k, que geralmente é desconhecido. O obje- tivo desta pesquisa é estudar e desenvolver algoritmos de agrupamento para este contexto escalável. Especificamente, procura-se trabalhar com meta-heurísticas que proporcionem o agrupamento escalável sem a necessidade de especificação do nú- mero de grupos k. Essa dissertação propõe dois novos algoritmos de agrupamento que encontram um valor para k automaticamente em um modelo escalável chamado MapReduce. Adicionalmente, foi estudado um algoritmo com o mesmo propósito encontrado na literatura. Todos os algoritmos foram desenvolvidos e comparados de duas maneiras: pela sua complexidade assintótica e através de experimentos em bases artificiais e reais. Com base em testes estatísticos, foi possível verificar as principais diferenças entre a performance dos algoritmos. / Everyday more data are generated from several sources. The knowledge extraction from datasets becomes more and more challenging as the applied techniques are not trivial. Data clustering techniques are able to work with little knowledge about the data in a totally unsupervised manner. These techniques divide data into clusters trying to capture the structure of the data to obtain knowledge that will serve as a starting point for further studies. Few clustering algorithms are able to work in a scalable scenario. One of the most influential clustering algorithms is k -means, which has linear asymptotic complexity and two distinct phases, which can be easily adapted for scalable models. However, k -means has limitations such as sensitivity to initialization and previous specification of the numbers of clusters k, which is generally unknown, specially for real world scenarios. The objective of this rese- arch is to study and develop scalable clustering algorithms. Specifically, the use of meta-heuristics for scalable clustering to automatically determine the number of k clusters. This dissertation proposes two new clustering algorithms that are able to automatically find the value k in a scalable programing model called MapRe- duce. Additionally, an state-of-art algorithm from the literature has been studied and compared. All algorithms were developed and compared in two ways: based on their asymptotic complexity and through experiments in artificial and real datasets. Based on statistical tests, is was possible to find the main differences among quality and performance of all compared algorithms.