Made available in DSpace on 2018-08-01T23:28:24Z (GMT). No. of bitstreams: 1 tese_11847_71 - GÉSSICA GONÇALVES MARTINS.pdf: 19034291 bytes, checksum: e6d9d519800deb1915abf5e9adcd6f16 (MD5) Previous issue date: 2018-03-02 / A Análise Combinatória tem sido considerada um tema difícil, tanto por alunos quan-to por professores de Matemática, apesar da resolução de uma significativa classe de problemas de contagem requerer apenas conhecimentos básicos, dentre os quais o Princípio Multiplicativo. Vimos então que a razão principal das dificuldades didáticas com esse tema está na confluência de dois fatores: (i) os problemas com-binatórios não admitem uma padronização que permita reduzir sua resolução à apli-cação de algoritmos simples e (ii) o modo de ensinar Matemática na Educação Bási-ca, que prioriza uma abordagem mecânica dos conteúdos. Corroborando esse en-tendimento, acreditamos que o ensino de Combinatória centralizado em definições e fórmulas, em detrimento do desenvolvimento do raciocínio estratégico, não favorece a aprendizagem e a capacidade de resolver problemas. Este é um estudo de campo exploratório-descritivo realizado ao longo dos anos 2016 e 2017 que, utilizando três instrumentos de coleta de dados (entrevista, questionário on-line e observação), pesquisou o tema com vinte professores de matemática das oito Escolas Estaduais de Ensino Médio de São Mateus/ES. Especificamente, buscamos analisar as repre-sentações dos professores relativas à Combinatória por meio dos pressupostos da História Cultural: representação, prática e apropriação, propostos por Roger Char-tier; estratégias e táticas, por Michel De Certeau; cultura escolar, por Dominique Ju-lia e disciplinas escolares, por André Chervel. Como resultado, constatamos que a maioria dos professores considera que a Análise Combinatória é um dos tópicos mais difíceis de ensinar no Ensino Médio e declara que o tema não foi devidamente estudado na sua formação inicial ou continuada. Além disso, para suprir essa carên-cia eles utilizam apenas o livro didático e a internet. Os professores pesquisados também não se apercebem da autonomia que possuem em meio às relações de es-tratégia e tática, no contexto escolar.

O Problema de Minimização do Número Máximo de Pilhas Abertas (MOSP, do inglês minimization of open stacks problem) é um problema de otimização combinatória da família NP-Difícil que vem recebendo grande atenção na literatura especializada. Este trabalho apresenta novas contribuições em termos de modelos e técnicas de resolução para o problema. A primeira parte deste trabalho lidou com modelos matemáticos, sendo analisados os modelos existentes que se baseiam em programação inteira mista. Variações de um modelo da literatura foram propostas, com o objetivo de tentar diminuir o tempo de execução necessário para se obter uma solução exata com a utilização de pacotes comerciais. Os resultados mostraram que as propostas são capazes de acelerar a solução de algumas classes de instâncias mas, que de maneira geral, métodos baseados em relaxação linear encontram dificuldade em provar a otimalidade devido à baixa qualidade dos limitantes inferiores. Uma outra contribuição deste trabalho foi o desenvolvimento de um modelo conjunto para o problema MOSP e para o problema de minimização da duração de pedidos (MORP, do inglês minimization of order spread problem). Este modelo propõe um framework unificado em que os dois problemas podem ser resolvidos ao mesmo tempo, tendo suas funções objetivo individuais ponderadas através de pesos definidos pelo usuário. A segunda parte do trabalho voltou-se para o desenvolvimento de métodos heurísticos para o MOSP. Duas estratégias de solução foram desenvolvidas. O primeiro método propõe uma transformação heurística entre o problema MOSP e o clássico problema do caixeiro viajente (TSP, do inglês traveling salesman problem). A partir de uma representação em grafo do MOSP, o TSP é definido por meio de uma regra de atribuição de distâncias baseadas nos graus dos nós. Nos testes computacionais, a estratégia proposta mostrou-se eficiente em relação às heurísticas específicas para o MOSP, obtendo a solução ótima do MOSP em 80,42% das instâncias testadas e sendo competitiva em termos de tempo computacional com algumas das melhores heurísticas da literatura. O segundo método heurístico proposto utilizou a ideia de decomposição. De fato, neste método, um corte no grafo associado ao problema original divide-o em problemas menores, que são resolvidos. A solução global é obtida através da junção das soluções dos subproblemas e, em alguns casos, é possível demonstrar a otimalidade da solução obtida. Testes computacionais indicam a validade da proposta e apontam caminhos para pesquisas futuras / The minimization of open stacks problem (MOSP) is a well known NP-hard combinatorial optimization problem that has been extensively discussed in the specialized literature. This study presents some new contributions in terms of models and solution methods for this problem. The first part of this thesis dealt with mathematical models. The existing mixedinteger models have been analyzed and variants of a well known model have been proposed, with the goal of reducing the time needed by commercial packages to obtain proved-optimal solutions. The results of computational tests on a widely used set of instances have indicated that the modifications proposed are able to reduce the time needed to obtain optimal solutions for some classes of instances. Nevertheless, a conclusion has been the fact that mixed-integer programming models have difficulty in obtaining convergence due to the low quality linear relaxation bounds. Another contribution of this thesis is the proposal of a single model that is able to deal with both the MOSP and with the Minimization of Order Spread Problem (MORP). This unified framework allows both problems to be jointly solved, by using a weighted objective function that included both original objectives. The second part of this thesis dealt with the development of heuristic strategies. Two solution strategies have been proposed. The first method proposes a heuristic conversion between MOSP and Traveling Salesman Problem (TSP) instances. This conversion relies the assignment distances to the TSP instance based on the degree of the vertices of the associated MOSP graph. Computational tests have shown that the proposed methodology is efficient, both in terms of solution quality (optimal solutions were obtained for 80.42% of the tested instances) and computational effort. The second method uses a decomposition idea. A cut is made in the graph associated with the original MOSP problem, yielding two smaller problems, which are solved. In some cases, the obtained combined solution can be prover optimal. Computational tests have shown the validity of the proposal and indicate new research opportunities

