PEREIRA, M. B. Particle swarm optimization and differential evolution for base station placement with multi-objective requirements. 2015. 72 f. Dissertação (Mestrado em Engenharia de Teleinformática) – Centro de Tecnologia, Universidade Federal do Ceará, Fortaleza, 2015. / Submitted by Marlene Sousa (mmarlene@ufc.br) on 2015-09-21T12:31:09Z No. of bitstreams: 1 2015_dis_mbpereira.pdf: 3666612 bytes, checksum: bc2466a863d5e64d596e5667f3ef5426 (MD5) / Approved for entry into archive by Marlene Sousa(mmarlene@ufc.br) on 2015-10-09T14:45:25Z (GMT) No. of bitstreams: 1 2015_dis_mbpereira.pdf: 3666612 bytes, checksum: bc2466a863d5e64d596e5667f3ef5426 (MD5) / Made available in DSpace on 2015-10-09T14:45:26Z (GMT). No. of bitstreams: 1 2015_dis_mbpereira.pdf: 3666612 bytes, checksum: bc2466a863d5e64d596e5667f3ef5426 (MD5) Previous issue date: 2015-07-15 / The infrastructure expansion planning in cellular networks, so called Base Station Placement (BSP) problem, is a challenging task that must consider a large set of aspects, and which cannot be expressed as a linear optimization function. The BSP is known to be a NP-hard problem unable to be solved by any deterministic method. Based on some fundamental assumptions of Long Term Evolution - Advanced (LTE-A) networks, this work proceeds to investigate the use of two methods for BSP optimization task: the Particle Swarm Optimization (PSO) and the Differential Evolution (DE), which were adapted for placement of many new network nodes simultaneously. The optimization process follows two multi-objective functions used as fitness criteria for measuring the performance of each node and of the network. The optimization process is performed in three scenarios where one of them presents actual data collected from a real city. For each scenario, the fitness performance of both methods as well as the optimized points found by each technique are presented / O planejamento de expansão de infraestrutura em redes celulares é uma desafio que exige considerar diversos aspectos que não podem ser separados em uma função de otimização linear. Tal problema de posicionamento de estações base é conhecido por ser do tipo NP-hard, que não pode ser resolvido por qualquer método determinístico. Assumindo características básicas da tecnologia Long Term Evolution (LTE)-Advanced (LTE-A), este trabalho procede à investigação do uso de dois métodos para otimização de posicionamento de estações base: Otimização por Enxame de Partículas – Particle Swarm Optimization (PSO) – e Evolução Diferencial – Differential Evolution (DE) – adaptados para posicionamento de múltiplas estações base simultaneamente. O processo de otimização é orientado por dois tipos de funções custo com multiobjetivos, que medem o desempenho dos novos nós individualmente e de toda a rede coletivamente. A otimização é realizada em três cenários, dos quais um deles apresenta dados reais coletados de uma cidade. Para cada cenário, são exibidos o desempenho dos dois algoritmos em termos da melhoria na função objetivo e os pontos encontrados no processo de otimização por cada uma das técnicas

Made available in DSpace on 2016-08-29T14:10:21Z (GMT). No. of bitstreams: 1 tese_4922_Pesquisa_Dissertação_05_04_13.pdf: 1102725 bytes, checksum: 113332fdb7e612205dd8c629c3f72892 (MD5) Previous issue date: 2012-08-20 / Esta pesquisa investigou, em uma abordagem psicogenética, aspectos do funcionamento cognitivo de crianças por meio de um jogo regras com base na teoria de Piaget. Participaram do estudo 21 crianças, de ambos os sexos, com idades de oito e doze anos, de uma escola pública de Ensino Fundamental de Vitória-ES. A coleta de dados ocorreu em três encontros por dupla, utilizando-se como instrumento o jogo Lig-4 e um protocolo contendo questões e situações-problema. O primeiro encontro foi realizado em duas etapas: uma de aprendizagem e outra de prática do jogo. O segundo em dois momentos, sendo um destinado à prática do jogo e outro à primeira avaliação do nível de análise heurística. No terceiro realizou-se a prática do jogo e a segunda avaliação do nível de análise heurística. Os dados foram analisados por meio de níveis de análise heurística formulados em relação aos Sistemas Cognitivos I e II propostos por Piaget. Entre os resultados, verificou-se que a situação destinada à primeira avaliação e a ampliação da prática do jogo, não possibilitaram uma melhora expressiva no nível de análise heurística dos participantes de ambas as idades na segunda avaliação. No entanto, comparando-se o desempenho das crianças das duas idades, constatou-se que o das de doze anos foi superior ao das de oito anos, sendo que no Sistema Cognitivo I elas alcançaram níveis mais complexos do que no Sistema Cognitivo II. Conclui-se que o jogo Lig-4 mostrou-se adequado para a análise de Sistemas Cognitivos, fornecendo subsídios para trabalhos de avaliação e intervenção.

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.

