Agrupamento de dados com restrições

Mestrado em Engenharia Informática

Auto-regulação na gestão de conflitos em retalho

Mestrado em Engenharia Informática

Aplicação da teoria das restrições na gestão de projectos: caso em estudo

Trabalho Final de Mestrado para obtenção do grau de Mestre em Engenharia Mecânica - Manutenção e Produção

Discursos sobre homossexualidade numa comunidade educativa : perspetivas de professores

Dissertação de Mestrado em Psicologia da Educação, especialidade em Contextos Comunitários.

New insights on integer-programming models for the kidney exchange problem

In recent years several countries have set up policies that allow exchange of kidneys between two or more incompatible patient–donor pairs. These policies lead to what is commonly known as kidney exchange programs. The underlying optimization problems can be formulated as integer programming models. Previously proposed models for kidney exchange programs have exponential numbers of constraints or variables, which makes them fairly difficult to solve when the problem size is large. In this work we propose two compact formulations for the problem, explain how these formulations can be adapted to address some problem variants, and provide results on the dominance of some models over others. Finally we present a systematic comparison between our models and two previously proposed ones via thorough computational analysis. Results show that compact formulations have advantages over non-compact ones when the problem size is large.

Constraint solving over multi-valued logics - application to digital circuits

Due to usage conditions, hazardous environments or intentional causes, physical and virtual systems are subject to faults in their components, which may affect their overall behaviour. In a ‘black-box’ agent modelled by a set of propositional logic rules, in which just a subset of components is externally visible, such faults may only be recognised by examining some output function of the agent. A (fault-free) model of the agent’s system provides the expected output given some input. If the real output differs from that predicted output, then the system is faulty. However, some faults may only become apparent in the system output when appropriate inputs are given. A number of problems regarding both testing and diagnosis thus arise, such as testing a fault, testing the whole system, finding possible faults and differentiating them to locate the correct one. The corresponding optimisation problems of finding solutions that require minimum resources are also very relevant in industry, as is minimal diagnosis. In this dissertation we use a well established set of benchmark circuits to address such diagnostic related problems and propose and develop models with different logics that we formalise and generalise as much as possible. We also prove that all techniques generalise to agents and to multiple faults. The developed multi-valued logics extend the usual Boolean logic (suitable for faultfree models) by encoding values with some dependency (usually on faults). Such logics thus allow modelling an arbitrary number of diagnostic theories. Each problem is subsequently solved with CLP solvers that we implement and discuss, together with a new efficient search technique that we present. We compare our results with other approaches such as SAT (that require substantial duplication of circuits), showing the effectiveness of constraints over multi-valued logics, and also the adequacy of a general set constraint solver (with special inferences over set functions such as cardinality) on other problems. In addition, for an optimisation problem, we integrate local search with a constructive approach (branch-and-bound) using a variety of logics to improve an existing efficient tool based on SAT and ILP.

Constraint reasoning for differential models

