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 Reginaldo Soares de Freitas (reginaldo.freitas@ufv.br) on 2016-08-25T18:42:05Z No. of bitstreams: 1 texto completo.pdf: 824487 bytes, checksum: 7543250bb64554ce1550eac3064b9ccc (MD5) / Made available in DSpace on 2016-08-25T18:42:05Z (GMT). No. of bitstreams: 1 texto completo.pdf: 824487 bytes, checksum: 7543250bb64554ce1550eac3064b9ccc (MD5) Previous issue date: 2016-02-24 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / O trabalho consiste em apresentar uma proposta alternativa para o estudo da análise combinatória utilizando o triângulo de Pascal associados ao princípio aditivo e multiplicativo. Essa proposta visa contar os diversos tipos de funções e também demonstrar algumas identidades presentes no triângulo de Pascal via argumentos combinatórios. / The work presents an alternative proposal for the study of combinatorial analysis using Pascal’s triangle associated with additive and multiplicative principle. The proposal aims to count the different types of functions and also demonstrates some identities present in Pascal’s triangle through combinatorial arguments.

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.

Made available in DSpace on 2016-08-29T15:36:58Z (GMT). No. of bitstreams: 1 tese_5112_.pdf: 2115802 bytes, checksum: 4156ee444f2073e0a5e4552dc48ba7fc (MD5) Previous issue date: 2011-10-04 / MENEGUZZI, Cristiane Meneguzzi. Modelo de roteamento de veículos aplicado ao planejamento do Inventário Florestal. 2011. Dissertação (Mestrado em Ciências Florestais) Universidade Federal do Espírito Santo, Alegre-ES. Orientador: Prof. Dr. Gilson Fernandes da Silva. Coorientador: Geraldo Regis Mauri. Na área florestal, ainda é dada maior ênfase ao desenvolvimento de estudos envolvendo as etapas de colheita e transporte florestal, por serem diretamente responsáveis pelo custo final da madeira. Entretanto, diversas outras etapas possuem grande potencial para estudos, como é o caso do inventário florestal. Informações fornecidas pelo inventário florestal são importantes no planejamento de todo empreendimento florestal, pois subsidiam qualquer tomada de decisão envolvendo recursos florestais. Nesta pesquisa, utilizou-se o modelo de roteamento de veículos (PRV) no planejamento dessa atividade. O PRV e suas variantes vêm sendo amplamente estudados nos últimos anos, principalmente pela sua aplicabilidade e eficiência em gerar soluções apresentando redução de custo e/ou distâncias. O objetivo geral foi otimizar o planejamento da atividade de inventário florestal a partir de um modelo PRV e avaliar a importância do uso desta técnica no rendimento das atividades. Dentre os fatores que influenciam neste rendimento, a dispersão espacial, característica básica dos povoamentos florestais, é um fator controlável a partir do uso de técnicas que possibilitem associá-lo ao planejamento. Estudos mostram que essa associação traz resultados significativos. Palavras-chave: branch-and-bound, pesquisa operacional, planejamento, otimização combinatória.

