Avaliação de usabilidade da interface de busca do portal da Câmara dos Deputados : um estudo de caso

A questão dessa monografia é responder se existem problemas de usabilidade na interface de busca do Portal da Câmara dos Deputados, quais são eles e como podem ser identificados. O trabalho resultou em um diagnóstico útil para aprimorar a usabilidade da interface, retratando sua situação e indicando possíveis soluções para os problemas encontrados. Os objetivos traçados foram: evidenciar a importância de que uma interface de busca atenda a princípios de usabilidade; descrever a técnica selecionada para a avaliação da interface; identificar os critérios necessários para a aplicação dessa técnica; avaliar a interface utilizando a técnica e os critérios propostos; e produzir um diagnóstico da interface. As motivações da escolha do objeto de pesquisa foram: o interesse profissional do pesquisador em relação a ele; e o fato de que a interface nunca havia sido submetida a esse tipo de avaliação. Foram levantados os conceitos tanto de interface, de forma geral, quanto de interface de busca, e afirmada a importância de fazer com que especialmente essa última permita ao usuário concentrar seus esforços na realização de suas tarefas. Os conceitos de usabilidade e ergonomia foram expostos, bem como o de avaliação heurística de usabilidade. Foram detalhadas as regras de ouro de Shneiderman adaptadas ao contexto de recuperação da informação, que serviram como heurísticas para a avaliação da interface. Ela foi feita por uma equipe de três especialistas, junto a um coordenador. Utilizou-se um conjunto de documentos para dar apoio a essa tarefa, provendo orientações aos avaliadores, auxiliando na coleta das descobertas, e permitindo a compilação dos resultados em um relatório final. Ao final do procedimento de avaliação, chegou-se a uma lista de problemas relacionados à usabilidade da interface, classificados por grau de severidade, e associados às soluções para eles propostas. Com base nessa lista foi feito o diagnóstico da interface. Por fim, o estudo afirma que a técnica escolhida mostrou-se adequada para o que se esperava, e fala da importância da realização sistemática de avaliações de usabilidade.

Algoritmos meméticos en problemas de investigación operativa

En este artículo se plantea la resolución de un problema de Investigación Operativa utilizando PHPSimplex (herramienta online de resolución de problemas de optimización utilizando el método Simplex), Solver de Microsoft Excel y un prototipo híbrido que combina las teorías de los Algoritmos Genéticos con una técnica heurística de búsqueda local. La hibridación de estas dos técnicas es conocida como Algoritmo Memético. Este prototipo será capaz de resolver problemas de Optimización con función de maximización o minimización conocida, superando las restricciones que se planteen. Los tres métodos conseguirán buenos resultados ante problemas sencillos de Investigación Operativa, sin embargo, se propone otro problema en el cual el Algoritmo Memético y la herramienta Solver de Microsoft Excel, alcanzarán la solución óptima. La resolución del problema utilizando PHPSimplex resultará inviable. El objetivo, además de resolver el problema propuesto, es comparar cómo se comportan los tres métodos anteriormente citados ante el problema y cómo afrontan las dificultades que éste presenta. Además, este artículo pretende dar a conocer diferentes técnicas de apoyo a la toma de decisiones, con la intención de que se utilicen cada vez más en el entorno empresarial sustentando, de esta manera, las decisiones mediante la matemática o la Inteligencia Artificial y no basándose únicamente en la experiencia.

Proposição e análise de modelos híbridos para o problema de escalonamento de produção em oficina de máquinas

