Problema de atribuição de vigilâncias de exames a docentes

O presente trabalho foi realizado com o intuito de resolver o problema de alocação de vigilantes a exames do Instituto Superior de Engenharia do Porto, no departamento de Engenharia Mecânica. O modelo apresentado faz a atribuição das vigilâncias de uma forma hierárquica, utilizando vários critérios, desde a regência da unidade curricular até à simples vigilância. Devido ao facto de estar implementado informaticamente, apresenta reduzidos tempos na formulação e obtenção de uma solução, o que o torna uma boa ferramenta para a criação de cenários alternativos. Em suma, o modelo proposto neste trabalho apresenta soluções de melhor qualidade, em que a distribuição de afetações é proporcional entre os docentes, e o seu tempo de obtenção é muito reduzido em comparação com a alternativa atual.

Resolução do problema de atribuição de salas a exames

Este trabalho pretende resolver o problema das alocações de salas a exames no Departamento de Engenharia Mecânica do Instituto Superior de Engenharia do Porto. A solução desenvolvida atribui salas a exames respeitando as restrições de capacidade de salas e a restrição de realização dum único exame por sala num determinado período, por forma a minimizar a atribuição de salas e, consequentemente, docentes a exames. Foi criado um modelo matemático, que representa as variáveis relevantes do problema, e realiza a sua implementação numa plataforma informática amigável para o utilizador. O modelo matemático foi validado comparando as suas soluções com as obtidas através do processo manual. Os resultados do novo método demonstram a sua supremacia relativamente ao modelo atual. No futuro, poderá ser estudada a possibilidade de usar esta ferramenta na resolução do mesmo problema em realidades diferentes da do Departamento de Engenharia Mecânica do ISEP.

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.

Proposta de solução de videovigilância para locais remotos

Desde tempos remotos que homens faziam a vigilância de bens e mercadorias e mais recentemente também de pessoas com o intuito de dissuadir roubos, atos de vandalismo e de violência. Nos últimos anos, com a evolução das novas tecnologias verificou-se a sua adoção para auxílio da vigilância. Os atos de terrorismo que têm acontecido um pouco por todo o mundo trouxeram um clima de insegurança à população mundial. Este fenómeno, juntamente com o elevado número de roubos e atos de violência levou à expansão de utilização dos meios de videovigilância de forma a dissuadir estes tipos de crime podendo mesmo, nalguns casos servir como prova para punir os autores dos mesmos. Em Portugal tem-se verificado uma escalada de crimes nas zonas mais rurais não só de bens como as alfaias agrícolas mas também de frutos e mesmo de animais. Estes crimes predominam em locais rurais, relativamente distantes das povoações e em locais onde não existem (ou são praticamente inexistentes) infraestruturas necessárias para implementar meios de videovigilância como a falta de rede elétrica e internet o que torna quase inviável a existência de sistemas de videovigilância nesses locais. Dotar esses locais das infra estruturas necessárias poderia tornar-se demasiado dispendioso e os vigilantes humanos poderiam correr riscos no meio dos montes ou noutros locais remotos para além dos seus elevados custos. Para além do problema dos roubos, existe um outro flagelo relacionado com os incêndios na floresta portuguesa, que todos os anos é dizimada pelo fogo devido a incêndios que surgem na sua maioria causados pelo homem sendo uma parte significativa os de origem criminosa. Para dar resposta a estes problemas e no sentido de vigiar e dissuadir estes tipos de crimes, iniciamos um estudo que pretende propor um protótipo de um sistema de videovigilância para locais remotos (SVR - Sistema de Videovigilância Remota) de baixo custo de forma a diminuir o número de crimes e assim minimizar os prejuízos económico e sociais causados pelos mesmos. Pretendemos estudar o problema e analisar tecnologias com potencial para propor uma solução que possa auxiliar a vigilância nesse tipo de locais com o pressuposto de poder vir a contribuir para a diminuição deste tipo de crimes devido ao seu efeito dissuasor pelo facto de se poder divulgar que estes locais já têm uma solução de vigilância oculta. A solução proposta contempla um sistema de videovigilância com uma camara construída com base num Raspberry Pi onde o vídeo é transmitido em streaming via Web através de comunicações móveis. A alimentação do sistema nestes espaços sem energia elétrica é feita através de um painel fotovoltaico. É proporcionado ao utilizador uma interface para visualizar o vídeo transmitido e um mecanismo de notificações por email. É ainda possível a visualização de imagens gravadas num cartão de memória relativas a ocorrências de deteção de movimentos. Foram realizados inúmeros testes ao protótipo SVR sendo os resultados obtidos aqui descritos.

