Auto-parametrização de meta-heurísticas para escalonamento dinâmico

Este artigo aborda o problema da parametrização de Técnicas de Optimização Inspiradas na Biologia (BIT - Biological Inspired Optimization Techniques), também conhecidas como Meta-heurísticas, considerando a importância que estas técnicas têm na resolução de situações de mundo real, sujeitas a perturbações externas. É proposto um módulo de aprendizagem com o objectivo de permitir que um Sistema Multi-Agente (SMA) para Escalonamento seleccione automaticamente uma Metaheurística e escolha a parametrização a usar no processo de optimização. Para o módulo de aprendizagem foi usado o Raciocínio baseado em Casos (RBC), permitindo ao sistema aprender a partir da experiência acumulada na resolução de problemas similares. Através da análise dos resultados obtidos é possível concluir acerca das vantagens da sua utilização.

Híper-heurísticas com aprendizagem

A otimização nos sistemas de suporte à decisão atuais 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, sendo que a computação de soluções ótimas em muitos destes problemas é intratável. Os métodos de pesquisa heurística são conhecidos por permitir obter bons resultados num intervalo temporal aceitável. Muitas vezes, necessitam que a parametrização seja ajustada de forma a permitir obter bons resultados. Neste sentido, as estratégias de aprendizagem podem incrementar o desempenho de um sistema, dotando-o com a capacidade de aprendizagem, por exemplo, qual a técnica de otimização mais adequada para a resolução de uma classe particular de problemas, ou qual a parametrização mais adequada de um dado algoritmo num determinado cenário. Alguns dos métodos de otimização mais usados para a resolução de problemas do mundo real resultaram da adaptação de ideias de várias áreas de investigação, principalmente com inspiração na natureza - Meta-heurísticas. O processo de seleção de uma Meta-heurística para a resolução de um dado problema é em si um problema de otimização. As Híper-heurísticas surgem neste contexto como metodologias eficientes para selecionar ou gerar heurísticas (ou Meta-heurísticas) na resolução de problemas de otimização NP-difícil. Nesta dissertação pretende-se dar uma contribuição para o problema de seleção de Metaheurísticas respetiva parametrização. Neste sentido é descrita a especificação de uma Híperheurística para a seleção de técnicas baseadas na natureza, na resolução do problema de escalonamento de tarefas em sistemas de fabrico, com base em experiência anterior. O módulo de Híper-heurística desenvolvido utiliza um algoritmo de aprendizagem por reforço (QLearning), que permite dotar o sistema da capacidade de seleção automática da Metaheurística a usar no processo de otimização, assim como a respetiva parametrização. Finalmente, procede-se à realização de testes computacionais para avaliar a influência da Híper- Heurística no desempenho do sistema de escalonamento AutoDynAgents. Como conclusão genérica, é possível afirmar que, dos resultados obtidos é possível concluir existir vantagem significativa no desempenho do sistema quando introduzida a Híper-heurística baseada em QLearning.

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.

Aspectos de aprendizagem em optimização

A optimização e a aprendizagem em Sistemas Multi-Agente são consideradas duas áreas promissoras mas relativamente pouco exploradas. A optimização nestes ambientes deve ser capaz de lidar com o dinamismo. Os agentes podem alterar o seu comportamento baseando-se em aprendizagem recente ou em objectivos de optimização. As estratégias de aprendizagem podem melhorar o desempenho do sistema, dotando os agentes da capacidade de aprender, por exemplo, qual a técnica de optimização é mais adequada para a resolução de uma classe particular de problemas, ou qual a parametrização é mais adequada em determinado cenário. Nesta dissertação são estudadas algumas técnicas de resolução de problemas de Optimização Combinatória, sobretudo as Meta-heurísticas, e é efectuada uma revisão do estado da arte de Aprendizagem em Sistemas Multi-Agente. É também proposto um módulo de aprendizagem para a resolução de novos problemas de escalonamento, com base em experiência anterior. O módulo de Auto-Optimização desenvolvido, inspirado na Computação Autónoma, permite ao sistema a selecção automática da Meta-heurística a usar no processo de optimização, assim como a respectiva parametrização. Para tal, recorreu-se à utilização de Raciocínio baseado em Casos de modo que o sistema resultante seja capaz de aprender com a experiência adquirida na resolução de problemas similares. Dos resultados obtidos é possível concluir da vantagem da sua utilização e respectiva capacidade de adaptação a novos e eventuais cenários.

