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.

Concurrent tabling

In the past few years Tabling has emerged as a powerful logic programming model. The integration of concurrent features into the implementation of Tabling systems is demanded by need to use recently developed tabling applications within distributed systems, where a process has to respond concurrently to several requests. The support for sharing of tables among the concurrent threads of a Tabling process is a desirable feature, to allow one of Tabling’s virtues, the re-use of computations by other threads and to allow efficient usage of available memory. However, the incremental completion of tables which are evaluated concurrently is not a trivial problem. In this dissertation we describe the integration of concurrency mechanisms, by the way of multi-threading, in a state of the art Tabling and Prolog system, XSB. We begin by reviewing the main concepts for a formal description of tabled computations, called SLG resolution and for the implementation of Tabling under the SLG-WAM, the abstract machine supported by XSB. We describe the different scheduling strategies provided by XSB and introduce some new properties of local scheduling, a scheduling strategy for SLG resolution. We proceed to describe our implementation work by describing the process of integrating multi-threading in a Prolog system supporting Tabling, without addressing the problem of shared tables. We describe the trade-offs and implementation decisions involved. We then describe an optimistic algorithm for the concurrent sharing of completed tables, Shared Completed Tables, which allows the sharing of tables without incurring in deadlocks, under local scheduling. This method relies on the execution properties of local scheduling and includes full support for negation. We provide a theoretical framework and discuss the implementation’s correctness and complexity. After that, we describe amethod for the sharing of tables among threads that allows parallelism in the computation of inter-dependent subgoals, which we name Concurrent Completion. We informally argue for the correctness of Concurrent Completion. We give detailed performance measurements of the multi-threaded XSB systems over a variety of machines and operating systems, for both the Shared Completed Tables and the Concurrent Completion implementations. We focus our measurements inthe overhead over the sequential engine and the scalability of the system. We finish with a comparison of XSB with other multi-threaded Prolog systems and we compare our approach to concurrent tabling with parallel and distributed methods for the evaluation of tabling. Finally, we identify future research directions.

A high level e-maintenance architecture to support on-site teams

Emergent architectures and paradigms targeting reconfigurable manufacturing systems increasingly rely on intelligent modules to maximize the robustness and responsiveness of modern installations. Although intelligent behaviour significantly minimizes the occurrence of faults and breakdowns it does not exclude them nor can prevent equipment’s normal wear. Adequate maintenance is fundamental to extend equipments’ life cycle. It is of major importance the ability of each intelligent device to take an active role in maintenance support. Further this paradigm shift towards “embedded intelligence”, supported by cross platform technologies, induces relevant organizational and functional changes on local maintenance teams. On the one hand, the possibility of outsourcing maintenance activities, with the warranty of a timely response, through the use of pervasive networking technologies and, on the other hand, the optimization of local maintenance staff are some examples of how IT is changing the scenario in maintenance. The concept of e-maintenance is, in this context, emerging as a new discipline with defined socio-economic challenges. This paper proposes a high level maintenance architecture supporting maintenance teams’ management and offering contextualized operational support. All the functionalities hosted by the architecture are offered to the remaining system as network services. Any intelligent module, implementing the services’ interface, can report diagnostic, prognostic and maintenance recommendations that enable the core of the platform to decide on the best course of action.

Integrando problem frames com aspectos

Dissertação apresentada na Faculdade de Ciências e Tecnologia da Universidade Nova de Lisboa para obtenção do grau de Mestre em Engenharia Informática

A new approach to the initial value problem

5th Portuguese Conference on Automatic Control, September, 5-7, 2002, Aveiro, Portugal

Study of a 9th century silver earrings set from Mikulčice: corrosion, conservation and maintenance

Dissertação apresentada na Faculdade de Ciências e Tecnologia da Universidade Nova de Lisboa para obtenção do grau de Mestre em Conservação e Restauro

A comparative study between centralization and decentralization of diagnostic reasoning in EPS

Dissertação apresentada na Faculdade de Ciências e Tecnologia da Universidade Nova de Lisboa de Lisboa para obtenção do grau de mestre em Engenharia Electrotécnica e de Computadores

Probabilistic maintenance and optimization strategies for deteriorating civil infrastructures

In developed countries, civil infrastructures are one of the most significant investments of governments, corporations, and individuals. Among these, transportation infrastructures, including highways, bridges, airports, and ports, are of huge importance, both economical and social. Most developed countries have built a fairly complete network of highways to fit their needs. As a result, the required investment in building new highways has diminished during the last decade, and should be further reduced in the following years. On the other hand, significant structural deteriorations have been detected in transportation networks, and a huge investment is necessary to keep these infrastructures safe and serviceable. Due to the significant importance of bridges in the serviceability of highway networks, maintenance of these structures plays a major role. In this paper, recent progress in probabilistic maintenance and optimization strategies for deteriorating civil infrastructures with emphasis on bridges is summarized. A novel model including interaction between structural safety analysis,through the safety index, and visual inspections and non destructive tests, through the condition index, is presented. Single objective optimization techniques leading to maintenance strategies associated with minimum expected cumulative cost and acceptable levels of condition and safety are presented. Furthermore, multi-objective optimization is used to simultaneously consider several performance indicators such as safety, condition, and cumulative cost. Realistic examples of the application of some of these techniques and strategies are also presented.

A framework for scientific computing with GPUs

Dissertação para obtenção do Grau de Mestre em Engenharia Informática

Modeling assembly program with constraints. A contribution to WCET problem

Dissertação para obtenção do Grau de Mestre em Lógica Computacional

GIS capacity building for risk management to help developing countries:Case of climate change problem in Amhara rural region (Ethiopia)

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

Aircraft Engines Maintenance Costs and Reliability: An Appraisal of the Decision Process to Remove an Engine for a Shop Visit Aiming at Minimum Maintenance Unit Cost

Dissertação apresentada como requisito parcial para obtenção do grau de Mestre em Estatística e Gestão de Informação.

Repair mortars for rammed earth constructions

Proceedingsof the XII DBMC – 12th International Conference on Durability of Building Materials and Components, Vol.2, Porto, FEUP, March 2011, p.689-696

Long-term behaviour of railway transitions under dynamic loading application to soft soil sites

Dissertação para obtenção do Grau de Doutor em Engenharia Civil

Implementação, documentação e avaliação da aplicação de Lean Maintenance no Sistema de Armas Epsilon

Dissertação para obtenção do Grau de Mestre em Engenharia Mecânica