Programação paralela estruturada aplicada a um problema de reconstrução de imagem

A Digital Breast Tomosynthesis (DBT) é uma técnica que permite obter imagens mamárias 3D de alta qualidade, que só podem ser obtidas através de métodos de re-construção. Os métodos de reconstrução mais rápidos são os iterativos, sendo no en-tanto computacionalmente exigentes, necessitando de sofrer muitas optimizações. Exis-tem optimizações que usam computação paralela através da implementação em GPUs usando CUDA. Como é sabido, o desenvolvimento de programas eficientes que usam GPUs é ainda uma tarefa demorada, dado que os modelos de programação disponíveis são de baixo nível, e a portabilidade do código para outras arquitecturas não é imedia-ta. É uma mais valia poder criar programas paralelos de forma rápida, com possibili-dade de serem usados em diferentes arquitecturas, sem exigir muitos conhecimentos sobre a arquitectura subjacente e sobre os modelos de programação de baixo nível. Para resolver este problema, propomos a utilização de soluções existentes que reduzam o esforço de paralelização, permitindo a sua portabilidade, garantindo ao mesmo tempo um desempenho aceitável. Para tal, vamos utilizar um framework (FastFlow) com suporte para Algorithmic Skeletons, que tiram partido da programação paralela estruturada, capturando esquemas/padrões recorrentes que são comuns na programação paralela. O trabalho realizado centrou-se na paralelização de uma das fases de reconstru-ção da imagem 3D – geração da matriz de sistema – que é uma das mais demoradas do processo de reconstrução; esse trabalho incluiu um método de ordenação modificado em relação ao existente. Foram realizadas diferentes implementações em CPU e GPU (usando OpenMP, CUDA e FastFlow) o que permitiu comparar estes ambientes de programação em termos de facilidade de desenvolvimento e eficiência da solução. A comparação feita permite concluir que o desempenho das soluções baseadas no FastFlow não é muito diferente das tradicionais o que sugere que ferramentas deste tipo podem simplificar e agilizar a implementação de um algoritmos na área de recons-trução de imagens 3D, mantendo um bom desempenho.

Optimização do processo de recolha de resíduos: desenvolvimento de ferramentas de investigação operacional para o problema de orientação de equipas com multi-restrições

Tese de Doutoramento em Engenharia Industrial e de Sistemas.

Contribuição ao estudo do problema alimentar da Amazônia