Este luminoso e magnifico céu azul

Num texto de cariz jornalístico, escrito na plena maturidade da sua vida literária, em 1895, Eça de Queirós reflecte irónica e liricamente sobre a chamada ―influência‖ do clima sobre a mentalidade, a cultura e a economia dos povos europeus. É seu pretexto uma cómica palinódia dos seus sarcasmos juvenis acerca de um romântico desabafo poético-político de um ex-primeiro-ministro português, o qual enaltecia, como principal riqueza nacional, ―o luminoso e magnífico céu azul que nos cobre!‖. Já desde a década de 1870, no advento da sua vida de escritor, que, para Eça, é tema recorrente uma espécie de ―mitologia do sul‖, em que impera a tutela benfazeja e doce do céu meridional. Nesta crónica, no fim da sua vida, Eça de Queirós retoma e desenvolve, definitivamente, uma representação cultural e psicológica do clima meridional, pretexto para uma magnífica síntese contrastiva sobre o Norte e o Sul da Europa, uma enternecida apologia do sol, do calor e da luz dos climas ―ricos‖, saudosamente evocados durante um Inverno sombrio em Paris. É justamente a coerência exemplar deste motivo – associada, não obstante, à natural e estratégica evolução estético-ideológica do autor – que será objecto de reflexão deste texto: porque o signo climático e a oposição Norte/ Sul podem funcionar como noções heurísticas de uma obra e de um autor sobre os quais (como sobre Flaubert) já se disse muito, mas nunca se diz o suficiente.

Projecto de avaliação de interfaces – PAI

Para obtenção do grau de Doutor pela Universidade de Vigo com menção internacional Departamento de Informática

Simulação de um Pool Simétrico com validação técnica do despacho provisório e apresentação de medidas corretivas baseadas num despacho ótimo

Os mercados de energia elétrica são atualmente uma realidade um pouco por todo o mundo. Contudo, não é consensual o modelo regulatório a utilizar, o que origina a utilização de diferentes modelos nos diversos países que deram início ao processo de liberalização e de reestruturação do sector elétrico. A esses países, dado que a energia elétrica não é um bem armazenável, pelo menos em grandes quantidades, colocam-se questões importantes relacionadas com a gestão propriamente dita do seu sistema elétrico. Essas questões implicam a adoção de regras impostas pelo regulador que permitam ultrapassar essas questões. Este trabalho apresenta um estudo feito aos mercados de energia elétrica existentes um pouco por todo o mundo e que o autor considerou serem os mais importantes. Foi também feito um estudo de ferramentas de otimização essencialmente baseado em meta-heurísticas aplicadas a problemas relacionados com a operação dos mercados e com os sistemas elétricos de energia, como é o exemplo da resolução do problema do Despacho Económico. Foi desenvolvida uma aplicação que simula o funcionamento de um mercado que atua com o modelo Pool Simétrico, em que são transmitidas as ofertas de venda e compra de energia elétrica por parte dos produtores, por um lado, e dos comercializadores, consumidores elegíveis ou intermediários financeiros, por outro, analisando a viabilidade técnica do Despacho Provisório. A análise da viabilidade técnica do Despacho Provisório é verificada através do modelo DC de trânsito de potências. No caso da inviabilidade do Despacho Provisório, por violação de restrições afetas ao problema, são determinadas medidas corretivas a esse despacho, com base nas ofertas realizadas e recorrendo a um Despacho Ótimo. Para a determinação do Despacho Ótimo recorreu-se à meta-heurística Algoritmos Genéticos. A aplicação foi desenvolvida no software MATLAB utilizando a ferramenta Graphical User Interfaces. A rede de teste utilizada foi a rede de 14 barramentos do Institute of Electrical and Electronics Engineers (IEEE). A aplicação mostra-se competente no que concerne à simulação de um mercado com tipo de funcionamento Pool Simétrico onde são efetuadas ofertas simples e onde as transações ocorrem no mercado diário, porém, não reflete o problema real relacionado a este tipo de mercados. Trata-se, portanto, de um simulador básico de um mercado de energia cujo modelo de funcionamento se baseia no tipo Pool Simétrico.