Tese de mestrado. Engenharia Electrotécnica e de Computadores. Faculdade de Engenharia. Universidade do Porto. 1990

Tese de doutoramento. Engenharia Electrotécnica e de Computadores. Faculdade de Engenharia. Universidade do Porto. 1995

Tese de doutoramento. Engenharia Electrotécnica e de Computadores. Faculdade de Engenharia. Universidade do Porto. 2007

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.

SILVA, Fernando Hugo Martins da. O uso de objetos de aprendizagem como instrumento diferenciado para o ensino de análise combinatória. 2013. 53 f. Dissertação (Mestrado em Matemática em Rede Nacional) – Centro de Ciências, Universidade Federal do Ceará, Fortaleza, 2013. / Submitted by Rocilda Sales (rocilda@ufc.br) on 2013-05-10T16:22:07Z No. of bitstreams: 1 2013_dis_fhmdasilva.pdf: 3033391 bytes, checksum: e23606b2d915b74d84d5694a1c9b6a0e (MD5) / Approved for entry into archive by Rocilda Sales(rocilda@ufc.br) on 2013-05-13T16:37:37Z (GMT) No. of bitstreams: 1 2013_dis_fhmdasilva.pdf: 3033391 bytes, checksum: e23606b2d915b74d84d5694a1c9b6a0e (MD5) / Made available in DSpace on 2013-05-13T16:37:37Z (GMT). No. of bitstreams: 1 2013_dis_fhmdasilva.pdf: 3033391 bytes, checksum: e23606b2d915b74d84d5694a1c9b6a0e (MD5) Previous issue date: 2013 / This paper shows the use of learning objects to the teaching of Combinatorial Analysis and how they can contribute to interactive way to the students learning. As such, the objective of this work is to verify if the use of learning objects in Mathematics classes promotes better assimilation of the combinatorial analysis. Therefore, we chose an experimental study in which 18 students participated at the 2nd year of Escola Estadual de Educação Professional (State School of Professional Education) Marta Maria Giffoni de Sousa, located in Acaraú, Ceará. These were chosen and divided randomly and equally into two groups (experimental and control). The instruments for data collection were: RIVED activities, socioeconomic questionnaire and test consisting of questions about permutation arrangement and combination. The data were analyzed using statistical programs, SPSS and Microsoft Excel. The results show to a superior performance of the group that was differentiated class (experimental) compared to the group that received traditional class (control). / Este estudo mostra a utilização de objetos de aprendizagem para o ensino de Análise Combinatória e como os mesmos podem contribuir de forma interativa para a aprendizagem dos alunos. Nessa medida, o objetivo deste trabalho é verificar se a utilização de objetos de aprendizagem nas aulas de Matemática favorece uma melhor assimilação dos conteúdos de análise combinatória. Para tanto, optou-se por um estudo experimental do qual participaram 18 alunos do 2º ano do Ensino Médio da Escola Estadual de Educação Profissional Marta Maria Giffoni de Sousa, situada em Acaraú, Ceará. Estes foram escolhidos e divididos aleatoriamente e igualmente em dois grupos (experimental e controle). Os instrumentos para coleta de dados foram: atividades do RIVED, questionário socioeconômico e teste composto de questões sobre permutação, arranjo e combinação. Os dados foram analisados através de um programa estatístico, o SPSS e Microsoft Excel. Os resultados apontam para um desempenho superior do grupo que obteve aula diferenciada (experimental) em relação ao grupo que recebeu aula tradicional (controle).

NUNES, Alemay Soares. As permutações caóticas, o problema de Lucas e a teoria dos permanentes . 2015. 77 f. Dissertação (Mestrado em Matemática em Rede Nacional) – Centro de Ciências, Universidade Federal do Ceará, Fortaleza, 2015. / Submitted by Erivan Almeida (eneiro@bol.com.br) on 2015-11-23T16:36:58Z No. of bitstreams: 1 2015_dis_asnunes.pdf: 1578418 bytes, checksum: f79764af9a15912c1a014a9a4a4b1b0b (MD5) / Approved for entry into archive by Rocilda Sales(rocilda@ufc.br) on 2015-11-23T16:59:42Z (GMT) No. of bitstreams: 1 2015_dis_asnunes.pdf: 1578418 bytes, checksum: f79764af9a15912c1a014a9a4a4b1b0b (MD5) / Made available in DSpace on 2015-11-23T16:59:42Z (GMT). No. of bitstreams: 1 2015_dis_asnunes.pdf: 1578418 bytes, checksum: f79764af9a15912c1a014a9a4a4b1b0b (MD5) Previous issue date: 2015 / In this work we cover some counting techniques used to solve some classic problems in Combinatorics. We also show a link between the so called “rencontre problem”, the “ménage problem” and the permanent of a square matrix. / Neste trabalho abordamos algumas técnicas de contagem utilizadas para solucionar alguns problemas clássicos da Análise Combinatória. Mostramos também uma relação entre o problema das cartas mal endereçadas, o problema de Lucas e os permanentes de uma matriz quadrada.

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.