Nas últimas décadas, o problema de escalonamento da produção em oficina de máquinas, na literatura referido como JSSP (do inglês Job Shop Scheduling Problem), tem recebido grande destaque por parte de pesquisadores do mundo inteiro. Uma das razões que justificam tamanho interesse está em sua alta complexidade. O JSSP é um problema de análise combinatória classificado como NP-Difícil e, apesar de existir uma grande variedade de métodos e heurísticas que são capazes de resolvê-lo, ainda não existe hoje nenhum método ou heurística capaz de encontrar soluções ótimas para todos os problemas testes apresentados na literatura. A outra razão basea-se no fato de que esse problema encontra-se presente no diaa- dia das indústrias de transformação de vários segmento e, uma vez que a otimização do escalonamento pode gerar uma redução significativa no tempo de produção e, consequentemente, um melhor aproveitamento dos recursos de produção, ele pode gerar um forte impacto no lucro dessas indústrias, principalmente nos casos em que o setor de produção é responsável por grande parte dos seus custos totais. Entre as heurísticas que podem ser aplicadas à solução deste problema, o Busca Tabu e o Multidão de Partículas apresentam uma boa performance para a maioria dos problemas testes encontrados na literatura. Geralmente, a heurística Busca Tabu apresenta uma boa e rápida convergência para pontos ótimos ou subótimos, contudo esta convergência é frequentemente interrompida por processos cíclicos e a performance do método depende fortemente da solução inicial e do ajuste de seus parâmetros. A heurística Multidão de Partículas tende a convergir para pontos ótimos, ao custo de um grande esforço computacional, sendo que sua performance também apresenta uma grande sensibilidade ao ajuste de seus parâmetros. Como as diferentes heurísticas aplicadas ao problema apresentam pontos positivos e negativos, atualmente alguns pesquisadores começam a concentrar seus esforços na hibridização das heurísticas existentes no intuito de gerar novas heurísticas híbridas que reúnam as qualidades de suas heurísticas de base, buscando desta forma diminuir ou mesmo eliminar seus aspectos negativos. Neste trabalho, em um primeiro momento, são apresentados três modelos de hibridização baseados no esquema geral das Heurísticas de Busca Local, os quais são testados com as heurísticas Busca Tabu e Multidão de Partículas. Posteriormente é apresentada uma adaptação do método Colisão de Partículas, originalmente desenvolvido para problemas contínuos, onde o método Busca Tabu é utilizado como operador de exploração local e operadores de mutação são utilizados para perturbação da solução. Como resultado, este trabalho mostra que, no caso dos modelos híbridos, a natureza complementar e diferente dos métodos Busca Tabu e Multidão de Partículas, na forma como são aqui apresentados, da origem à algoritmos robustos capazes de gerar solução ótimas ou muito boas e muito menos sensíveis ao ajuste dos parâmetros de cada um dos métodos de origem. No caso do método Colisão de Partículas, o novo algorítimo é capaz de atenuar a sensibilidade ao ajuste dos parâmetros e de evitar os processos cíclicos do método Busca Tabu, produzindo assim melhores resultados.

Solução de problemas inversos de transferência radiativa em meios heterogêneos unidimensionais e uma e duas camadas utilizando o algoritmo dos vagalumes

Esta tese apresenta um estudo sobre modelagem computacional onde são aplicadas meta-heurísticas de otimização na solução de problemas inversos de transferência radiativa em meios unidimensionais com albedo dependente da variável óptica, e meios unidimensionais de duas camadas onde o problema inverso é tratado como um problema de otimização. O trabalho aplica uma meta-heurística baseada em comportamentos da natureza conhecida como algoritmo dos vagalumes. Inicialmente, foram feitos estudos comparativos de desempenho com dois outros algoritmos estocásticos clássicos. Os resultados encontrados indicaram que a escolha do algoritmo dos vagalumes era apropriada. Em seguida, foram propostas outras estratégias que foram inseridas no algoritmo dos vagalumes canônico. Foi proposto um caso onde se testou e investigou todas as potenciais estratégias. As que apresentaram os melhores resultados foram, então, testadas em mais dois casos distintos. Todos os três casos testados foram em um ambiente de uma camada, com albedo de espalhamento dependente da posição espacial. As estratégias que apresentaram os resultados mais competitivos foram testadas em um meio de duas camadas. Para este novo cenário foram propostos cinco novos casos de testes. Os resultados obtidos, pelas novas variantes do algoritmo dos vagalumes, foram criticamente analisados.

Roteamento e alocação de comprimento de onda em redes WDM segundo algoritmo baseado em regras da natureza.