Programa de Pós-Graduação em Ciência da Computação. Departamento de Ciência da Computação, Instituto de Ciências Exatas e Biológicas, Universidade Federal de Ouro Preto. / Submitted by Oliveira Flávia (flavia@sisbin.ufop.br) on 2014-10-08T18:11:44Z No. of bitstreams: 1 DISSERTAÇÃO_AlgoritmoEstimaçãoDistribuição.pdf: 4257329 bytes, checksum: 46c818238b61dc57ce8e996ee4c097f8 (MD5) / Approved for entry into archive by Gracilene Carvalho (gracilene@sisbin.ufop.br) on 2014-11-04T16:22:10Z (GMT) No. of bitstreams: 1 DISSERTAÇÃO_AlgoritmoEstimaçãoDistribuição.pdf: 4257329 bytes, checksum: 46c818238b61dc57ce8e996ee4c097f8 (MD5) / Made available in DSpace on 2014-11-04T16:22:10Z (GMT). No. of bitstreams: 1 DISSERTAÇÃO_AlgoritmoEstimaçãoDistribuição.pdf: 4257329 bytes, checksum: 46c818238b61dc57ce8e996ee4c097f8 (MD5) Previous issue date: 2013 / Neste trabalho, propõem-se um novo algoritmo híbrido denominado Multiobjective Optimization Estimation of Distribution Algorithm Based on Bee Colonies and Clusters (MOEDABC) para resolução de problemas de otimização multiobjetivo de larga escala no domínio contínuo. Este algoritmo é inspirado na organização de uma colônia de abelhas e baseia-se nos algoritmos de estimação de distribuição. Como forma de gerar melhores soluções utiliza-se também técnicas de clusterização com a finalidade de aumentar a convergência local das soluções na fronteira Pareto. O algoritmo é baseado em quatro tipos de abelhas: as campistas, as observadoras, as nutrizes e as escoteiras, onde cada uma utiliza uma forma diferente de gerar as novas soluções. Combinando diferentes técnicas como clusterização, estimação de distribuição e algoritmos genéticos possibilitou-se um melhor aprendizado por meio de modelos probabilísticos baseados em distribuições Gaussianas e de Cauchy, obtendo assim soluções de maior qualidade. Em busca de obter maior flexibilidade do algoritmo na resolução de problemas foi introduzido um feromônio de controle responsável por controlar a proporção de cada tipo de abelhas na colônia. Comparado com outros algoritmos os resultados obtidos demonstram que o algoritmo proposto apresenta uma maior velocidade de convergência e uma melhor distribuição das soluções na fronteira Pareto conforme os indicadores utilizados. _______________________________________________________________________ / ABSTRACT: In this paper, are proposed a new hybrid optimization algorithm denominated Multiobjective Estimation of Distribution Algorithm based on Bee Colonies and Clusters (MOEDABC) to solve large scale multi-objective optimization problems in continuous domain. This algorithm is inspired in the organization of a bee colony and is based on estimation of distribution algorithms. As a way to generate better solutions also employ the clustering methods in order to increase the local convergence of the solutions in the Pareto front. The algorithm is based in four types of bees, the employer, the onlookers, the nursings and scouts, each a of which uses differents way of generating new solutions. Combining different techniques such as clustering, estimation of distribution algorithms and genetic algorithms was possible a better learning through probabilistic models based on Gaussian distributions and Cauchy, thus obtaining higher quality solutions. In search of greater flexibility of the algorithm in solving problems we introduce a pheromone control that is responsible for controlling the proportion of each type of bees in the colony. Compared with other algorithms the results obtained show that the proposed algorithm shows a faster convergence and a better distribution of solutions in the front Pareto according to the metrics used.