Afetação de recursos em sistemas de produção

O problema do escalonamento, por ser um dos factores fundamentais na tomada de decisão para uma boa gestão das operações, tem sido alvo de um amplo estudo, tanto na sua componente teórica como na sua componente prática. A importância de um escalonamento correto das operações é preponderante, quando as pequenas diferenças, em termos de tempos de produção, podem ter um grande impacto na competitividade da organização. Em muitas unidades produtivas, existem máquinas capazes de realizar as mesmas operações com diferentes desempenhos. Isto pode dever-se à necessidade de flexibilizar os recursos ou mesmo a uma atualização da capacidade produtiva. Embora os problemas de máquinas diferentes em paralelo tenham sido alvo de um vasto estudo, muitos deles não são passíveis de ser resolvidos através de métodos exatos. O problema de minimização do makespan (Rm||Cmax), é NP-hard, sendo habitualmente abordado através de heurísticas. Entre as heurísticas utilizadas em problemas de minimização do makespan em máquinas diferentes em paralelo, é possível identificar duas filosofias de afectação: a que utiliza os tempos de processamento para alocar as tarefas e a que utiliza as datas de conclusão. Nesta dissertação, pretende-se dar uma contribuição para a resolução do problema de afectação de recursos em sistemas de produção. Para tal, foram propostas as heurísticas OMTC 3 e Suffrage One. A contribuição consiste na proposta de versões híbridas e modificadas das heurística MCT e Suffrage, uma vez identificadas várias características que podem limitar o seu desempenho, como o facto da heurística MCT alocar as tarefas numa ordem aleatória ou a heurística Suffrage alocar mais que uma tarefa por iteração. Finalmente, procedeu-se à realização de testes computacionais, para avaliar o desempenho das heurísticas propostas. Os testes realizados permitiram concluir que a heurística OMTC 3 apresentou um melhor desempenho que a heurística MCT.

Tolerância a falhas em sistemas de tempo-real distribuídos e embebidos

Este documento descreve um modelo de tolerância a falhas para sistemas de tempo-real distribuídos. A sugestão deste modelo tem como propósito a apresentação de uma solu-ção fiável, flexível e adaptável às necessidades dos sistemas de tempo-real distribuídos. A tolerância a falhas é um aspeto extremamente importante na construção de sistemas de tempo-real e a sua aplicação traz inúmeros benefícios. Um design orientado para a to-lerância a falhas contribui para um melhor desempenho do sistema através do melhora-mento de aspetos chave como a segurança, a confiabilidade e a disponibilidade dos sis-temas. O trabalho desenvolvido centra-se na prevenção, deteção e tolerância a falhas de tipo ló-gicas (software) e físicas (hardware) e assenta numa arquitetura maioritariamente basea-da no tempo, conjugada com técnicas de redundância. O modelo preocupa-se com a efi-ciência e os custos de execução. Para isso utilizam-se também técnicas tradicionais de to-lerância a falhas, como a redundância e a migração, no sentido de não prejudicar o tempo de execução do serviço, ou seja, diminuindo o tempo de recuperação das réplicas, em ca-so de ocorrência de falhas. Neste trabalho são propostas heurísticas de baixa complexida-de para tempo-de-execução, a fim de se determinar para onde replicar os componentes que constituem o software de tempo-real e de negociá-los num mecanismo de coordena-ção por licitações. Este trabalho adapta e estende alguns algoritmos que fornecem solu-ções ainda que interrompidos. Estes algoritmos são referidos em trabalhos de investiga-ção relacionados, e são utilizados para formação de coligações entre nós coadjuvantes. O modelo proposto colmata as falhas através de técnicas de replicação ativa, tanto virtual como física, com blocos de execução concorrentes. Tenta-se melhorar ou manter a sua qualidade produzida, praticamente sem introduzir overhead de informação significativo no sistema. O modelo certifica-se que as máquinas escolhidas, para as quais os agentes migrarão, melhoram iterativamente os níveis de qualidade de serviço fornecida aos com-ponentes, em função das disponibilidades das respetivas máquinas. Caso a nova configu-ração de qualidade seja rentável para a qualidade geral do serviço, é feito um esforço no sentido de receber novos componentes em detrimento da qualidade dos já hospedados localmente. Os nós que cooperam na coligação maximizam o número de execuções para-lelas entre componentes paralelos que compõem o serviço, com o intuito de reduzir atra-sos de execução. O desenvolvimento desta tese conduziu ao modelo proposto e aos resultados apresenta-dos e foi genuinamente suportado por levantamentos bibliográficos de trabalhos de in-vestigação e desenvolvimento, literaturas e preliminares matemáticos. O trabalho tem também como base uma lista de referências bibliográficas.