O surgimento de novos serviços de telecomunicações tem provocado um enorme aumento no tráfego de dados nas redes de transmissão. Para atender a essa demanda crescente, novas tecnologias foram desenvolvidas e implementadas ao longo dos anos, sendo que um dos principais avanços está na área de transmissão óptica, devido à grande capacidade de transporte de informação da fibra óptica. A tecnologia que melhor explora a capacidade desse meio de transmissão atualmente é a multiplexação por divisão de comprimento de onda ou Wavelength Division Multiplexing (WDM) que permite a transmissão de diversos sinais utilizando apenas uma fibra óptica. Redes ópticas WDM se tornaram muito complexas, com enorme capacidade de transmissão de informação (terabits por segundo), para atender à explosão de necessidade por largura de banda. Nesse contexto, é de extrema importância que os recursos dessas redes sejam utilizados de forma inteligente e otimizada. Um dos maiores desafios em uma rede óptica é a escolha de uma rota e a seleção de um comprimento de onda disponível na rede para atender uma solicitação de conexão utilizando o menor número de recursos possível. Esse problema é bastante complexo e ficou conhecido como problema de roteamento e alocação de comprimento de onda ou, simplesmente, problema RWA (Routing and Wavelentgh Assignment problem). Muitos estudos foram realizados com o objetivo de encontrar uma solução eficiente para esse problema, mas nem sempre é possível aliar bom desempenho com baixo tempo de execução, requisito fundamental em redes de telecomunicações. A técnica de algoritmo genético (AG) tem sido utilizada para encontrar soluções de problemas de otimização, como é o caso do problema RWA, e tem obtido resultados superiores quando comparada com soluções heurísticas tradicionais encontradas na literatura. Esta dissertação apresenta, resumidamente, os conceitos de redes ópticas e de algoritmos genéticos, e descreve uma formulação do problema RWA adequada à solução por algoritmo genético.

Síntese evolucionária de circuitos sequenciais inspirada nos princípios da computação quântica.

Esta dissertação investiga a aplicação dos algoritmos evolucionários inspirados na computação quântica na síntese de circuitos sequenciais. Os sistemas digitais sequenciais representam uma classe de circuitos que é capaz de executar operações em uma determinada sequência. Nos circuitos sequenciais, os valores dos sinais de saída dependem não só dos valores dos sinais de entrada como também do estado atual do sistema. Os requisitos cada vez mais exigentes quanto à funcionalidade e ao desempenho dos sistemas digitais exigem projetos cada vez mais eficientes. O projeto destes circuitos, quando executado de forma manual, se tornou demorado e, com isso, a importância das ferramentas para a síntese automática de circuitos cresceu rapidamente. Estas ferramentas conhecidas como ECAD (Electronic Computer-Aided Design) são programas de computador normalmente baseados em heurísticas. Recentemente, os algoritmos evolucionários também começaram a ser utilizados como base para as ferramentas ECAD. Estas aplicações são referenciadas na literatura como eletrônica evolucionária. Os algoritmos mais comumente utilizados na eletrônica evolucionária são os algoritmos genéticos e a programação genética. Este trabalho apresenta um estudo da aplicação dos algoritmos evolucionários inspirados na computação quântica como uma ferramenta para a síntese automática de circuitos sequenciais. Esta classe de algoritmos utiliza os princípios da computação quântica para melhorar o desempenho dos algoritmos evolucionários. Tradicionalmente, o projeto dos circuitos sequenciais é dividido em cinco etapas principais: (i) Especificação da máquina de estados; (ii) Redução de estados; (iii) Atribuição de estados; (iv) Síntese da lógica de controle e (v) Implementação da máquina de estados. O Algoritmo Evolucionário Inspirado na Computação Quântica (AEICQ) proposto neste trabalho é utilizado na etapa de atribuição de estados. A escolha de uma atribuição de estados ótima é tratada na literatura como um problema ainda sem solução. A atribuição de estados escolhida para uma determinada máquina de estados tem um impacto direto na complexidade da sua lógica de controle. Os resultados mostram que as atribuições de estados obtidas pelo AEICQ de fato conduzem à implementação de circuitos de menor complexidade quando comparados com os circuitos gerados a partir de atribuições obtidas por outros métodos. O AEICQ e utilizado também na etapa de síntese da lógica de controle das máquinas de estados. Os circuitos evoluídos pelo AEICQ são otimizados segundo a área ocupada e o atraso de propagação. Estes circuitos são compatíveis com os circuitos obtidos por outros métodos e em alguns casos até mesmo superior em termos de área e de desempenho, sugerindo que existe um potencial de aplicação desta classe de algoritmos no projeto de circuitos eletrônicos.