Programa de Pós-Graduação em Ciência da Computação. Departamento de Ciência da Computação, Instituto de Ciências Exatas e Biológicas, Universidade Federal de Ouro Preto. / Submitted by Oliveira Flávia (flavia@sisbin.ufop.br) on 2014-09-29T16:05:40Z No. of bitstreams: 2 license_rdf: 21174 bytes, checksum: b98541e59f955f816d2d78f2222e44c8 (MD5) DISSERTAÇÃO_MetaheurísticasBuscaTabu.pdf: 1081988 bytes, checksum: 1df813c1c7108a23fd54b5fd3f7e804c (MD5) / Approved for entry into archive by Gracilene Carvalho (gracilene@sisbin.ufop.br) on 2014-11-07T13:01:18Z (GMT) No. of bitstreams: 2 license_rdf: 21174 bytes, checksum: b98541e59f955f816d2d78f2222e44c8 (MD5) DISSERTAÇÃO_MetaheurísticasBuscaTabu.pdf: 1081988 bytes, checksum: 1df813c1c7108a23fd54b5fd3f7e804c (MD5) / Made available in DSpace on 2014-11-07T13:01:18Z (GMT). No. of bitstreams: 2 license_rdf: 21174 bytes, checksum: b98541e59f955f816d2d78f2222e44c8 (MD5) DISSERTAÇÃO_MetaheurísticasBuscaTabu.pdf: 1081988 bytes, checksum: 1df813c1c7108a23fd54b5fd3f7e804c (MD5) Previous issue date: 2013 / O Problema de Rodízio das Tripulações (PRT) do sistema de transporte público consiste em atribuir a cada tripulação uma sequência de jornadas para os dias do horizonte de planejamento. Como as jornadas diárias tem durações diferentes, as sequências das jornadas podem resultar em um acúmulo de horas extras ou de horas ociosas. Assim o objetivo do PRT é minimizar as horas extras da escala, compensando-as com ociosidades entre jornadas.Este é o princípio do banco de horas permitido pela legislação, desde que sejam respeitadas as restrições operacionais e leis trabalhistas. Neste trabalho o problema foi resolvido utilizando diferentes implementações do Algoritmo de Busca Tabu. Primeiramente é feita a geração da solução inicial através de uma heurística gulosa. A solução gerada é viável, no entanto os custos são altos. Depois são utilizadas as jornadas criadas e com base em trocas viáveis tenta diminuir o custo de cada rodízio com diferentes versões implementadas de Busca Tabu. Foram implementadas quatro versões: a primeira versão, BTMP, que possui menor tempo da busca local para quando encontra um vizinho melhor; a segunda, denominada BTMV, em que a busca local é efetuada sobre toda a vizinhança; a terceira, BTPV, que utiliza um critério de porcentagem variável para a busca pelo melhor vizinho e a quarta versão BTID, que utiliza critérios de intensificação e diversificação para a Busca Tabu. Ao montar um rodízio, devem ser consideradas as folgas das tripulações ao longo do período. Neste trabalho foi desenvolvido um modelo em dois cenários distintos: um que não considera a atribuição das folgas e outro que realiza esta atribuição. Posteriormente os resultados foram comparados aos obtidos no trabalho de Prates e Silva (2012) através da metaheurística VNS. Os resultados mostram que as implementações do modelo desenvolvido se aproveitam das características de cada etapa, gerando soluções mais econômicas.cada tripulação uma sequência de jornadas para os dias do horizonte de planejamento. Como as jornadas diárias tem durações diferentes, as sequências das jornadas podem resultar em um acúmulo de horas extras ou de horas ociosas. Assim o objetivo do PRT é minimizar as horas extras da escala, compensando-as com ociosidades entre jornadas. Este é o princípio do banco de horas permitido pela legislação, desde que sejam respeitadas as restrições operacionais e leis trabalhistas. Neste trabalho o problema foi resolvido utilizando diferentes implementações do Algoritmo de Busca Tabu. Primeiramente é feita a geração da solução inicial através de uma heurística gulosa. A solução gerada é viável, no entanto os custos são altos. Depois são utilizadas as jornadas criadas e com base em trocas viáveis tenta diminuir o custo de cada rodízio com diferentes versões implementadas de Busca Tabu. Foram implementadas quatro versões: a primeira versão, BTMP, que possui menor tempo da busca local para quando encontra um vizinho melhor; a segunda, denominada BTMV, em que a busca local é efetuada sobre toda a vizinhança; a terceira, BTPV, que utiliza um critério de porcentagem variável para a busca pelo melhor vizinho e a quarta versão BTID, que utiliza critérios de intensificação e diversificação para a Busca Tabu. Ao montar um rodízio, devem ser consideradas as folgas das tripulações ao longo do período. Neste trabalho foi desenvolvido um modelo em dois cenários distintos: um que não considera a atribuição das folgas e outro que realiza esta atribuição. Posteriormente os resultados foram comparados aos obtidos no trabalho de Prates e Silva (2012) através da metaheurística VNS. Os resultados mostram que as implementações do modelo desenvolvido se aproveitam das características de cada etapa, gerando soluções mais econômicas. __________________________________________________________________________ / ABSTRACT: The Crew Rostering Problem (CRP) of public transportation system consists in assigning, for each crew, a sequence of journeys over the days in the planning horizon. As the daily journeys have different durations, the sequences can result in an accumulation of overtime or idle hours. Thus, the goal of the CRP is to minimize the overtime in the schedule, compensating them with idleness between journeys. This is the principle of the bank of hours allowed by the legislation, subject to operational restrictions and labor laws. In this work, the problem was solved using Tabu Search algorithm. First is generated the initial solution by greedy search. The generated solution is feasible, though the costs are high. Then the journeys are used to created the rost and through viable changes it tries to decrease the cost of each rostering with different implemented versions of Tabu Search. Four versions have been implemented: the first version, BTMP, which has shorter local search stops when it finds a better neighbor; the second, so-called BTMV, wherein the local search is performed over the entire neighborhood; the third, BTPV, using a criterion percentage variable to search for the best neighbor and the fourth version BTID, which uses criteria intensification and diversification for Tabu Search. When mounting a rostering should be considered the respite of the crews throughout the period. Subsequently, the results were compared to those obtained in the work of Prates e Silva (2012) that uses VNS metaheuristic. The results show that the implementations of the model developed take advantage of the characteristics of each stage, generating more economic solutions.

