Cutting path as a rural postman problem

The Rural Postman Problem (RPP) is a particular Arc Routing Problem (ARP) which consists of determining a minimum cost circuit on a graph so that a given subset of required edges is traversed. The RPP is an NP-hard problem with significant real-life applications. This paper introduces an original approach based on Memetic Algorithms - the MARP algorithm - to solve the RPP and, also deals with an interesting Industrial Application, which focuses on the path optimization for component cutting operations. Memetic Algorithms are a class of Metaheuristics which may be seen as a population strategy that involves cooperation and competition processes between population elements and integrates “social knowledge”, using a local search procedure. The MARP algorithm is tested with different groups of instances and the results are compared with those gathered from other publications. MARP is also used in the context of various real-life applications.

Tutor Inteligente para o Ensino em Medicina

O objectivo deste trabalho consistiu no desenvolvimento de um protótipo que possibilita a adaptação do conteúdo disponibilizado de acordo com as características pessoais e psicológicas do aluno, aplicado no ensino da Medicina, nomeadamente na componente de Desenho de Estudos da disciplina de Introdução à Medicina. Para o protótipo desenvolvido foi definida uma arquitectura constituída por três componentes: um Modelo de Aluno que engloba as características pessoais e psicológicas do aluno, um Modelo de Domínio constituído por um grafo de conceitos e um Modelo Pedagógico formado pelas regras de adaptação e mecanismos de interação utilizados para obter uma solução adaptativa. Os diferentes componentes desenvolvidos para este protótipo permitem que este apresente as seguintes funcionalidades: Acesso ao conceito adequado, tendo em consideração o nível de conhecimento do aluno; Visualização de conte udos adequados ao estilo de aprendizagem do aluno; Adaptação do percurso do aluno de acordo com os resultados obtidos; Atualização das preferências de aprendizagem, com base no comportamento demonstrado pelo aluno na interação com o sistema. A primeira versão da ferramenta j a foi implementada. No entanto ainda será realizada a avaliação do protótipo em ambiente de aprendizagem, com a maior brevidade possível.

Heurísticas de pesquisa local para problemas de máquina única

O escalonamento é uma das decisões mais importantes no funcionamento de uma linha de produção. No âmbito desta dissertação foi realizada uma descrição do problema do escalonamento, identificando alguns métodos para a optimização dos problemas de escalonamento. Foi realizado um estudo ao caso do problema de máquina única através do teste de várias instâncias com o objectivo de minimizar o atraso pesado, aplicando uma Meta-Heurística baseada na Pesquisa Local e dois algoritmos baseados no SB. Os resultados obtidos reflectem que os algoritmos baseados no SB apresentaram resultados mais próximos do óptimo, em relação ao algoritmo baseado na PL. Os resultados obtidos permitem sustentar a hipótese de não existirem algoritmos específicos para os problemas de escalonamento. A melhor forma de encontrar uma solução de boa qualidade em tempo útil é experimentar diferentes algoritmos e comparar o desempenho das soluções obtidas.