La enseñanza de la probabilidad condicional

La teoría de la probabilidad es una rama importante dentro del desarrollo del pensamiento aleatorio, y en general, de la educación matemática, pues promueve el uso de heurísticas para realizar predicciones y tomar decisiones en torno a una situación del diario vivir. Si bien, en los lineamientos curriculares y en los estándares básicos de calidad se citan conceptos y temáticas en relación con la probabilidad que deben ser abordadas en las aulas de clase, las formas usuales de enseñanza ponen en evidencia el énfasis determinista que recae en la cultura escolar.

Currículum oficial de matemáticas y cultura de racionalidad

En la ponencia se analiza un material curricular oficial para las matemáticas de la educación secundaria, a la luz de los componentes de la noción de ‘Cultura de Racionalidad’: Creencias, Normas de Sustentación, Normas Heurísticas, y Normas sobre Reparto de Responsabilidades (entre otros aspectos). Se argumenta que el enfoque didáctico del currículum analizado, centrado en un enfoque hacia el descubrimiento –basado en procesos empíricos e inductivos–, va a ‘contraflujo’ en relación a otras propuestas curriculares internacionales (como las de Estados Unidos e Inglaterra), lo cual debe de alertar no sólo a las autoridades responsables del desarrollo curricular sino a todos los implicados con la educación matemática del país.

Análisis de los conocimientos probabilísticos del profesorado de educación primaria

Algunos profesores presentan dificultades para enseñar probabilidad, sobre todo en países en los que la incorporación de esta materia en el currículo es reciente y la preparación durante la formación inicial es escasa, como es el caso de Chile. Para diseñar programas de intervención que den lugar a una enseñanza idónea, se realiza un estudio exploratorio sobre el conocimiento didáctico-matemático para enseñar probabilidad, fundamentado en el modelo del Conocimiento Didáctico-Matemático (CDM). Con este propósito se ha administrado el Cuestionario CDM-Probabilidad a 93 profesores, cuyos resultados han puesto de manifiesto varios errores y dificultades, evidenciando la presencia de heurísticas y sesgos probabilísticos. Se concluye que es necesaria una mayor especialización del profesorado en todas las facetas de su conocimiento didáctico-matemático: conocimiento común del contenido, conocimiento ampliado del contenido y conocimiento especializado.

Perfil de ensino do professor de ciências: concetualização e validação

As ciências são um elemento central da cultura contemporânea pelo que a educação científica tem de ser vista como um direito essencial dos cidadãos. A qualidade do ensino das ciências na escola torna-se, portanto, um especial foco de interesse, científico, político e social, ao nível local, nacional, e global. A investigação em educação em ciências tem produzido conhecimentos que permitem compreender os problemas e fundamentar decisões conducentes a um ensino de ciências ajustado aos desafios atuais. Por outro lado, várias organizações internacionais (UE, OCDE e UNESCO) também têm produzido documentos que visam regular as políticas globais de ensino de ciências, assumindo que a educação científica dos cidadãos é uma condição para a prosperidade económica e social de qualquer estado. Assim, atualmente, existe um acervo documental extenso e diverso relativo ao ensino de ciências, pelo que se impõe um exercício de análise e síntese que identifique quais as orientações-chave que devem ser consideradas. O ensino de nível secundário (ISCE2 e ISCE3), sendo uma etapa em que os jovens fazem escolhas pessoais e vocacionais importantes, merece particular atenção, pois diversos estudos revelam que regista níveis preocupantes de abandono e de desinteresse pelas áreas científicas e tecnológicas. Sendo as práticas dos professores um dos principais fatores de inovação e mudança importa sistematizar os conhecimentos científicos que explicam a sua complexidade e podem orientar a promoção da sua qualidade. O estudo que se apresenta situa-se na confluência de todos estes interesses e visou duas finalidades: delimitar um conceito unificador que permita estudar e desenvolver a qualidade das práticas dos professores de ciências de nível secundário; desenvolver um instrumento de inquérito que operacionalize esse conceito, numa perspetiva de investigação, formação e supervisão de práticas de ensino de ciências. O plano da investigação decorreu em duas fases. Na fase I foi delimitado o conceito perfil de ensino do professor de ciências (PEPC); este estrutura-se em três dimensões – didática, epistemológica e psicológica – cujos referenciais teórico-empíricos decorreram de revisão sistemática de literatura e de abordagem empírica de natureza exploratória e qualitativa, baseada em entrevistas a professores de ciências. Na fase II foi construído e validado o questionário do perfil de ensino do professor de ciências (QPEPC); este contém itens empiricamente situados, construídos a partir do discurso dos professores entrevistados na fase I e seguidamente validados. A validação de QPEPC envolveu dois processos de inquérito por questionário e uma metodologia mista de investigação (análise de conteúdo e análise estatística de dados): a primeira validação contou com um painel internacional de 12 especialistas em didática de ciências; a segunda validação envolveu 184 professores de ciências portugueses. Concluindo-se que QPEPC avalia duas dimensões de PEPC, construíram-se índices e modelos gráficos para facilitar a interpretação dos dados recolhidos. Analisaram-se limitações e potencialidades heurísticas de PEPC e QPEPC, enquanto produtos da investigação, perspetivando o seu uso em contextos diversos, nomeadamente futuras investigações e cenários de formação, reflexão e supervisão de professores de ciências.