Programa de Pós-Graduação em Ciência da Computação. Departamento de Computação, Universidade Federal de Ouro Preto. / Submitted by giuliana silveira (giulianagphoto@gmail.com) on 2016-02-16T17:53:54Z No. of bitstreams: 1 DISSERTAÇÃO_AlgorismosExatosHeurísticos.pdf: 1324128 bytes, checksum: d6be4d92516819c254e0a44cfaa3a120 (MD5) / Approved for entry into archive by Gracilene Carvalho (gracilene@sisbin.ufop.br) on 2016-02-19T13:16:22Z (GMT) No. of bitstreams: 1 DISSERTAÇÃO_AlgorismosExatosHeurísticos.pdf: 1324128 bytes, checksum: d6be4d92516819c254e0a44cfaa3a120 (MD5) / Made available in DSpace on 2016-02-19T13:16:22Z (GMT). No. of bitstreams: 1 DISSERTAÇÃO_AlgorismosExatosHeurísticos.pdf: 1324128 bytes, checksum: d6be4d92516819c254e0a44cfaa3a120 (MD5) Previous issue date: 2015 / O presente trabalho trata do projeto, implementação e avaliação de algoritmos exatos e heur ísticos, sequenciais e paralelos, para a resolu c~ao do problema da enumera c~ao de cliques com peso acima de um limiar (PECPL). Esse problema considera um grafo com vertices ponderados, onde o objetivo e encontrar todos os cliques maximais com peso acima de um limiar. Os algoritmos estudados neste trabalho são aplicados na separa ção de cortes no contexto de Programa ção Inteira. Encontrar todos os cliques acima de um dado peso e equivalente ao problema de encontrar todas as desigualdades violadas de clique. Foram desenvolvidas adapta ções em algoritmos conhecidos na literatura, para a resolução do problema. Para o algoritmo de Bron-Kerbosch, uma adapta c~ao foi realizada para resolver o PECPL. Al em disso, v arias melhorias foram propostas a m de melhorar a efi ciência na resolu ção das instâncias do problema. Foram propostas uma versão iterativa do algoritmo, originalmente recursivo, e uma versão paralela. O algoritmo de Ostergard e a heur stica busca tabu com multi-vizinhanças tamb ém foram implementados e modi ficados para re etir o problema abordado no presente trabalho. Por m, a metaheur stica Simulated Annealing foi proposta e desenvolvida utilizando-se das mesmas estruturas de vizinhan ca utilizadas na heur stica busca tabu com multivizinhanças. A diferen ça das duas t ecnicas est a na estrat égia de resolu ção do problema: enquanto a primeira utiliza-se do conceito de lista tabu, a ultima simula o processo de recozimento de metais. Nos experimentos computacionais, foram utilizadas 7292 instâncias, oriundas de quatro conjuntos referentes a separa ção de cortes em problemas formulados por meio do uso de programa c~ao inteira. Os experimentos foram conduzidos em duas partes: em um primeiro momento, as instâncias foram utilizadas para resolu ção do PECPL. Posteriormente, o foco foi a resolu ção do problema do clique de peso m áximo (PCPM). Quanto a resolu c~ao do PECPL, os resultados obtidos comprovam a efi ciência do algoritmo de Bron-Kerbosch, quando comparado aos demais algoritmos, ao encontrar a solu ção ótima para todas as instâncias e em um tempo consideravelmente menor do que as outras t ecnicas. Quando a an alise dos resultados foi direcionada a resolu c~ao do PCPM, todas as t écnicas implementadas obtiveram bons resultados, com destaque para a heur stica busca tabu com multi-vizinhan cas, a qual resolveu todas as instâncias de forma ótima, com o menor tempo computacional em rela c~ao as demais abordagens. Como trabalhos futuros, são sugeridos a ado c~ao de operadores l ogicos para a representa c~ao do grafo no algoritmo de Bron-Kerbosch, a melhoria da vers~ao paralela do algoritmo e o estudo do projeto das metaheurí sticas Simulated Annealing e busca tabu. __________________________________________________________________________________ / ABSTRACT : This work deals with the design, implementation and evaluation of exact and heuristic algorithms, sequential and parallel to the resolution of clique enumeration problem with weight above a threshold (PECPL). This problem considers a graph with weighted vertices, where the goal is to nd all maximal cliques with weight above a threshold. The algorithms studied in this work are applied in the separation cuts in the context of Integer Programming. Find all clique above a certain weight is equivalent to the problem of nding all the inequalities violated clique. Adaptations were developed algorithms known in the literature, to solve the problem. For the Bron-Kerbosch algorithm, an adaptation was made to solve the PECPL. In addition, several improvements were proposed in order to improve e ciency in the resolution of problem instances. It has been proposed an iterative version of the algorithm, recursive originally, and a parallel version. The Ostergard algorithm and multi-neighborhoods tabu search heuristic were also implemented and modi ed to re ect the problem addressed in this paper. Finally, the Simulated Annealing metaheuristic was proposed and developed using the same neighborhood structures used in multi-neighborhoods tabu search heuristic. The di erence of the two techniques is in solving strategy problem: while the rst is used the concept of tabu list, the last simulates the process of annealing of metals. In the computational experiments, we used 7292 instances, belonging to four sets related to the separation cuts in problems formulated by using integer programming. The experiments were conducted in two parts: at rst, the instances were used for solving the PECPL. Later, the focus was on resolving the maximum weight clique problem (PCPM). As for the resolution of the PECPL, the results prove the e ciency of Bron-Kerbosch algorithm, when compared to other algorithms to nd the optimal solution for all instances and in a considerably shorter time than the other techniques. When analyzing the results was directed to resolving the PCPM, all techniques implemented performed well, particularly the multi-neighborhoods tabu search heuristic, which solved all instances optimally with less computational time compared to other approaches. As future work, it is suggested the adoption of logical operators for the representation of the graph in Bron-Kerbosch algorithm, improved parallel version of the algorithm and the study design of simulated annealing and tabu search metaheuristics.