Programa de Pós-Graduação em Ciência da Computação. Departamento de Ciência da Computação, Instituto de Ciências Exatas e Biológicas, Universidade Federal de Ouro Preto. / Submitted by Oliveira Flávia (flavia@sisbin.ufop.br) on 2014-11-20T16:36:46Z No. of bitstreams: 2 license_rdf: 22190 bytes, checksum: 19e8a2b57ef43c09f4d7071d2153c97d (MD5) DISSERTAÇÃO_PrinsMatheurísticaProblemas.pdf: 1066532 bytes, checksum: 4feb1b525e8f414603c45698cea9f6ea (MD5) / Approved for entry into archive by Gracilene Carvalho (gracilene@sisbin.ufop.br) on 2014-11-20T16:39:12Z (GMT) No. of bitstreams: 2 license_rdf: 22190 bytes, checksum: 19e8a2b57ef43c09f4d7071d2153c97d (MD5) DISSERTAÇÃO_PrinsMatheurísticaProblemas.pdf: 1066532 bytes, checksum: 4feb1b525e8f414603c45698cea9f6ea (MD5) / Made available in DSpace on 2014-11-20T16:39:12Z (GMT). No. of bitstreams: 2 license_rdf: 22190 bytes, checksum: 19e8a2b57ef43c09f4d7071d2153c97d (MD5) DISSERTAÇÃO_PrinsMatheurísticaProblemas.pdf: 1066532 bytes, checksum: 4feb1b525e8f414603c45698cea9f6ea (MD5) Previous issue date: 2014 / Uma importante técnica para resolver problemas de otimização é por meio de Programação Inteira Mista (MIP, do inglês Mixed Integer Programming). Uma formulação MIP de um problema envolve um conjunto de variáveis, um conjunto de restrições sobre estas variáveis, um conjunto de restrições de integralidade e uma função objetivo linear a otimizar. Aplicações em otimização inteira são encontradas em diversas àreas do conhecimento, incluindo-se roteamento de veículos, alocação de enfermeiros, programação de horários, entre outros. O uso de métodos heurísticos tem sido empregado na resolução de problemas MIP como uma forma de acelerar o processo de busca na árvore de branching. Este trabalho propõe uma adaptação da heurística MIP Relaxation Induced Neighborhood Search (RINS), que explora a ideia de fixar variáveis de mesmo valor na solução inteira e fracionária corrente. O método proposto, denominado pRINS, explora explicitamente técnicas de pré-processamento, procurando sistematicamente por um número ideal de fixações, visando a produzir sub-problemas de tamanho controlado. As variáveis a fixar são organizadas por meio de um vetor de prioridade, sendo propostas três maneiras de escolha destas variáveis, cada uma delas dando origem a uma variante do método. Em seguida, os problemas são criados e resolvidos de modo semelhante ao método Variable Neighborhood Descent até que um critério de parada seja satisfeito. Os resultados das variantes do método foram comparados com os do resolvedor COIN-OR e CBC stand-alone e com o método RINS original. Pelos resultados obtidos, o método proposto se mostrou com desempenho superior a essas duas técnicas. ______________________________________________________________________________________________ / ABSTRACT: An important technique for solving optimization problems is Mixed Integer Programming (MIP). A MIP formulation for a problem involves a set of variables, a set of constraints on these variables, a set of integrality constraints and a linear objective function to optimize. Applications in integer programming are found in many areas of knowledge, including vehicle routing, traveling salesman problem, nurse scheduling and school timetabling. Heuristic methods have been employed in solving MIP problems as a way to accelerate the search process in the branching tree. This dissertation proposes an adaptation of the MIP heuristic Relaxation Induced Neighborhood Search (RINS), which explores the idea of fixing variables with same value in integer and fractional current solutions. The proposed method, named pRINS, explicitly explores pre-processing techniques, systematically searching for the ideal number of fixations to produce sub-problems of controlled size. Candidate variables to be fixed are ranked and three different strategies to select among them were evaluated. Then, problems are created and solved similarly to the Variable Neighborhood Descent method until a stopping criterion is met. The results of the variants were compared to the COIN-OR CBC stand-alone solver and the original RINS method. The results indicate that pRINS presents a better heuristic behavior than other techniques.