Optimization models for a short sea fuel oil distribution problem

O transporte marítimo e o principal meio de transporte de mercadorias em todo o mundo. Combustíveis e produtos petrolíferos representam grande parte das mercadorias transportadas por via marítima. Sendo Cabo Verde um arquipelago o transporte por mar desempenha um papel de grande relevância na economia do país. Consideramos o problema da distribuicao de combustíveis em Cabo Verde, onde uma companhia e responsavel por coordenar a distribuicao de produtos petrolíferos com a gestão dos respetivos níveis armazenados em cada porto, de modo a satisfazer a procura dos varios produtos. O objetivo consiste em determinar políticas de distribuicão de combustíveis que minimizam o custo total de distribuiçao (transporte e operacões) enquanto os n íveis de armazenamento sao mantidos nos n íveis desejados. Por conveniencia, de acordo com o planeamento temporal, o prob¬lema e divido em dois sub-problemas interligados. Um de curto prazo e outro de medio prazo. Para o problema de curto prazo sao discutidos modelos matemáticos de programacao inteira mista, que consideram simultaneamente uma medicao temporal cont ínua e uma discreta de modo a modelar multiplas janelas temporais e taxas de consumo que variam diariamente. Os modelos sao fortalecidos com a inclusão de desigualdades validas. O problema e então resolvido usando um "software" comercial. Para o problema de medio prazo sao inicialmente discutidos e comparados varios modelos de programacao inteira mista para um horizonte temporal curto assumindo agora uma taxa de consumo constante, e sao introduzidas novas desigualdades validas. Com base no modelo escolhido sao compara¬das estrategias heurísticas que combinam três heur ísticas bem conhecidas: "Rolling Horizon", "Feasibility Pump" e "Local Branching", de modo a gerar boas soluçoes admissíveis para planeamentos com horizontes temporais de varios meses. Finalmente, de modo a lidar com situaçoes imprevistas, mas impor¬tantes no transporte marítimo, como as mas condicões meteorológicas e congestionamento dos portos, apresentamos um modelo estocastico para um problema de curto prazo, onde os tempos de viagens e os tempos de espera nos portos sao aleatórios. O problema e formulado como um modelo em duas etapas, onde na primeira etapa sao tomadas as decisões relativas as rotas do navio e quantidades a carregar e descarregar e na segunda etapa (designada por sub-problema) sao consideradas as decisoes (com recurso) relativas ao escalonamento das operacões. O problema e resolvido por um metodo de decomposto que usa um algoritmo eficiente para separar as desigualdades violadas no sub-problema.

A educação intercultural na formação contínua de professores de línguas