Esta tese investiga heurísticas de criação de oportunidades empreendedoras em startups. Pesquisas sobre ação empreendedora com base em heurísticas são desenvolvidas tendo como premissa que o mercado oferece várias oportunidades, prontas para serem selecionadas. Tais pesquisas não investigam como se dá a ação empreendedora quando há a necessidade de criação de uma nova oportunidade. Pesquisas sobre ação empreendedora com base em heurísticas também não exploram conceitualmente e empiricamente a criação de oportunidades empreendedoras por startups. Para preencher essas lacunas, esta tese se propõe a analisar a aderência da tipologia proposta por Bingham e Eisenhardt (2011) na criação de oportunidades empreendedoras por startups. A proposição que se faz é a seguinte: a tipologia proposta por Bingham e Eisenhardt não prevê heurísticas de gestão para a criação de novas oportunidades, já que tem como premissa que o mercado dispõe de várias oportunidades prontas para serem capturadas. Com base nesta análise, a seguinte pergunta dirige esta tese: Quais as heurísticas presentes na criação de oportunidades empreendedoras? Para responder a esta pergunta, esta tese constrói um quadro conceitual a partir da literatura e emprega a abordagem de pesquisa empírica, através da análise de ações empreendedoras unindo percepções, decisões e ações através de estudos de múltiplos casos realizados em oito startups. A contribuição central desta tese é a proposição de uma tipologia de heurísticas relacionadas à criação de oportunidades empreendedoras, adaptando a tipologia proposta por Bingham e Eisenhardt. Enquanto a tipologia de Bingham e Eisenhardt determina que empresas aprendem heurísticas dos tipos seleção, processual, prioridade e temporal, esta tese determina que empresas também aprendem heurísticas do tipo \'criação\' e propõe uma nova tipologia de heurísticas para a criação de oportunidades empreendedoras: \'startups aprendem heurísticas dos tipos criação, processual, prioridade e temporal\', uma vez que necessitam criar uma oportunidade que o mercado ainda não dispõe. / This thesis investigates heuristics creating entrepreneurial opportunities for startups. Research on entrepreneurial action based on heuristics are developed with the premise that the market offers several opportunities, ready to be selected. Such surveys do not investigate how is the entrepreneurial action when there is a need to create a new opportunity. Research on entrepreneurial action based on heuristics did not explore conceptually and empirically creating entrepreneurial opportunities for startups. To fill these gaps, this thesis aims to analyze the adherence of the typology proposed by Bingham and Eisenhardt (2011) in creating opportunities for entrepreneurial startups. The proposition that does is the following: the typology proposed by Bingham and Eisenhardt does not provide management of heuristics to create new opportunities, as it is premised that the market offers many opportunities ready to be captured. Based on this analysis, the following question directs this thesis: What heuristics present at the creation of entrepreneurial opportunities? To answer this question, this thesis builds a conceptual framework from the literature and employs empirical research approach through the analysis of entrepreneurial activities linking perceptions, decisions and actions through multiple cases performed in eight startups studies. The main contribution of this thesis is to propose a typology of heuristics related to creating entrepreneurial opportunities, adapting the typology proposed by Bingham and Eisenhardt. While the typology of Bingham and Eisenhardt requires that companies learn heuristics types selection, procedure, priority and time, this thesis requires that companies also learn heuristics like \'creation\' and proposes a new typology of heuristics to create opportunities entrepreneurial: \'startups learn heuristics types creation, procedure, priority and time\', since they need to create an opportunity that the market does not yet have.