Salientando os diversos aspectos a atender, para a solução racional do problema da alimentação na Amazônia, aliás já fixados em 1941 pela Comissão que traçou as linhas gerais de um plano de saneamento dessa vasta região, aludem os A.A. às realizações já empreendidas dentro do programa traçado, e que versaram apenas sôbre os hábitos alimentares de um grande núcleo de população e sôbre o valor nutritivo de alguns elementos pouco conhecidos da fauna e da flora locais. Abordam, à guisa de ensaio, neste trabalho, o ponto concernente ao planejamento de regimes adequados, que se adaptem tanto às exigências, como as possibilidades regionais. Frisam, então, de início, as bases racionais a que devem eles obedecer respeito não só à redução do total de calorias, fornecidas, nos seus 2/3, por hidratos de carbono e ao qual se subordinam as cotas das três principais vitaminas do complexo B,* como também a restrição, igualmente indicada, da taxa de proteínas; respeito, ainda, as cotas recomendáveis das vitaminas A e C e de cálcio, dando aí especial atenção ao detalhe da sua aproveitabilidade. Referem, de passagem, à conveniência de não se descurar do problema do ferro alimentar, em face das endemias reinantes na região e das dificuldades para fazer, artificialmente, o enriquecimento marcial dos regimes, já que, para instituí-los, partem do principio de ser vantajoso lançar mão de recursos de produção local, sem ficar em marcada dependência de grandes centres distribuidores regionais. Mostrando as dificuldades para a utilização, na escala desejada, da carne e leite de vaca, como artigos básicos de regime — e apontam, entre os percalços, os inerentes ao transporte e conservação desses alimentos — apresentam uma tabela básica, para o adulto em trabalho moderado, a qual lhe fornece 2.600 calorias diárias e obedece aos pontos fundamentais já aludidos. Nela figuram: os peixes, cujas variedades de pequeno porte poderão, com vantagem, ser consumidas fritas ou torradas, com espinhas; o amendoim; as verduras de produção econômica na Amazônia, incluídas na lista as ramas de batata doce, da mandioca e do inhame; essas raízes e tubérculos feculentos, de parceria com o cara; a farinha de mandioca, de grande uso na região; frutas, em que e, alias, rica a flora local; melado ou rapadura, como boa fonte de açucarados, cálcio e ferro; gorduras de origem animal e vegetal. Detêm-se, a propósito de cada um desses alimentos, sôbre o seu valor nutritivo e as possibilidades reais de produção local ou regional. Enumeram, por fim, vários outros, a que, similarmente, será possível recorrer, em maior ou menor escala — criação de animais domésticos, caças, carne e ovos de tartaruga, arroz, raízes, brotos de palmeiras, feijão de vara, castanhas de sapucaia, do caju e do Para — numa demonstração de ser possível a Amazônia valer-se, de muito, a si própria, no tocante à alimentação das suas populações.

Problema alimentar do Maranhão e Piauí: subsidio para o seu estudo

Os A. A., prosseguindo na serie de estudos,que vêm realizando, como contribuição para a solução racional do problema da alimentação das populações brasileiras, cuidam neste trabalho do Maranhão e do Piaui, considerados englobadamente, como área de transição entre as três Grandes Regiões, do Norte, do Nordeste e do Centro-oeste do país. Dando os caracteristicos principais e revistando, em face de informes estatisticos e de outros dados, as possibilidades presentes e futuras, de pesca, criação e agricultura, para as 19 zonas geograficas, discriminadas, dentro do conjunto dos dois Estados, pelo conselho nacional de Geografia, mostram ser na verdade realizavel dispo-las em três áreas distintas de abastecimento: isto dentro do proposito em vista de planejar regimes alimentares que, atendendo aos preceitos da ciencia da nutrição, se adaptem ás possíveis disponibilidades regionais. Facilidades, maiores ou menores, para provisão de leite e de pescado representam, afinal, os fatores dominantes nesta diferenciação de áreas de abastecimento. Em função de tais variações e recorrendo, ademais, a outros alimentos, cujo cultivo e produção são objeto de exame, organizaram os A. A., à guisa de exemplos, três regimes, um para cada área, e que atendem, satisfatoriamente, aos pontos basicos acima referidos. Mostram, em suma, como é possivel, aos dois Estados, valerem-se a si próprios em materia de alimentação.

Treinamento em solução de problemas: intervenção em mulheres com de pressão

Estudo exploratório, descritivo, que objetivou, a partir do Treinamento em Solução de Problemas, realizado em 12 sessões de grupo com mulheres internadas por depressão, avaliar o efeito desta intervenção. Para a avaliação, utilizou-se o Inventário de Depressão de BECK, Inventário de Ansiedade - Estado de SPILBERGER, Lista de Problema de MC KAY, Exercício de simulação por escrito sobre enfrentamento em cinco situações e entrevista sobre a percepção em participarem do grupo. Concluiu-se que o treinamento teve efeitos positivos sobre as pacientes, tanto pela técnica, como pela comunicação estabelecida e pelos fatores terapêuticos grupais que surgiram neste cenário.

Resposta diferencial de cultivares de algodão ao manganês em solução nutritiva