Situado entre o discurso investigativo e o profissional da Didática de Línguas, o presente estudo assenta: num entendimento da educação em línguas como um processo valorizador da diversidade linguística e cultural, tendo como fim último a promoção da intercompreensão e do diálogo intercultural, dentro dos pressupostos de uma didática das línguas e do plurilinguismo; na conceção do professor de línguas como um dos principais atores na educação de cidadãos / comunicadores interculturais, vendo-se, portanto, a braços com novas exigências, para as quais, muitas vezes, não se sente preparado; e nos pressupostos de que a identidade profissional condiciona fortemente a forma como o professor desempenha a sua ação didática, sendo este processo de se tornar professor contínuo e dependente, quer do sujeito-professor e dos seus percursos profissionais e formativos, quer do contexto (profissional, local, nacional, global) em que este se insere. Pretende-se, com este estudo, contribuir para que a educação intercultural seja uma realidade nas nossas escolas, potenciando a sua migração contextualizada dos documentos orientadores das políticas linguísticas e educativas nacionais e transnacionais e dos discursos da investigação em Didática de Línguas. Para o efeito, desenvolvemos um programa de investigação/formação denominado O Professor Intercultural, durante o ano letivo 2006/2007, com professores de línguas (materna e estrangeiras) de três escolas básicas e secundárias do distrito de Aveiro. Este programa integrava um curso (25 horas) e uma oficina (50 horas), ambas as ações de formação acreditadas pelo Conselho Científico-Pedagógico da Formação Contínua. Do ponto de vista formativo, com este programa pretendíamos levar as professoras em formação a desenvolver competências pessoais e profissionais que lhes permitissem gerir a diversidade nos seus contextos profissionais, tendo em vista o desenvolvimento nos seus alunos de uma competência de comunicação intercultural (CCI). Do ponto de vista investigativo, não só pretendíamos compreender as representações dos sujeitos relativamente à educação intercultural em geral e à CCI em particular; como também identificar princípios e estratégias de formação potenciadores do desenvolvimento de competências profissionais docentes para trabalhar a CCI, a partir das perspetivas dos próprios sujeitos. Trata-se, portanto, de um estudo de caso de cariz qualitativo e interpretativo / fenomenológico, com potencialidades heurísticas, que pretende evidenciar os sujeitos, as suas representações, as interações consigo e com os outros e a forma como conceptualizam a identidade profissional docente e as suas dinâmicas de desenvolvimento. Como instrumentos de recolha de dados, privilegiámos os Portefólios Profissionais que foram sendo construídos ao longo do percurso de formação; a sessão “Entre Línguas e Culturas” da plataforma Galanet (www.galanet.eu), recurso de formação no âmbito da oficina (entre fevereiro e maio de 2007); o “Diário do Investigador”; e as “entrevistas narrativas e de confrontação” efetuadas sensivelmente um ano após o final do programa de investigação/formação. Os resultados da análise de conteúdo revelam que os sujeitos consideram a CCI uma competência multidimensional e complexa, reconhecendo três componentes: afetiva (domínio do saber ser e saber viver com o outro), cognitiva (domínio do saber) e praxeológica (domínio do saber-fazer). A componente afetiva constitui, de acordo com os resultados, o motor de arranque do desenvolvimento desta competência, que, posteriormente, é alargada em dinâmicas de informação-(inter)ação-reflexão. Por outro lado, dada a grande pertinência que atribuem à abordagem intercultural e à urgência com que veem a sua integração escolar, os sujeitos consideram a CCI uma das competências inerentes à competência profissional docente, elemento integrador da identidade profissional, numa forte ligação com a missão ética e política que cada vez mais é associada ao docente (de línguas). Para além disso, percecionam o seu desenvolvimento profissional docente como um processo que os acompanha ao longo da vida, fruto das idiossincrasias e predisposições do próprio indivíduo, mas também das dinâmicas da sua formação, das caraterísticas dos contextos em que se movimenta e da colaboração com o Outro, no seu espaço profissional ou fora dele. Importa salientar que este desenvolvimento profissional é potenciado, segundo os nossos resultados, por propostas de formação assentes numa abordagem acional e reflexiva, articulando dinâmicas investigação-ação-reflexão como as propostas no nosso programa de formação, nomeadamente no âmbito da oficina. Neste quadro, concluímos o presente estudo, indicando alguns caminhos possíveis para a formação de professores de línguas para a educação intercultural.

Network virtualisation from an operator perspective

