Task partitioning and priority assignment for distributed hard real-time systems

In this paper, we propose the Distributed using Optimal Priority Assignment (DOPA) heuristic that finds a feasible partitioning and priority assignment for distributed applications based on the linear transactional model. DOPA partitions the tasks and messages in the distributed system, and makes use of the Optimal Priority Assignment (OPA) algorithm known as Audsley’s algorithm, to find the priorities for that partition. The experimental results show how the use of the OPA algorithm increases in average the number of schedulable tasks and messages in a distributed system when compared to the use of Deadline Monotonic (DM) usually favoured in other works. Afterwards, we extend these results to the assignment of Parallel/Distributed applications and present a second heuristic named Parallel-DOPA (P-DOPA). In that case, we show how the partitioning process can be simplified by using the Distributed Stretch Transformation (DST), a parallel transaction transformation algorithm introduced in [1].

Scalable and Efficient Configuration of TimeDivision Multiplexed Resources

Consumer-electronics systems are becoming increasingly complex as the number of integrated applications is growing. Some of these applications have real-time requirements, while other non-real-time applications only require good average performance. For cost-efficient design, contemporary platforms feature an increasing number of cores that share resources, such as memories and interconnects. However, resource sharing causes contention that must be resolved by a resource arbiter, such as Time-Division Multiplexing. A key challenge is to configure this arbiter to satisfy the bandwidth and latency requirements of the real-time applications, while maximizing the slack capacity to improve performance of their non-real-time counterparts. As this configuration problem is NP-hard, a sophisticated automated configuration method is required to avoid negatively impacting design time. The main contributions of this article are: 1) An optimal approach that takes an existing integer linear programming (ILP) model addressing the problem and wraps it in a branch-and-price framework to improve scalability. 2) A faster heuristic algorithm that typically provides near-optimal solutions. 3) An experimental evaluation that quantitatively compares the branch-and-price approach to the previously formulated ILP model and the proposed heuristic. 4) A case study of an HD video and graphics processing system that demonstrates the practical applicability of the approach.

Análise do Desempenho de Técnicas de Otimização no Problema de Escalonamento

A optimização nas aplicações modernas assume um carácter fortemente interdisciplinar, relacionando-se com a necessidade de integração de diferentes técnicas e paradigmas na resolução de problemas reais complexos. O problema do escalonamento é recorrente no planeamento da produção. Sempre que uma ordem de fabrico é lançada, é necessário determinar que recursos serão utilizados e em que sequência as atividades serão executadas, para otimizar uma dada medida de desempenho. Embora ainda existam empresas a abordar o problema do escalonamento através de simples heurísticas, a proposta de sistemas de escalonamento tem-se evidenciado na literatura. Pretende-se nesta dissertação, a realização da análise de desempenho de Técnicas de Optimização, nomeadamente as meta-heurísticas, na resolução de problemas de optimização complexos – escalonamento de tarefas, particularmente no problema de minimização dos atrasos ponderados, 1||ΣwjTj. Assim sendo, foi desenvolvido um protótipo que serviu de suporte ao estudo computacional, com vista à avaliação do desempenho do Simulated Annealing (SA) e o Discrete Artificial Bee Colony (DABC). A resolução eficiente de um problema requer, em geral, a aplicação de diferentes métodos, e a afinação dos respetivos parâmetros. A afinação dos parâmetros pode permitir uma maior flexibilidade e robustez mas requer uma inicialização cuidadosa. Os parâmetros podem ter uma grande influência na eficiência e eficácia da pesquisa. A sua definição deve resultar de um cuidadoso esforço experimental no sentido da respectiva especificação. Foi usado, no âmbito deste trabalho de mestrado, para suportar a fase de parametrização das meta-heurísticas em análise, o planeamento de experiências de Taguchi. Da análise dos resultados, foi possível concluir que existem vantagem estatisticamente significativa no desempenho do DABC, mas quando analisada a eficiência é possível concluir que há vantagem do SA, que necessita de menos tempo computacional.

Desenvolvimento de sequenciador para um Problema de Roteamento de Veículos

Este projecto tem como objectivo a optimização das rotas dos técnicos de serviço após venda da Schmitt+Sohn Elevadores, associadas à realização das manutenções preventivas a cada elemento contratado à empresa (elevadores, escadas rolantes, etc). Como tal, é necessário fazer uma distribuição dos equipamentos que se encontram em carteira, por um dos técnicos que assegura a manutenção, pelos vários dias úteis de cada mês, e pelas horas de trabalho de cada dia. Apesar do técnico ter disponíveis, por dia, 8h de trabalho, apenas 6h podem ser preenchidas com manutenções preventivas. As 2h restantes são essencialmente para possíveis manutenções correctivas para as quais o técnico seja solicitado. Caso o técnico não seja contactado para resolver nenhuma avaria, essas horas podem ser utilizadas pelo mesmo para adiantar trabalho do dia seguinte, isto é, visitar já alguns dos próximos pontos de manutenção preventiva do dia seguinte, ou para compensar trabalho que esteja atrasado. De salientar que, para cada dia, as deslocações do técnico de qualquer local ao primeiro ponto de uma rota ou de regresso do último ponto de uma rota não são contabilizadas. O trabalho desenvolvido nesta dissertação pretende dar resposta ao problema apresentado pela Schmitt+Sohn Elevadores. Para isso foi desenvolvida uma heurística para a optimização das rotas dos técnicos. Esta é baseada no conceito de “vizinho mais próximo” que procura sempre o ponto que se apresenta mais perto do último ponto que foi adicionado à rota. Com base nesta metodologia, nos processos de escolha dos pontos que formam clusters, e na selecção dos pontos iniciais de cada uma das rotas diárias, a ferramenta de optimização resultante define as rotas diárias para que o percurso efectuado por cada técnico num mês seja o menor possível. São feitas alterações às rotas definidas inicialmente quando encontrados pontos de uma mesma entrada a serem visitados em dias diferentes. Isto obrigaria o técnico a fazer duas viagens ao mesmo local. Por fim, o resultado é apresentado num documento Word a ser utilizado pelo técnico como guia diário das suas deslocações aos equipamentos que necessitam de verificações periódicas. Os resultados obtidos foram comparados com as rotas que estavam a ser usadas pela empresa, tendo apresentado resultados de melhor qualidade, constatando-se a eficiência da solução criada pelo algoritmo proposto neste trabalho.