The basic motivation of this work was the integration of biophysical models within the interval constraints framework for decision support. Comparing the major features of biophysical models with the expressive power of the existing interval constraints framework, it was clear that the most important inadequacy was related with the representation of differential equations. System dynamics is often modelled through differential equations but there was no way of expressing a differential equation as a constraint and integrate it within the constraints framework. Consequently, the goal of this work is focussed on the integration of ordinary differential equations within the interval constraints framework, which for this purpose is extended with the new formalism of Constraint Satisfaction Differential Problems. Such framework allows the specification of ordinary differential equations, together with related information, by means of constraints, and provides efficient propagation techniques for pruning the domains of their variables. This enabled the integration of all such information in a single constraint whose variables may subsequently be used in other constraints of the model. The specific method used for pruning its variable domains can then be combined with the pruning methods associated with the other constraints in an overall propagation algorithm for reducing the bounds of all model variables. The application of the constraint propagation algorithm for pruning the variable domains, that is, the enforcement of local-consistency, turned out to be insufficient to support decision in practical problems that include differential equations. The domain pruning achieved is not, in general, sufficient to allow safe decisions and the main reason derives from the non-linearity of the differential equations. Consequently, a complementary goal of this work proposes a new strong consistency criterion, Global Hull-consistency, particularly suited to decision support with differential models, by presenting an adequate trade-of between domain pruning and computational effort. Several alternative algorithms are proposed for enforcing Global Hull-consistency and, due to their complexity, an effort was made to provide implementations able to supply any-time pruning results. Since the consistency criterion is dependent on the existence of canonical solutions, it is proposed a local search approach that can be integrated with constraint propagation in continuous domains and, in particular, with the enforcing algorithms for anticipating the finding of canonical solutions. The last goal of this work is the validation of the approach as an important contribution for the integration of biophysical models within decision support. Consequently, a prototype application that integrated all the proposed extensions to the interval constraints framework is developed and used for solving problems in different biophysical domains.

Examination timetabling automation using hybrid meta-heuristics

Trabalho de projeto realizado para obtenção do grau de Mestre em Engenharia Informática e de Computadores

Fisioterapia e reabilitação em Portugal : o financiamento como factor crítico do desempenho

RESUMO - Num contexto em que a prestação de cuidados de Fisioterapia e Reabilitação é identificada como apresentando uma desigualdade e desajustamento da oferta regional superior à dos restantes cuidados de saúde, assim como uma falta de adequação dos preços praticados, perante as condições de oferta e procura actualmente existentes, o presente trabalho tem por objectivo investigar, no domínio do Desempenho, a influência do Financiamento na definição da prestação destes cuidados, tendo como pressuposto genérico que as decisões estratégicas e a reestruturação produtiva das organizações de saúde são condicionadas pelo sistema de preços. Considera-se que o actual sistema de Financiamento/Pagamento provoca um constrangimento na qualidade da resposta destes cuidados a dois níveis: um primeiro nível, ao colocar o pagamento no âmbito dos Meios Complementares de Diagnóstico e Terapêutica (MCDTs) a contratar pelo Serviço Nacional de Saúde, com isso determinando a configuração organizativa do sistema; um segundo nível de constrangimento que incide sobre as estruturas das organizações prestadoras, pela modelação que induz, nomeadamente a nível da sua produção. Na impossibilidade de tratar as duas dimensões do problema, pela falta de indicadores de desempenho deste sector, analisou-se, relativamente ao segundo nível de constrangimento, a produção de fisioterapia de três organizações que, potencialmente, teriam o mesmo o mesmo perfil de oferta por se enquadrarem num mesmo perfil de procura. Os resultados reflectem o pressuposto genérico do trabalho e abrem espaço para colocar como futura hipótese de investigação a razão da(s) causa(s) que poderão estar subjacentes à discrepância encontrada na média de tratamentos por sessão (duas vezes e meia) na produção das duas organizações que foi possível comparar.------------------- ABSTRACT - In a context where the provision of Physical Therapy and Rehabilitation care is identified as having a regional mismatch of supply and inequality above all the others health cares, and a lack of adequacy of prices in the current conditions of supply and demand, the present work has, as main purpose, to investigate, in the field of Performance, the Payment’s influence in shaping the provision of such health care. The general assumption tracking this analysis is that the strategic decisions on productive structure of health care organizations are influenced by the price systems. It is considered that the current Finance / Payment system causes two levels of constraints on the quality of such health care: a first constraint, as it putts its payment under the Supplementary Means of Diagnosis and Therapy (MCDTs), witch ends up establishing the organizational setup of the system; a second level of constraint by modelling the internal structure of these organizations. The lack of indicators characterizing the performance of this sector, addressed the present study to the second dimension, in witch was analysed the physical therapy production in three organizations that, potentially, would have the same profile of supply responding to similar characteristics of demand. The results reflect the above mentioned general assumption that supported the work, and leave an open space for future research, about the reason (s) that lay behind the discrepancy found between the average of treatments per session (two and a half times) in

