A operação de uma companhia área raramente acontece como planeado. São comuns os problemas relacionados com os aviões, com as tripulações e com os passageiros. As acções que têm como objectivo resolver estes problemas são conhecidas como Gestão das Irregularidades Operacionais. O Centro de Controlo Operacional da Companhia Aérea (CCO) tenta resolver estes problemas com o mínimo de impacto na operação, com o mínimo custo e, ao mesmo tempo, satisfazendo todas as regras de segurança requeridas. Normalmente, cada problema é tratado separadamente e algumas ferramentas têm sido propostas para ajudar no processo de tomada de decisão pelos coordenadores destes centros de controlo. Observamos o CCO da TAP Portugal, a maior companhia aérea Portuguesa, e, destas observações, várias hipóteses foram identificadas e algumas experimentadas. Acreditamos, e esta é uma das nossas principais hipóteses, que o paradigma do Sistema Multi-Agente (SMA) é mais adequado para representar a organização hierárquica de vários níveis e as várias funções (roles) existentes no CCO. Nesta tese, propomos o desenho e a implementação parcial de um SMA Distribuído que represente as várias funções existentes no CCO. Admitimos a hipótese de que, tirando partido do facto de que cada base operacional tem recursos específicos (quer aviões quer tripulantes) e juntando informações que digam respeito aos custos envolvidos (por exemplo, informação sobre vencimentos dos tripulantes, custos dos hotéis, entre outros), as soluções para os problemas detectados serão encontradas mais rapidamente e serão menos caras. Também admitimos a hipótese de que se utilizarmos agentes de software especializados que implementam diferentes soluções (heurísticas e outras soluções baseadas em modelos de investigação operacional e algoritmos de inteligência artificial) aplicadas ao mesmo problema, a robustez do sistema irá aumentar. Finalmente, acreditamos que a inclusão de um mecanismo de aprendizagem, que aprenda com a utilização anterior dos tripulantes, irá aumentar a qualidade das soluções. Estendendo esse mecanismo de forma a aprender o perfil de cada tripulante e aplicando esse conhecimento na geração de planeamentos (escalas) futuros, a gestão deste recurso tão caro será muito mais eficiente e o nível de satisfação de cada tripulante irá aumentar. Apresentamos um caso de estudo real, obtido no CCO da TAP, onde um problema relacionado com tripulantes é resolvido usando o SMA proposto. Apresentamos resultados computacionais, usando uma operação real da companhia aérea, incluindo a comparação com uma solução para o mesmo problema encontrada pelo operador humano do CCO. Mostramos que, mesmo para problemas simples e quando comparado com soluções encontradas por operadores humanos, no caso específico desta companhia aérea, é possível encontrar soluções válidas, em menos tempo e com menos custos.Nesta tese também mostramos como completamos a metodologia GAIA de forma a melhor analisar e desenhar o SMA proposto para o CCO. Para além de mostrarmos o rationale que está por trás da análise, desenho e implementação do nosso sistema, também mostramos como mapeamos as abstracções usadas no desenho orientado a agentes para código específico em JADE. As vantagens da utilização de uma análise de requisitos orientada a objectivos e a sua influência nas fases seguintes da análise e do desenho, também são apresentadas. Finalmente, propomos diagramas UML 2.0 para representação de vários deliverables da GAIA, tais como, estrutura organizacional, modelos de funções (role) e de interacções e modelos de agentes e de serviços. / An airline schedule seldom operates as planned. Problems related with aircrafts, crew members and passengers are common and the actions towards the solution of these problems are usually known as operations recovery or disruption management. The Airline Operations Control Center (AOCC) tries to solve these problems with the minimum impact in the airline schedule, with the minimum cost and, at the same time, satisfying all the required safety rules. Usually, each problem is treated separately and some tools have been proposed to help in the decision making process of the airline coordinators. We have observed the AOCC of TAP Portugal, the major Portuguese airline, and, from those observations, several hypotheses have been identified and some of them experimented. We believe, and that is one of our main hypothesis, that the Multi-Agent System (MAS) paradigm is more adequate to represent the multi-level hierarchy organization and the several roles that are played in an AOCC. In this thesis we propose the design and partial implementation of a Distributed MAS representing the existing roles in an AOCC. We hypothesize that if we take advantage of the fact that each operational base has specific resources (both crew and aircrafts) and that if we include information regarding costs involved (for example, crew payroll information and hotels costs, among others), the solutions to the detected problems will be faster to find and less expensive. We also hypothesize that if we use specialized software agents that implement different solutions (heuristic and other solutions based in operations research models and artificial intelligence algorithms), to the same problem, the robustness of the system will increase. Finally, we believe that the inclusion of some kind of learning mechanism that learns from previous utilization of crew members will improve the solutions quality. Extending that learning mechanism to learn each crew member profile, and applying that knowledge for generating future schedules, the management of that expensive resource will be much more efficient and the level of satisfaction of each crew member will increase. We also present a real case study taken from TAP Portugal AOCC, where a crew recovery problem is solved using the MAS. Computational results using a real airline schedule are presented, including a comparison with a solution for the same problem found by the human operators in the Airline Operations Control Center. We show that, even for simple problems, and when comparing with solutions found by human operators in the case of this airline company, it is possible to find valid solutions, in less time and with a smaller cost. In this thesis we also show how we complement the GAIA methodology in order to better analyze and design the proposed MAS for the AOCC. Besides showing the rationale behind the analysis, design and implementation of our system, we also present how we mapped the abstractions used in agent-oriented design to specific constructs in JADE. The advantages of using a goal-oriented early requirements analysis and its influence on subsequent phases of analysis and design are also presented. Finally, we also propose UML 2.0 diagrams at several different levels for representation of GAIA deliverables, like organizational structure, role and interaction model, agent and service model.