Made available in DSpace on 2014-06-12T15:58:14Z (GMT). No. of bitstreams: 2 arquivo3312_1.pdf: 1761748 bytes, checksum: f69f8cc401b77f11592d842023b76ada (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2011 / Jogos digitais exigem constante interação, no entanto desenvolvedores e designers de jogos devem estar muito atentos a questões de usabilidade, pois, um dos principais objetivos de um jogo digital é o entretenimento e o envolvimento do usuário para com o jogo, e isso pode envolver vários aspectos do design, como por exemplo, a história do jogo, a estimulação, o nível de desafio, a mecânica dos jogos entre outros aspectos. Para o desenvolvimento desse trabalho elaboramos um estudo de vários conceitos de jogos e os elementos que o compõem, assim como a descrição do processo de pesquisa de um método de avaliação de usabilidade para aplicação no primeiro protótipo funcional de um jogo digital. As heurísticas de design de jogos são listadas de acordo com pesquisas realizadas na literatura. Uma avaliação heurística representa um julgamento de valor sobre as qualidades ergonômicas das interfaces humano-computador, heurísticas são diretrizes que servem como um instrumento útil de avaliação, elas ajudam a identificar problemas especificos de jogos que podem ser facilmente despercebidos ou ignorados. Após todos os estudos da metodologia, sugerimos uma ferramenta chamada Avaliação Heuristica de Jogos Digitais que pode ser utilizada em todas as fases de desenvolvimento dos jogos

Submitted by Milenna Moraes Figueiredo (milennasjn@gmail.com) on 2016-03-21T18:27:37Z No. of bitstreams: 1 2013-03-CassiaBeckel.pdf: 3043262 bytes, checksum: b4d8ecc2f5cd3190b2764693ce30f76a (MD5) / Rejected by Angelica Conceição Dias Miranda (angelicacdm@gmail.com), reason: Alterar 160 p. para 160 f. (Utilizamos folhas páginas seriam para livros) Fazer correções na Citação: como está - BECKEL, Cássia Cris. Heurística construtiva para o empacotamento de elipses tangentes em um polígono de n lados. 2013. 160p. Dissertação (Mestrado em Modelagem Computacional) - Programa de Pós-Graduação em Modelagem Computacional. Universidade Federal do Rio Grande, Rio Grande, 2013. Como deve ser - BECKEL, Cássia Cris. Heurística construtiva para o empacotamento de elipses tangentes em um polígono de n lados. 2013. 160 f. Dissertação (Mestrado em Modelagem Computacional) - Centro de Ciências Computacionais, Universidade Federal do Rio Grande, Rio Grande, 2013. Atenciosamente Equipe Revisão RI. on 2016-04-26T19:46:13Z (GMT) / Submitted by Milenna Moraes Figueiredo (milennasjn@gmail.com) on 2016-04-26T21:09:45Z No. of bitstreams: 1 2013-03-CassiaBeckel.pdf: 3043262 bytes, checksum: b4d8ecc2f5cd3190b2764693ce30f76a (MD5) / Rejected by Gilmar Barros (gilmargomesdebarros@gmail.com), reason: - Não foi colocado o nome do co-orientador. - Não foi colocado “ponto final” na citação. on 2016-04-27T12:24:49Z (GMT) / Submitted by Milenna Moraes Figueiredo (milennasjn@gmail.com) on 2016-04-27T17:31:32Z No. of bitstreams: 1 2013-03-CassiaBeckel.pdf: 3043262 bytes, checksum: b4d8ecc2f5cd3190b2764693ce30f76a (MD5) / Approved for entry into archive by Gilmar Barros (gilmargomesdebarros@gmail.com) on 2016-04-27T17:55:18Z (GMT) No. of bitstreams: 1 2013-03-CassiaBeckel.pdf: 3043262 bytes, checksum: b4d8ecc2f5cd3190b2764693ce30f76a (MD5) / Made available in DSpace on 2016-04-27T17:55:18Z (GMT). No. of bitstreams: 1 2013-03-CassiaBeckel.pdf: 3043262 bytes, checksum: b4d8ecc2f5cd3190b2764693ce30f76a (MD5) Previous issue date: 2013 / Problemas de corte e empacotamento estão presentes em diversos setores da industria, e o estudo destes problemas propicia oportunidades de colaboração entre os setores acadêmicos e industrial, com vistas a que se obtenham benefícios para ambos, contribuindo para a sociedade como um todo. Entre os setores industriais nos quais surgem problemas de corte e empacotamento estão as industrias têxtil, automotiva, portuária, lapidaria, entre outras. O presente trabalho tem como objetivo elaborar uma metodologia analítica e computacional com a qual seja possível encontrar uma solução viável para o problema de empacotamento de elipses, sendo idênticas ou não, sem sobreposição e tangentes a cada vértice e quadrante de uma elipse inicial inscrita em um polígono irregular de n lados. A metodologia analítica e computacional desenvolvida visa obter a maximização da área total das elipses empacotadas e a minimização do tempo de processamento computacional. Destaca-se a aplicabilidade das transformações em R2 para obter as novas equações paramétricas das elipses com centro deslocado da origem e rotacionadas em relação ao sistema de eixos cartesianos original. A heurística que realiza a verificação da inscrição de cada elipse, baseia-se em uma modificação da função inpolygon do software Matlab [34], de maneira que garante o empacotamento total das elipses no polígono. Para validar a heurística construtiva utilizaram-se 7 polígonos e com os resultados obtidos em cada simulação foi possível encontrar a função exponencial, através de um ajuste de curva, que descreve o comportamento da simulação.

Orientador: Clovis Perin Filho / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Científica / Made available in DSpace on 2018-07-21T08:33:25Z (GMT). No. of bitstreams: 1 Scheidt_JoaoEduardoCardoso_M.pdf: 2581014 bytes, checksum: c1f985e905d424059b556edf8774af28 (MD5) Previous issue date: 1996 / Resumo: Túneis de congelamento são equipamentos utilizados pela industria alimentícia para o condicionamento térmico de produto tais como iogurte, sorvete, leite, carne e derivados. Assim, geralmente estão no fim do processo de produção de produtos altamente perecíveis. Quando um túnel representa m gargalo do processo, ele causa transtornos à produção que podem até interrompê-la. Este trabalho visa a abordagem do problema de operação eficiente e túneis de congelamento quanto ao aspecto de carregamento. Primeiramente abordamos o problema estático e suas relaxações e restrições. No problema estático determinístico, o instante de chegada das bandejas de produtos e o tempo de exposição necessário para seu condicionamento são conhecidos de antemão. Deve-se, então, programar por completo o carregamento do refrigerador definindo, para cada bandeja, em que nível do túnel deve ser colocada ou se deve ser rejeitada. Resultados teóricos são obtidos, particularmente para o caso (relaxado) do refrigerador de gavetas. Várias possibilidades de abordagem do problema estático são discutidas. Em seguida abordamos o problema dinâmico, onde não se dispõe do conhecimento prévio dos parâmetros de cada bandeja. Estes só ficam definidos a partir da chegada de cada bandeja, quando então a decisão quanto ao carregamento ou rejeição da bandeja deve ser tomada. Para o problema dinâmico são apresentadas várias políticas, que são testadas num caso real e em cenários hipotéticos nele baseados. Para avaliação de desempenho das políticas usamos limites' inferiores calculados com base no desenvolvimento teórico do problema estático. Os resultados são muito satisfatórios para uma classe de políticas a que chamamos de encadeamento. / Abstract: Freezing tunnels are food industry facilities for conditioning of meat, ice-cream, milk, yogurt, etc. They are very unwished botlenecks because they are positioned at the end of the production process of highly perishable items (low in-process inventory). The freezing tunnel loading problem is that of maximizing its production in terms of the amount of frozen trays of products. The purpose of this study is to model this problem and develop methods for solving its static and dynamic versions. In the static problem, the arrival time and the conditioning time of each tray are known in advance for the entire loading period. One should then completely schedule the loading of the tunnel. Each tray must be assigned to a position in the tunnel or be rejected. . We discuss several approaches and show some theoretical results for relaxed problems. In the dynamic problem, the arrival and the demand of trays are not known in advance. In this case, the decisions must take place at the arrival times. Several policies are developed. Some real case based scenarios are used for testing the policies. The study shows the potential gains with the application of some policies, mainly those ofthe class we named 'chain policies'. / Mestrado / Mestre em Matemática Aplicada