Selection Constructive based Hyper-heuristic for Dynamic Scheduling

A função de escalonamento desempenha um papel importante nos sistemas de produção. Os sistemas de escalonamento têm como objetivo gerar um plano de escalonamento que permite gerir de uma forma eficiente um conjunto de tarefas que necessitam de ser executadas no mesmo período de tempo pelos mesmos recursos. Contudo, adaptação dinâmica e otimização é uma necessidade crítica em sistemas de escalonamento, uma vez que as organizações de produção têm uma natureza dinâmica. Nestas organizações ocorrem distúrbios nas condições requisitos de trabalho regularmente e de forma inesperada. Alguns exemplos destes distúrbios são: surgimento de uma nova tarefa, cancelamento de uma tarefa, alteração na data de entrega, entre outros. Estes eventos dinâmicos devem ser tidos em conta, uma vez que podem influenciar o plano criado, tornando-o ineficiente. Portanto, ambientes de produção necessitam de resposta imediata para estes eventos, usando um método de reescalonamento em tempo real, para minimizar o efeito destes eventos dinâmicos no sistema de produção. Deste modo, os sistemas de escalonamento devem de uma forma automática e inteligente, ser capazes de adaptar o plano de escalonamento que a organização está a seguir aos eventos inesperados em tempo real. Esta dissertação aborda o problema de incorporar novas tarefas num plano de escalonamento já existente. Deste modo, é proposta uma abordagem de otimização – Hiper-heurística baseada em Seleção Construtiva para Escalonamento Dinâmico- para lidar com eventos dinâmicos que podem ocorrer num ambiente de produção, a fim de manter o plano de escalonamento, o mais robusto possível. Esta abordagem é inspirada em computação evolutiva e hiper-heurísticas. Do estudo computacional realizado foi possível concluir que o uso da hiper-heurística de seleção construtiva pode ser vantajoso na resolução de problemas de otimização de adaptação dinâmica.

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.

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.

Estudo e análise do sequenciamento de tarefas de produção: job shop scheduling

Esta dissertação apresenta um estudo sobre os problemas de sequenciamento de tarefas de produção do tipo job shop scheduling. Os problemas de sequenciamento de tarefas de produção pretendem encontrar a melhor sequência para o processamento de uma lista de tarefas, o instante de início e término de cada tarefa e a afetação de máquinas para as tarefas. Entre estes, encontram-se os problemas com máquinas paralelas, os problemas job shop e flow shop. As medidas de desempenho mais comuns são o makespan (instante de término da execução de todas as tarefas), o tempo de fluxo total, a soma dos atrasos (tardiness), o atraso máximo, o número de tarefas que são completadas após a data limite, entre outros. Num problema do tipo job shop, as tarefas (jobs) consistem num conjunto de operações que têm de ser executadas numa máquina pré-determinada, obedecendo a um determinado sequenciamento com tempos pré-definidos. Estes ambientes permitem diferentes cenários de sequenciamento das tarefas. Normalmente, não são permitidas interrupções no processamento das tarefas (preemption) e pode ainda ser necessário considerar tempos de preparação dependentes da sequência (sequence dependent setup times) ou atribuir pesos (prioridades) diferentes em função da importância da tarefa ou do cliente. Pretende-se o estudo dos modelos matemáticos existentes para várias variantes dos problemas de sequenciamento de tarefas do tipo job shop e a comparação dos resultados das diversas medidas de desempenho da produção. Este trabalho contribui para demonstrar a importância que um bom sequenciamento da produção pode ter na sua eficiência e consequente impacto financeiro.