Programa de Pós-Graduação em Ciência da Computação. Departamento de Ciência da Computação, Instituto de Ciências Exatas e Biológicas, Universidade Federal de Ouro Preto. / Submitted by Maurílio Figueiredo (maurilioafigueiredo@yahoo.com.br) on 2015-01-13T18:37:57Z No. of bitstreams: 2 license_rdf: 22190 bytes, checksum: 19e8a2b57ef43c09f4d7071d2153c97d (MD5) DISSERTAÇÂO_NovosAlgoritimos.pdf: 1337200 bytes, checksum: 1e210fd648c651e8b6990d8ededc6a2c (MD5) / Approved for entry into archive by Gracilene Carvalho (gracilene@sisbin.ufop.br) on 2015-01-15T17:28:11Z (GMT) No. of bitstreams: 2 license_rdf: 22190 bytes, checksum: 19e8a2b57ef43c09f4d7071d2153c97d (MD5) DISSERTAÇÂO_NovosAlgoritimos.pdf: 1337200 bytes, checksum: 1e210fd648c651e8b6990d8ededc6a2c (MD5) / Made available in DSpace on 2015-01-15T17:28:11Z (GMT). No. of bitstreams: 2 license_rdf: 22190 bytes, checksum: 19e8a2b57ef43c09f4d7071d2153c97d (MD5) DISSERTAÇÂO_NovosAlgoritimos.pdf: 1337200 bytes, checksum: 1e210fd648c651e8b6990d8ededc6a2c (MD5) Previous issue date: 2014 / Este trabalho trata o Problema de Sequenciamento em Máquinas Paralelas Não- Relacionadas com Tempos de Preparação Dependentes da Sequência (UPMSPST, do inglês Unrelated Parallel Machine Scheduling Problem with Setup Times), objetivando minimizar o makespan. Para resolvê-lo foram desenvolvidos três algoritmos heurísticos e um algoritmo híbrido. O primeiro algoritmo heurístico, denominado HIVP, tem uma solução inicial gerada por um procedimento construtivo parcialmente guloso baseado no método Heuristic-Biased Stochastic Sampling e na regra Adaptive Shortest Processing Time { ASPT. Essa solução e, posteriormente, refinada pelo procedimento Iterated Local Search { ILS, tendo o Random Variable Neighborhood Descent como método de busca local. Além disso, periodicamente a busca é intensificada e diversificada por meio de um procedimento Path Relinking { PR. No segundo algoritmo heurístico, denominado GIAP, a solução inicial é criada por um procedimento inspirado no Greedy Randomized Adaptive Search Procedures. Nesse segundo algoritmo, a solução é refinada por um procedimento ILS que utiliza como método de busca local o procedimento Adaptive Local Search { ALS. A busca _e também intensificada e diversificada por meio de um procedimento PR. O terceiro e último algoritmo heurístico, denominado AIRP, tem sua solução inicial gerada por um procedimento construtivo guloso baseado na regra ASPT. Essa solução é refinada por um procedimento ILS que tem como busca local um procedimento chamado RIV. De forma análoga aos algoritmos anteriores, a busca também passa por uma intensificação ao e diversificação periodicamente por meio de um procedimento PR. O algoritmo híbrido, denominado AIRMP, tem o funcionamento similar ao do algoritmo heurístico AIRP, diferindo deste por acrescentar um módulo de programação linear inteira mista. Para a aplicação desse módulo são selecionados um par de máquinas e subconjuntos de tarefas nessas máquinas. Esses subconjuntos são combinados e passam por uma busca local que consiste em acionar um resolvedor de programação matemática aplicado a melhor das formulações de programação matemática dentre aquelas estudadas e desenvolvidas. Pelos experimentos computacionais foi possível concluir que o AIRP obteve os melhores resultados dentre os algoritmos heurísticos propostos, conseguindo superar vários outros algoritmos da literatura. Também foram realizados experimentos para comparar os algoritmos AIRMP e AIRP. Como o AIRMP necessita de um tempo maior para acionar o módulo de programação matemática, esses experimentos utilizaram um tempo maior de execução. Observou-se, no entanto, que a adição do módulo de programação matemática não melhorou o desempenho do AIRMP no tempo testado e na estrutura utilizada de subconjuntos de tarefas. Esses testes também mostraram que aumentando-se o tempo de processamento do AIRP, o algoritmo e capaz de encontrar melhores soluções. __________________________________________________________________________________________________________________________ / ABSTRACT: This paper deals with the Unrelated Parallel Machine Scheduling Problem with Setup Times { UPMSPST, having as goal to minimize the makespan. In order to solve it, three heuristic algorithms and a hybrid algorithm were developed. The first heuristic algorithm, called HIVP, has an initial solution generated by a greedy constructive procedure based on the Heuristic-Biased Stochastic Sampling and on the Adaptive Shortest Processing Time { ASPT rule. This solution is then refined by the Iterated Local Search { ILS procedure, having the Random Variable Neighborhood Descent as local search method. Moreover, the search is periodically intensified and diversified by a Path Relinking { PR procedure. In the second algorithm, called GIAP, the initial solution is created by a procedure inspired on the Greedy Randomized Adaptive Search Procedures. This solution is then refined by an ILS procedure that uses the procedure Adaptive Local Search { ALS as local search method. The search is also intensified and diversified by a PR procedure. The third and final heuristic algorithm, called AIRP, has its initial solution generated by a greedy constructive procedure based on ASPT rule. This solution is then refined by the ILS, having as local search a procedure called RVI. Analogously to the previous algorithms, the search also applies periodically an intensification and diversification strategy based on the PR procedure. The hybrid algorithm, named AIRMP, is similar to the AIRP heuristic algorithm, differing from it by adding a module of mixed integer linear programming. To apply this module one pair of machines are selected and subsets of jobs of these machines. These subsets are combined and they pass through a local search that consists in running a mathematical programming solver applied to the best formulation among the studied and developed ones. By computational experiments it was concluded that the AIRP algorithm obtained the best results among the proposed heuristic algorithms, outperforming several other algorithms from the literature. Experiments were also conducted to compare the AIRMP and AIRP algorithms. As the AIRMP needs more time to execute the mathematical programming module, these experiments utilized a higher runtime. It was observed, however, that the addition of the mathematical programming module does not improved the performance of the AIRMP algorithm in the tested time and in the used structure of subsets of jobs. These tests also showed that increasing the processing time of the AIRP, the algorithm is able to find better solutions.

Submitted by MAURIZIO MARCHETTI null (maurizius@terra.com.br) on 2016-04-29T19:25:39Z No. of bitstreams: 1 UNESP entrega.pdf: 14595052 bytes, checksum: 1760390610892e246306287972e21913 (MD5) / Rejected by Felipe Augusto Arakaki (arakaki@reitoria.unesp.br), reason: Solicitamos que realize uma nova submissão seguindo as orientações abaixo: A versão final da dissertação/tese deve ser submetida no formato PDF (Portable Document Format) e o arquivo não deve estar protegido. Por favor, corrija o arquivo PDF e realize uma nova submissão com o arquivo desprotegido. Agradecemos a compreensão. on 2016-05-02T19:03:46Z (GMT) / Submitted by MAURIZIO MARCHETTI null (maurizius@terra.com.br) on 2016-05-02T20:01:26Z No. of bitstreams: 2 UNESP entrega.pdf: 14595052 bytes, checksum: 1760390610892e246306287972e21913 (MD5) LINEAMENTOS DE ANALISE COMBINATORIA 02.pdf: 14341052 bytes, checksum: 6d2c15e4c40cdfa8c838440bbd625acb (MD5) / Approved for entry into archive by Juliano Benedito Ferreira (julianoferreira@reitoria.unesp.br) on 2016-05-04T18:52:14Z (GMT) No. of bitstreams: 1 marchetti_m_me_rcla.pdf: 14341052 bytes, checksum: 6d2c15e4c40cdfa8c838440bbd625acb (MD5) / Made available in DSpace on 2016-05-04T18:52:14Z (GMT). No. of bitstreams: 1 marchetti_m_me_rcla.pdf: 14341052 bytes, checksum: 6d2c15e4c40cdfa8c838440bbd625acb (MD5) Previous issue date: 2016-02-29 / Não recebi financiamento / Com os avanços da computação, a matemática discreta passou a ser objeto de novas e mais complexas pesquisas. Uma das razões é que os fundamentos da computação encontram-se nos princípios da matemática discreta. No que se refere aos centros de pesquisa, cada vez são mais numerosos e avanlçdos os trabalhos que visam dar sistematicidade e rigor aos princípios da matemática discreta como aqueles já conquistados pela matemática contínua. Nesse contexto, nossa proposta no presente trabalho, ao atuar na formação de base relativa ao ensino da matemática discreta no ensino médio, foi apresentar um texto que ao mesmo tempo compilasse tópicos que jé existe a respeito e, também, introduzisse novas questões e teorias que colocassem em compasso ensino médio com os significativos avanços da matemática discreta produzida nos grandes centros mundiais. Dentro dessas novas questões e teorias, privilegiamos a introdução das funções geradoras como assunto a ser abordado no ensino médio como aprendizado para eventuais desenvolvimentos posteriores no ensino superior, tanto das faculdades de matemática quanto das faculdades de computação. O presente trabalho apresenta-se como obra de base, redigida em linguagem acessível a professores e alunos do ensino médio, sem abrir mão do rigor necessário próprio dos estudos matemáticos.