Enquanto a toxidez de Mn pode ser um problema para a cultura do algodoeiro nos estados de São Paulo e Paraná, a deficiência pode causar problemas nas áreas de solos sob cerrado. No presente trabalho, objetivou-se o estudo da resposta comparativa de cultivares de algodão ao Mn, em solução nutritiva. Plantas de algodão dos cultivares Coodetec 401, CNPA-ITM 90 e IAC 22 foram cultivadas em vasos, com solução nutritiva que continha 0,0, 36,4, 72,8, 145,5 e 290,9 ∝mol L-1 de Mn, por 70 dias. Foi observado sintoma de deficiência de Mn apenas no tratamento sem Mn, para os três cultivares. A deficiência de Mn na solução nutritiva provocou a diminuição da altura das plantas, produção de matéria seca, absorção de Mn e retenção de estruturas reprodutivas. Não foram notados sintomas visuais de toxidez de Mn em qualquer dos três cultivares, mesmo com teores muito altos do nutriente nas folhas. Embora os três cultivares não apresentem diferenças quanto à absorção total de Mn, IAC 22 é mais sensível à toxidez, enquanto Coodetec 401 e CNPA-ITM 90 são mais sensíveis à deficiência do nutriente. Pode haver prejuízo na fixação de estruturas reprodutivas, tanto com deficiência como com toxidez de Mn, sem sintomas aparentes.

Problemas com o uso de programação linear com posterior arredondamento da solução ótima, em regulação florestal

O principal objetivo deste trabalho foi avaliar, com a ajuda da Programação Inteira, as conseqüências do uso da Programação Linear com posterior arredondamento das respostas, com ênfase na regulação de florestas eqüiâneas. Para isto, um problema de regulação florestal simplificado foi idealizado e resolvido pelo modelo I, por meio de Programação Linear, Programação Linear com posterior arredondamento e Programação Inteira. Ao final, concluiu-se que o arredondamento das respostas obtidas pelo modelo resolvido por Programação Linear levou a uma solução inviável para o problema de regulação proposto. O mesmo não ocorreu com o modelo de Programação Inteira, que apresentou um plano de regulação factível e otimizado, mostrando que, do ponto de vista matemático, respostas com arredondamento da solução de modelos de Programação Linear não devem ser adotadas.

Solução de problemas de planejamento florestal com restrições de inteireza utilizando busca tabu

Este trabalho teve como objetivos desenvolver e testar um algoritmo com base na metaheurística busca tabu (BT), para a solução de problemas de gerenciamento florestal com restrições de inteireza. Os problemas avaliados tinham entre 93 e 423 variáveis de decisão, sujeitos às restrições de singularidade, produção mínima e produção máxima periódicas. Todos os problemas tiveram como objetivo a maximização do valor presente líquido. O algoritmo para implementação da BT foi codificado em ambiente delphi 5.0 e os testes foram efetuados em um microcomputador AMD K6II 500 MHZ, com memória RAM de 64 MB e disco rígido de 15GB. O desempenho da BT foi avaliado de acordo com as medidas de eficácia e eficiência. Os diferentes valores ou categorias dos parâmetros da BT foram testados e comparados quanto aos seus efeitos na eficácia do algoritmo. A seleção da melhor configuração de parâmetros foi feita com o teste L&O, a 1% de probabilidade, e as análises através de estatísticas descritivas. A melhor configuração de parâmetros propiciou à BT eficácia média de 95,97%, valor mínimo igual a 90,39% e valor máximo igual a 98,84%, com um coeficiente de variação de 2,48% do ótimo matemático. Para o problema de maior porte, a eficiência da BT foi duas vezes superior à eficiência do algoritmo exato branch and bound, apresentando-se como uma abordagem muito atrativa para solução de importantes problemas de gerenciamento florestal.

Metaheurística algoritmo genético para solução de problemas de planejamento florestal com restrições de integridade