Matrix fractional systems

This paper addresses the matrix representation of dynamical systems in the perspective of fractional calculus. Fractional elements and fractional systems are interpreted under the light of the classical Cole–Cole, Davidson–Cole, and Havriliak–Negami heuristic models. Numerical simulations for an electrical circuit enlighten the results for matrix based models and high fractional orders. The conclusions clarify the distinction between fractional elements and fractional systems.

Algoritmo genético para empacotamento de contentores

No âmbito da investigação operacional o problema de empacotamento de contentores é conhecido por procurar definir uma configuração de carga, de forma a otimizar a utilização de um espaço disponível para efetuar o empacotamento. Este problema pode ser apresentado em diversas formas, formas estas que variam em função das características de cada empacotamento. Estas características podem ser: o tipo de carga que se pretende carregar (homogénea ou heterogénea), a possibilidade de a carga poder sofrer rotações em todas as suas dimensões ou apenas em algumas, o lucro que está associado a cada caixa carregada ou restrições inerentes ao contentor como por exemplo dimensões. O interesse pelo estudo de problemas de empacotamento de contentores tem vindo a receber cada vez mais ênfase por várias razões, uma delas é o interesse financeiro dado que o transporte é uma prática que representa custos, sendo importante diminuir estes custos aproveitando o volume do contentor da melhor forma. Outra preocupação que motiva o estudo deste problema prende-se com fatores ambientes, onde se procura racionalizar os recursos naturais estando esta também ligada a questões financeiras. Na literatura podem ser encontradas varias propostas para solucionar este problema, cada uma destas dirigidas a uma variante do problema, estas propostas podem ser determinísticas ou não determinísticas onde utilizam heurísticas ou metaheurísticas. O estudo realizado nesta dissertação descreve algumas destas propostas, nomeadamente as metaheurísticas que são utilizadas na resolução deste problema. O trabalho aqui apresentado traz também uma nova metaheurísticas, mais precisamente um algoritmo genético que terá como objetivo, apresentar uma configuração de carga para um problema de empacotamento de um contentor. O algoritmo genético tem como objetivo a resolução do seguinte problema: empacotar várias caixas retangulares com diversos tamanhos num contentor. Este problema é conhecido como Bin-Packing. A novidade que este algoritmo genético vai introduzir nas diversas soluções apresentadas até à data, é uma nova forma de criar padrões iniciais, ou seja, é utilizada a heurística HSSI (Heurística de Suavização de Superfícies Irregulares) que tem como objetivo criar uma população inicial de forma a otimizar o algoritmo genético. A heurística HSSI tenta resolver problemas de empacotamento simulando, o comportamento da maioria das pessoas ao fazer este processo na vida real, contudo, tem um campo de busca reduzido entre as soluções possíveis e será então utilizado um algoritmo genético para ampliar este campo de busca e explorar novas soluções. No final pretende-se obter um software onde será possível configurar um dado problema de empacotamento de um contentor e obter, a solução do mesmo através do algoritmo genético. Assim sendo, o estudo realizado tem como principal objetivo contribuir com pesquisas e conclusões, sobre este problema e trazer uma nova proposta de solução para o problema de empacotamento de contentores.

Profissionalidade docente: fonte de possibilidades e de (in)certezas

O longo percurso de formação, iniciado com a Licenciatura em Educação Básica, termina agora com a conclusão do Mestrado em Ensino do 1º e 2º Ciclos do Ensino Básico surgindo, por isso, o presente relatório de estágio no âmbito da unidade curricular de Integração Curricular: Prática Educativa Supervisionada e Relatório de Estágio. Este caminho foi trilhado tomando opções fundamentadas e intencionais, conciliando saberes teóricos e práticos, construídos e desenvolvidos nos contextos educativos onde decorreu a Prática Educativa Supervisionada (PES). Ancorada numa perspetiva de investigação, onde se reconhecem características da metodologia de investigação-ação, a supervisão pedagógica desenrolou-se por etapas que promoveram o crescimento pessoal e profissional da futura professora. Todo o percurso espelhado no decorrer das próximas páginas foi solidamente cimentado graças à experiência partilhada dos orientadores cooperantes, dos supervisores institucionais e do par pedagógico, permitindo desenvolver e consolidar competências heurísticas, bem como a transformação e o melhoramento das práticas. Atribuiu-se, neste processo, um especial significado à relação com o par pedagógico por ter constituído um apoio fundamental, valorizando-se a colaboração, enquanto agente potenciador da tomada de decisão em contextos de incerteza e de complexidade da prática docente. Este relatório de estágio configura-se como mais uma oportunidade de autoconsciência e de reflexão relativamente ao processo de construção da identidade profissional. O constante progresso do mundo atual, as dificuldades sentidas e os obstáculos ultrapassados reforçam a ideia de que o processo de formação será sempre ávido de uma permanente atualização.

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.