Network virtualisation is seen as a promising approach to overcome the so-called “Internet impasse” and bring innovation back into the Internet, by allowing easier migration towards novel networking approaches as well as the coexistence of complementary network architectures on a shared infrastructure in a commercial context. Recently, the interest from the operators and mainstream industry in network virtualisation has grown quite significantly, as the potential benefits of virtualisation became clearer, both from an economical and an operational point of view. In the beginning, the concept has been mainly a research topic and has been materialized in small-scale testbeds and research network environments. This PhD Thesis aims to provide the network operator with a set of mechanisms and algorithms capable of managing and controlling virtual networks. To this end, we propose a framework that aims to allocate, monitor and control virtual resources in a centralized and efficient manner. In order to analyse the performance of the framework, we performed the implementation and evaluation on a small-scale testbed. To enable the operator to make an efficient allocation, in real-time, and on-demand, of virtual networks onto the substrate network, it is proposed a heuristic algorithm to perform the virtual network mapping. For the network operator to obtain the highest profit of the physical network, it is also proposed a mathematical formulation that aims to maximize the number of allocated virtual networks onto the physical network. Since the power consumption of the physical network is very significant in the operating costs, it is important to make the allocation of virtual networks in fewer physical resources and onto physical resources already active. To address this challenge, we propose a mathematical formulation that aims to minimize the energy consumption of the physical network without affecting the efficiency of the allocation of virtual networks. To minimize fragmentation of the physical network while increasing the revenue of the operator, it is extended the initial formulation to contemplate the re-optimization of previously mapped virtual networks, so that the operator has a better use of its physical infrastructure. It is also necessary to address the migration of virtual networks, either for reasons of load balancing or for reasons of imminent failure of physical resources, without affecting the proper functioning of the virtual network. To this end, we propose a method based on cloning techniques to perform the migration of virtual networks across the physical infrastructure, transparently, and without affecting the virtual network. In order to assess the resilience of virtual networks to physical network failures, while obtaining the optimal solution for the migration of virtual networks in case of imminent failure of physical resources, the mathematical formulation is extended to minimize the number of nodes migrated and the relocation of virtual links. In comparison with our optimization proposals, we found out that existing heuristics for mapping virtual networks have a poor performance. We also found that it is possible to minimize the energy consumption without penalizing the efficient allocation. By applying the re-optimization on the virtual networks, it has been shown that it is possible to obtain more free resources as well as having the physical resources better balanced. Finally, it was shown that virtual networks are quite resilient to failures on the physical network.

O problema da árvore de suporte de custo mínimo com restrições de peso

Nesta tese abordam-se várias formulações e diferentes métodos para resolver o Problema da Árvore de Suporte de Custo Mínimo com Restrições de Peso (WMST – Weight-constrained Minimum Spanning Tree Problem). Este problema, com aplicações no desenho de redes de comunicações e telecomunicações, é um problema de Otimização Combinatória NP-difícil. O Problema WMST consiste em determinar, numa rede com custos e pesos associados às arestas, uma árvore de suporte de custo mínimo de tal forma que o seu peso total não exceda um dado limite especificado. Apresentam-se e comparam-se várias formulações para o problema. Uma delas é usada para desenvolver um procedimento com introdução de cortes baseado em separação e que se tornou bastante útil na obtenção de soluções para o problema. Tendo como propósito fortalecer as formulações apresentadas, introduzem-se novas classes de desigualdades válidas que foram adaptadas das conhecidas desigualdades de cobertura, desigualdades de cobertura estendida e desigualdades de cobertura levantada. As novas desigualdades incorporam a informação de dois conjuntos de soluções: o conjunto das árvores de suporte e o conjunto saco-mochila. Apresentam-se diversos algoritmos heurísticos de separação que nos permitem usar as desigualdades válidas propostas de forma eficiente. Com base na decomposição Lagrangeana, apresentam-se e comparam-se algoritmos simples, mas eficientes, que podem ser usados para calcular limites inferiores e superiores para o valor ótimo do WMST. Entre eles encontram-se dois novos algoritmos: um baseado na convexidade da função Lagrangeana e outro que faz uso da inclusão de desigualdades válidas. Com o objetivo de obter soluções aproximadas para o Problema WMST usam-se métodos heurísticos para encontrar uma solução inteira admissível. Os métodos heurísticos apresentados são baseados nas estratégias Feasibility Pump e Local Branching. Apresentam-se resultados computacionais usando todos os métodos apresentados. Os resultados mostram que os diferentes métodos apresentados são bastante eficientes para encontrar soluções para o Problema WMST.