Os objetivos deste trabalho foram desenvolver e testar um algoritmo genético (AG) para a solução de problemas de gerenciamento florestal com restrições de integridade. O AG foi testado em quatro problemas, contendo entre 93 e 423 variáveis de decisão, sujeitos às restrições de singularidade, produção mínima e produção máxima, periodicamente. Todos os problemas tiveram como objetivo a maximização do valor presente líquido. O AG foi codificado em ambiente delphi 5.0 e os testes foram realizados em um microcomputador AMD K6II 500 MHZ, com memória RAM de 64 MB e disco rígido de 15GB. O desempenho do AG foi avaliado de acordo com as medidas de eficácia e eficiência. Os valores ou categorias dos parâmetros do AG foram testados e comparados quanto aos seus efeitos na eficácia do algoritmo. A seleção da melhor configuração de parâmetros foi feita com o teste L&O, a 1% de probabilidade, e as análises foram realizadas através de estatísticas descritivas. A melhor configuração de parâmetros propiciou ao AG eficácia média de 94,28%, valor mínimo de 90,01%, valor máximo de 98,48%, com coeficiente de variação de 2,08% do ótimo matemático, obtido pelo algoritmo exato branch and bound. Para o problema de maior porte, a eficiência do AG foi cinco vezes superior à eficiência do algoritmo exato branch and bound. O AG apresentou-se como uma abordagem bastante atrativa para solução de importantes problemas de gerenciamento florestal.

Metaheurística Simulated Annealing para solução de problemas de planejamento florestal com restrições de integridade

Os objetivos deste trabalho foram desenvolver e testar a metaheurística SA para solução de problemas de gerenciamento florestal com restrições de integridade. O algoritmo SA desenvolvido foi testado em quatro problemas, contendo entre 93 e 423 variáveis de decisão, sujeitos às restrições de singularidade, produção mínima e produção máxima, periodicamente. Todos os problemas tiveram como objetivo a maximização do valor presente líquido. O algoritmo SA foi codificado em liguagem delphi 5.0 e os testes foram efetuados em um microcomputador AMD K6II 500 MHZ, com memória RAM de 64 MB e disco rígido de 15GB. O desempenho da SA foi avaliado de acordo com as medidas de eficácia e eficiência. Os diferentes valores ou categorias dos parâmetros da SA foram testados e comparados quanto aos seus efeitos na eficácia do algoritmo. A seleção da melhor configuração de parâmetros foi feita com o teste L&O, a 1% de probabilidade, e as análises foram realizadas através de estatísticas descritivas. A melhor configuração de parâmetros propiciou à SA eficácia média de 95,36%, valor mínimo de 83,66%, valor máximo de 100% e coeficiente de variação igual a 3,18% do ótimo matemático obtido pelo algoritmo exato branch and bound. Para o problema de maior porte, a eficiência da SA foi dez vezes superior à eficiência do algoritmo exato branch and bound. O bom desempenho desta heurística reforçou as conclusões, tiradas em outros trabalhos, do seu enorme potencial para resolver importantes problemas de gerenciamento florestal de difícil solução pelos instrumentos computacionais da atualidade.

Um modelo de regulação florestal e suas implicações na formulação e solução de problemas com restrições de recobrimento

Este trabalho teve como objetivo avaliar uma estratégia utilizada para geração de alternativas de manejo na formulação e solução de problemas de planejamento florestal com restrições de recobrimento. O problema de planejamento florestal foi formulado via modelo I e modelo II, assim denominados por Johnson E Scheurman (1977), resultando em problemas de programação linear inteira com 63 e 42 alternativas de manejo, respectivamente. Conforme esperado, no problema formulado via modelo I não houve violação das restrições de recobrimento, enquanto no problema formulado via modelo II algumas unidades de manejo foram fracionadas, fato já esperado, uma vez que essa formulação não assegura a integridade das unidades de manejo. Na formulação via modelo II, para assegurar a integridade das unidades de manejo foi necessário reformular o problema como um problema de programação não-linear inteira, problema esse de solução ainda mais complexa do que os de programação linear inteira. As soluções eficientes dos problemas de programação não-linear inteira esbarram nas limitações de eficiências dos principais algoritmos de solução exata e na carência de aplicações dos algoritmos aproximativos na solução desse tipo de problema, a exemplo das metaeurísticas simulated annealing, busca tabu e algoritmos genéticos, tornando-se, portanto, um atrativo para pesquisas nessa área.