Nesta dissertação estuda-se o problema do ensino e da falta de acessibilidade dos documentos com conteúdos matemáticos na Internet por parte de pessoas com necessidades especiais, nomeadamente cegos e amblíopes. A solução proposta nesta dissertação baseia-se na análise, interpretação e conversão de documentos com fórmulas matemáticas em MathML para uma forma escrita por extenso, sendo posteriormente lida com recurso a um conversor texto-fala. Foram desenvolvidas três aplicações: AudioMathENGINE, AudioMathGUI e AudioMathWEB. AudioMathENGINE consiste num motor de análise, interpretação e conversão de documentos com conteúdos matemáticos, e que possui módulos de processamento para: numerais, abreviações, acrónimos, referências de rede, assim como, reconhecimento automático dos elementos a converter, interpretação e conversão de expressões matemáticas, e implementação de mecanismos de navegação nas mesmas. AudioMathGUI consiste numa aplicação gráfica que permite a aplicação do motor de análise, interpretação e conversão de expressões matemáticas, assim como a demonstração de um mecanismo de navegação contextualizado das fórmulas. AudioMathWEB consiste num serviço público on-line de conversão de documentos com MathML, que se encontra disponível no sítio web da tese. Neste trabalho apresenta-se também um estudo detalhado sobre a prosódia matemática e a forma como os humanos lêem e entendem a leitura das expressões matemáticas. Ao longo da dissertação são apresentados resultados de trabalhos de pesquisa em diversas áreas, incluindo: engenharia, psicologia, matemática e linguística, com a finalidade de adquirir conhecimentos, conceitos e teorias, que permitem escolher as tecnologias e técnicas mais adequadas à concretização deste trabalho. O trabalho de dissertação termina com um conjunto de testes objectivos e subjectivos para a determinação da qualidade dos resultados obtidos; assim como um conjunto de conclusões sobre esses mesmos resultados. Mais informações sobre a dissertação, incluindo publicações e um serviço público de conversão de MathML, encontram-se disponíveis no sítio web da tese em: http://lpf-esi.fe.up.pt/~audiomath. / This dissertation focus itself the problem of teaching and the lack of accessibility in documents with mathematical contents over the Internet, aiming people with several types of visual impairment, like blindness. The proposed solution in this thesis consists in the analysis, interpretation and conversion of documents containing mathematical formulae in MathML into a full written form, prepared to be read by a text-to-speech engine later on. Three applications have been mainly developed: AudioMathENGINE, AudioMathGUI and AudioMathWEB. AudioMathENGINE is the engine responsible for the analysis, interpretation and conversion of documents with mathematical contents. This engine includes processing modules for: numerals, abbreviations, acronyms, network references, and also, automatic recognition of certain elements to be converted, interpretation and conversion of mathematical expressions, and the implementation of a navigation mechanism for the existing mathematical expressions. AudioMathGUI is a graphical user interface that allows the usage of the analysis, interpretation and conversion engine, and also the demonstration of the contextualized navigation mechanism for the mathematical expressions. AudioMathWEB consists in a public on-line service, available on the thesis website, which converts documents with MathML. On this thesis a detailed study is presented concerning math prosody and the way humans read and perceive mathematical expressions. Along this dissertation several research results are presented in numerous areas, including: engineering, psychology, mathematics and linguistics, with the aim of acquiring knowledge, concepts and theories that guided in choosing technologies and techniques that are more adequate to this work's implementation. The dissertation work ends with a set of objective and subjective tests about the quality of results; as well as a set of conclusions concerning these same results. More information about the thesis, including publications and the public on-line conversion service of MathML, is available in the thesis website at: http://lpf-esi.fe.up.pt/~audiomath.