Environmental Decision Support: a Distributed Artificial Intelligence Approach

Decision making in any environmental domain is a complex and demanding activity, justifying the development of dedicated decision support systems. Every decision is confronted with a large variety and amount of constraints to satisfy as well as contradictory interests that must be sensibly accommodated. The first stage of a project evaluation is its submission to the relevant group of public (and private) agencies. The individual role of each agency is to verify, within its domain of competence, the fulfilment of the set of applicable regulations. The scope of the involved agencies is wide and ranges from evaluation abilities on the technical or economical domains to evaluation competences on the environmental or social areas. The second project evaluation stage involves the gathering of the recommendations of the individual agencies and their justified merge to produce the final conclusion. The incorporation and accommodation of the consulted agencies opinions is of extreme importance: opinions may not only differ, but can be interdependent, complementary, irreconcilable or, simply, independent. The definition of adequate methodologies to sensibly merge, whenever possible, the existing perspectives while preserving the overall legality of the system, will lead to the making of sound justified decisions. The proposed Environmental Decision Support System models the project evaluation activity and aims to assist developers in the selection of adequate locations for their projects, guaranteeing their compliance with the applicable regulations.

Desenvolvimento e Estratégia na Orçamentação: Estudo de Caso

O relatório inserido na Unidade Curricular de DIPRE do Mestrado em Engenharia Civil do ISEP e desenvolvido no âmbito do estágio curricular realizado na COGEDIR, Gestão de Projetos SA, tem como objetivo caraterizar o mercado nacional da construção civil, os procedimentos da orçamentação, analisando os seus processos no âmbito dos concursos públicos em Portugal. Deste modo, o relatório inicia-se com o fundamento da importância da orçamentação na construção civil e a caraterização do mercado da construção no momento atual de crise e as dificuldades dos empreiteiros em obter empreitadas. Em seguida foi realizado um levantamento ao estudo da arte sobre os temas de custos e orçamentos, e ainda uma abordagem as ferramentas de orçamentação. Depois de analisada toda a metodologia de orçamentação, são caraterizados os processos das empresas do grupo para o ato de orçamentação. Nessa linha foi ainda realizado um estudo de vários procedimentos de concurso já finalizados para servir como base de sustentação para uma mudança estratégica a implementar nas empresas. Neste estudo ficou bem patente a tendência dos valores das propostas apresentadas pelos vários concorrentes, nos diferentes procedimentos. Com base nestes elementos é feita uma avaliação simplificada dos valores que os empreiteiros possivelmente apresentam para os diferentes tipos de concursos. Dessa análise foi possível definir a estratégia a implementar pelas empresas. Definida a estratégia a seguir pelas empresas, são alvo de estudo de caso dois procedimentos de realidades distintas. Um relativo ao processo de concurso de uma empreitada de construção e o outro a um concurso de prestação de serviços. Neste capítulo, são abordadas situações reais de processos de concurso, desde a consulta do procedimento, estudo das condicionantes, composição de custos, elaboração da documentação e entrega das propostas.

Standard commercial education robotic platform: intermediate solution to teaching robotics

Teaching robotics to students at the beginning of their studies has become a huge challenge. Simulation environments can be an effective solution to that challenge where students can interact with simulated robots and have the first contact with robotic constraints. From our previous experience with simulation environments it was possible to observe that students with lower background knowledge in robotics where able to deal with a limited number of constraints, implement a simulated robotic platform and study several sensors. The question is: after this first phase what should be the best approach? Should the student start developing their own hardware? Hardware development is a very important part of an engineer's education but it can also be a difficult phase that could lead to discouragement and loss of motivation in some students. Considering the previous constraints and first year engineering students’ high abandonment rate it is important to develop teaching strategies to deal with this problem in a feasible way. The solution that we propose is the integration of a low-cost standard robotic platform WowWee Rovio as an intermediate solution between the simulation phase and the stage where the students can develop their own robots. This approach will allow the students to keep working in robotic areas such as: cooperative behaviour, perception, navigation and data fusion. The propose approach proved to be a motivation step not only for the students but also for the teachers. Students and teachers were able to reach an agreement between the level of demand imposed by the teachers and satisfaction/motivation of the students.