Airline companies make a huge effort to maximize their revenue while keeping their costs at a minimum. This is not an easy task and, because of that, airline companies invest in tools that allow to optimize their operational schedule. Unfortunately, any operational plan has a strong probability of being affected, not only by large disruptions like the one that happened in April 2010 due to the eruption of the Iceland Eyjafjallajökull volcano but, more frequently, by smaller daily disruptions caused by bad weather, aircraft malfunctions and crew absenteeism, for example. These disruptions affect the original schedule plan, delaying the flights, and cause what is called an Irregular Operation. Studies have estimated that irregular operations can cost between 2% and 3% of the airlines annual revenues and that a better recovery process could result in cost reductions of at least 20% of its irregular operations. In this thesis, we have studied the AOCC of TAP Portugal as well as the work of other researchers in this field in order to propose a distributed and decentralized general approach to integrated and dynamic disruption management in airline operations control, based on the Multi-Agent System (MAS) paradigm. This is one of the main contributions of our work.The approach is distributed because it allows the functional, spatial and physical distribution of the intervening agent roles and the environment (i.e., resources available); it is decentralized because some decisions are made in different nodes of the agents network; it is integrated because it includes the main dimensions of the problem: aircraft, crew and passengers; and it is dynamic because, in real time, several agents are performing in the environment, reacting to constant change. Although we use the TAP Portugals AOCC as a case study, our work was performed with an out-of-the-box thinking. By out-of-the-box thinking we mean trying to think beyond the requirements of the specific problem we are solving as of this moment in time, exploring divergent directions and involving a variety of aspects that, at this moment in time might not be relevant but, in the future, might be an asset. We propose (and this is another one of the main contributions of our work) a negotiation protocol called Generic Q-Negotiation (GQN) to be used as a decision mechanism in the disruption management process. This protocol has characteristics that are beyond what we need to solve the problem as it is today. However, these characteristics, besides solving the problem as we know it today, allow it to be applied to different scenarios that may arise in the future, either for the same application domain or to different application domains that share similar characteristics. The same line of thinking was followed in the other contributions of our work, including the proposal of an Agent-Oriented Software Engineering (AOSE) methodology called PORTO, which resulted from the use and improvement of other methodologies. Based on our MAS-based approach and on the GQN protocol, we have performed several experiments, comparing the results with those of the manual process followed by the AOCC operators at TAP and with an automated process that implements the typical sequential approach followed by the AOCCs. The results show that our proposal, not only corroborates existing studies regarding the possible cost reductions that could result from a better disruption management process but, also, gives the possibility of reaching solutions that balance the utility of the three dimensions of the problem: aircraft, crew and passengers.