Como responder à heterogeneidade dos alunos, de modo a proporcionar o sucesso de cada um?

O sucesso educativo dos alunos é como facilmente se compreenderá, a essência do ato educativo nas suas múltiplas dimensões e formas. O percurso para a obtenção desse sucesso é variado e representa muitas vezes um enorme investimento das organizações educativas nomeadamente na gestão dos seus recursos humanos. Por outro lado, o modelo organizativo instituído pode ser o fator preponderante para a obtenção do sucesso procurado sobretudo quando ele é promotor de um clima harmonioso e motivador para o ato educativo. O projeto apresentado neste estudo estruturou-se numa nova construção dos grupos de trabalho, em que o conceito tradicional de turma foi substituído por grupos, constituídos por alunos cujo grau de conhecimento e competências no âmbito das disciplinas de Português e Matemática, fosse o mais aproximado possível não perdendo de vista o princípio de heterogeneidade do grupo mesmo que relativa ou diminuída, tão importante para promover a diversidade. Este sistema organizativo rompeu com o conceito tradicional da turma o que implicou uma alteração não só na organização de horários escolares dos alunos e docentes mas também obrigou estruturação e implementação de um processo de mobilidades dos alunos entre grupos em função do seu grau de aprendizagens ou de dificuldades na sua obtenção. Este projeto foi ainda promotor de uma cultura de trabalho colaborativo e partilha entre docentes de cada grupo disciplinar promovendo a sistematização de interações entre pares quer na preparação das atividades letivas quer na discussão e resolução dos constrangimentos que o desenvolvimento do projeto evidenciou.

Evaluating Dynamic Signage for Emergency Evacuation using an Immersive Video Environment

Dissertation submitted in partial fulfillment of the requirements for the Degree of Master of Science in Geospatial Technologies.

A public transport bus assignment problem: parallel metaheuristics assessment

Combinatorial Optimization Problems occur in a wide variety of contexts and generally are NP-hard problems. At a corporate level solving this problems is of great importance since they contribute to the optimization of operational costs. In this thesis we propose to solve the Public Transport Bus Assignment problem considering an heterogeneous fleet and line exchanges, a variant of the Multi-Depot Vehicle Scheduling Problem in which additional constraints are enforced to model a real life scenario. The number of constraints involved and the large number of variables makes impracticable solving to optimality using complete search techniques. Therefore, we explore metaheuristics, that sacrifice optimality to produce solutions in feasible time. More concretely, we focus on the development of algorithms based on a sophisticated metaheuristic, Ant-Colony Optimization (ACO), which is based on a stochastic learning mechanism. For complex problems with a considerable number of constraints, sophisticated metaheuristics may fail to produce quality solutions in a reasonable amount of time. Thus, we developed parallel shared-memory (SM) synchronous ACO algorithms, however, synchronism originates the straggler problem. Therefore, we proposed three SM asynchronous algorithms that break the original algorithm semantics and differ on the degree of concurrency allowed while manipulating the learned information. Our results show that our sequential ACO algorithms produced better solutions than a Restarts metaheuristic, the ACO algorithms were able to learn and better solutions were achieved by increasing the amount of cooperation (number of search agents). Regarding parallel algorithms, our asynchronous ACO algorithms outperformed synchronous ones in terms of speedup and solution quality, achieving speedups of 17.6x. The cooperation scheme imposed by asynchronism also achieved a better learning rate than the original one.