Este trabalho apresenta um estudo sobre o problema de substituição de linhas de cache em microprocessadores. Inspirado no conceito de Entropia da Informação proposto em 1948 por Claude E. Shannon, este trabalho propõe uma nova heurística de substituição de linhas de cache. Seu objetivo é capturar e explorar melhor a localidade de referência dos programas e diminuir a taxa de miss rate durante a execução dos programas. O algoritmo proposto, Entropy, utiliza a heurística de entropia da informação para estimar as chances de uma linha ou bloco de cache ser referenciado após ter sido carregado na cache. Uma nova função de decaimento de entropia foi introduzida no algoritmo, otimizando seu funcionamento. Dentre os resultados obtidos, o Entropy conseguiu reduzir em até 50,41% o miss rate em relação ao algoritmo LRU. O trabalho propõe, ainda, uma implementação em hardware com complexidade e custo computacional comparáveis aos do algoritmo LRU. Para uma memória cache de segundo nível com 2-Mbytes e 8-way associative, a área adicional requerida é da ordem de 0,61% de bits adicionais. O algoritmo proposto foi simulado no SimpleScalar e comparado com o algoritmo LRU utilizando-se os benchmarks SPEC CPU2000. / This work presents a study about cache line replacement problem for microprocessors. Inspired in the Information Entropy concept stated by Claude E. Shannon in 1948, this work proposes a novel heuristic to replace cache lines in microprocessors. The major goal is to capture the referential locality of programs and to reduce the miss rate for cache access during programs execution. The proposed algorithm, Entropy, employs that new entropy heuristic to estimate the chances of a cache line to be referenced after it has been loaded into cache. A novel decay function has been introduced to optimize its operation. Results show that Entropy could reduce miss rate up to 50.41% in comparison to LRU. This work also proposes a hardware implementation which keeps computation and complexity costs comparable to the most employed algorithm, LRU. To a 2-Mbytes and 8-way associative cache memory, the required storage area is 0.61% of the cache size. The Entropy algorithm was simulated using SimpleScalar ISA simulator and compared to LRU using SPEC CPU2000 benchmark programs.

Este trabalho apresenta um estudo sobre o problema de substituição de linhas de cache em microprocessadores. Inspirado no conceito de Entropia da Informação proposto em 1948 por Claude E. Shannon, este trabalho propõe uma nova heurística de substituição de linhas de cache. Seu objetivo é capturar e explorar melhor a localidade de referência dos programas e diminuir a taxa de miss rate durante a execução dos programas. O algoritmo proposto, Entropy, utiliza a heurística de entropia da informação para estimar as chances de uma linha ou bloco de cache ser referenciado após ter sido carregado na cache. Uma nova função de decaimento de entropia foi introduzida no algoritmo, otimizando seu funcionamento. Dentre os resultados obtidos, o Entropy conseguiu reduzir em até 50,41% o miss rate em relação ao algoritmo LRU. O trabalho propõe, ainda, uma implementação em hardware com complexidade e custo computacional comparáveis aos do algoritmo LRU. Para uma memória cache de segundo nível com 2-Mbytes e 8-way associative, a área adicional requerida é da ordem de 0,61% de bits adicionais. O algoritmo proposto foi simulado no SimpleScalar e comparado com o algoritmo LRU utilizando-se os benchmarks SPEC CPU2000. / This work presents a study about cache line replacement problem for microprocessors. Inspired in the Information Entropy concept stated by Claude E. Shannon in 1948, this work proposes a novel heuristic to replace cache lines in microprocessors. The major goal is to capture the referential locality of programs and to reduce the miss rate for cache access during programs execution. The proposed algorithm, Entropy, employs that new entropy heuristic to estimate the chances of a cache line to be referenced after it has been loaded into cache. A novel decay function has been introduced to optimize its operation. Results show that Entropy could reduce miss rate up to 50.41% in comparison to LRU. This work also proposes a hardware implementation which keeps computation and complexity costs comparable to the most employed algorithm, LRU. To a 2-Mbytes and 8-way associative cache memory, the required storage area is 0.61% of the cache size. The Entropy algorithm was simulated using SimpleScalar ISA simulator and compared to LRU using SPEC CPU2000 benchmark programs.