Task Assignment Algorithms for Heterogeneous Multiprocessors

Consider the problem of assigning implicit-deadline sporadic tasks on a heterogeneous multiprocessor platform comprising a constant number (denoted by t) of distinct types of processors—such a platform is referred to as a t-type platform. We present two algorithms, LPGIM and LPGNM, each providing the following guarantee. For a given t-type platform and a task set, if there exists a task assignment such that tasks can be scheduled to meet their deadlines by allowing them to migrate only between processors of the same type (intra-migrative), then: (i) LPGIM succeeds in finding such an assignment where the same restriction on task migration applies (intra-migrative) but given a platform in which only one processor of each type is 1 + α × t-1/t times faster and (ii) LPGNM succeeds in finding a task assignment where tasks are not allowed to migrate between processors (non-migrative) but given a platform in which every processor is 1 + α times faster. The parameter α is a property of the task set; it is the maximum of all the task utilizations that are no greater than one. To the best of our knowledge, for t-type heterogeneous multiprocessors: (i) for the problem of intra-migrative task assignment, no previous algorithm exists with a proven bound and hence our algorithm, LPGIM, is the first of its kind and (ii) for the problem of non-migrative task assignment, our algorithm, LPGNM, has superior performance compared to state-of-the-art.

Provably Good Task Assignment for Two-Type Heterogeneous Multiprocessors Using Cutting Planes

Consider scheduling of real-time tasks on a multiprocessor where migration is forbidden. Specifically, consider the problem of determining a task-to-processor assignment for a given collection of implicit-deadline sporadic tasks upon a multiprocessor platform in which there are two distinct types of processors. For this problem, we propose a new algorithm, LPC (task assignment based on solving a Linear Program with Cutting planes). The algorithm offers the following guarantee: for a given task set and a platform, if there exists a feasible task-to-processor assignment, then LPC succeeds in finding such a feasible task-to-processor assignment as well but on a platform in which each processor is 1.5 × faster and has three additional processors. For systems with a large number of processors, LPC has a better approximation ratio than state-of-the-art algorithms. To the best of our knowledge, this is the first work that develops a provably good real-time task assignment algorithm using cutting planes.

NoC contention analysis using a branch-and-prune algorithm

“Many-core” systems based on a Network-on-Chip (NoC) architecture offer various opportunities in terms of performance and computing capabilities, but at the same time they pose many challenges for the deployment of real-time systems, which must fulfill specific timing requirements at runtime. It is therefore essential to identify, at design time, the parameters that have an impact on the execution time of the tasks deployed on these systems and the upper bounds on the other key parameters. The focus of this work is to determine an upper bound on the traversal time of a packet when it is transmitted over the NoC infrastructure. Towards this aim, we first identify and explore some limitations in the existing recursive-calculus-based approaches to compute the Worst-Case Traversal Time (WCTT) of a packet. Then, we extend the existing model by integrating the characteristics of the tasks that generate the packets. For this extended model, we propose an algorithm called “Branch and Prune” (BP). Our proposed method provides tighter and safe estimates than the existing recursive-calculus-based approaches. Finally, we introduce a more general approach, namely “Branch, Prune and Collapse” (BPC) which offers a configurable parameter that provides a flexible trade-off between the computational complexity and the tightness of the computed estimate. The recursive-calculus methods and BP present two special cases of BPC when a trade-off parameter is 1 or ∞, respectively. Through simulations, we analyze this trade-off, reason about the implications of certain choices, and also provide some case studies to observe the impact of task parameters on the WCTT estimates.

Step count algorithm adapted to indoor localization

This paper presents a step count algorithm designed to work in real-time using low computational power. This proposal is our first step for the development of an indoor navigation system, based on Pedestrian Dead Reckoning (PDR). We present two approaches to solve this problem and compare them based in their error on step counting, as well as, the capability of their use in a real time system.

Traveled Distance Estimation Algorithm for Indoor Localization

This paper presents an ankle mounted Inertial Navigation System (INS) used to estimate the distance traveled by a pedestrian. This distance is estimated by the number of steps given by the user. The proposed method is based on force sensors to enhance the results obtained from an INS. Experimental results have shown that, depending on the step frequency, the traveled distance error varies between 2.7% and 5.6%.

Resistência ao fogo de alvenarias sem função estrutural

Um incêndio é algo difícil de prever, assim como a sua consequência nos elementos de construção. Dessa forma, ao longo das últimas décadas, os elementos de construção têm sido alvo de diversos estudos a fim de avaliar os seus comportamentos quando solicitados em situação de incêndio. O International Building Code (IBC) descreve um método de cálculo analítico para a determinação da resistência ao fogo dos elementos da construção de acordo com os procedimentos de teste estabelecidos na ASTM E119 (Standard Test Methods for Fire Tests of Building Construction and Materials). Nesta dissertação foi feita uma análise desse método, que se mostrou inadequado para estimar a resistência ao fogo das alvenarias, sem função estrutural, de blocos cerâmicos e blocos de betão, uma vez que despreza qualquer efeito do ar no interior das mesmas. No seguimento desta análise, é apresentado um desenvolvimento do método descrito tendo em conta o efeito do ar. Depois de uma análise aos vários tipos de blocos cerâmicos e de betão com diferentes dimensões e geometrias foi possível obter uma relação entre a espessura equivalente de ar existente num bloco e a sua respectiva resistência ao fogo, de modo a serem obtidos os valores descritos na normalização existente. O efeito do ar mostrou ter uma maior influência na resistência ao fogo nas alvenarias constituídas por blocos cerâmicos de furação vertical, já que a sua geometria caracterizada por um elevado número de pequenos alvéolos contribui para o aumento do isolamento térmico, e consequentemente da sua resistência ao fogo. Nas alvenarias rebocadas os valores da resistência ao fogo aumentam cerca de 50%, quando revestidos com argamassa de cimento, e 70% quando revestidos com gesso, logo, o emprego de revestimentos representam uma boa alternativa para aumentar a resistência ao fogo.

Domestic Consumption Simulation and Management Using a Continuous Consumption Management and Optimization Algorithm

The recent changes concerning the consumers’ active participation in the efficient management of load devices for one’s own interest and for the interest of the network operator, namely in the context of demand response, leads to the need for improved algorithms and tools. A continuous consumption optimization algorithm has been improved in order to better manage the shifted demand. It has been done in a simulation and user-interaction tool capable of being integrated in a multi-agent smart grid simulator already developed, and also capable of integrating several optimization algorithms to manage real and simulated loads. The case study of this paper enhances the advantages of the proposed algorithm and the benefits of using the developed simulation and user interaction tool.

A Learning Algorithm and System Approach to Address Exceptional Events in Domestic Consumption Management

The integration of the Smart Grid concept into the electric grid brings to the need for an active participation of small and medium players. This active participation can be achieved using decentralized decisions, in which the end consumer can manage loads regarding the Smart Grid needs. The management of loads must handle the users’ preferences, wills and needs. However, the users’ preferences, wills and needs can suffer changes when faced with exceptional events. This paper proposes the integration of exceptional events into the SCADA House Intelligent Management (SHIM) system developed by the authors, to handle machine learning issues in the domestic consumption context. An illustrative application and learning case study is provided in this paper.

Análise dinâmica de composições musicais

A composição musical é um tema de muito interesse para a computação evolucionária dentro da área da inteligência artificial. É uma área que tem sofrido vários desenvolvimentos ao longo dos últimos anos pois o interesse em que hajam computadores que façam obras musicais é deveras aliciante. Este trabalho tem por objectivo realizar mais um passo nesse sentido. Assim, foi desenvolvida uma aplicação informática que realiza composições musicais de dois géneros distintos: Músicas Infantis e Músicas Blues. A aplicação foi implementada com recurso aos Algoritmos Genéticos, que são os algoritmos evolucionários mais populares da área da computação evolucionária. O trabalho foi estruturado em duas fases de desenvolvimento. Na primeira fase, realizou-se um levantamento estatístico sobre as características específicas de cada um dos géneros musicais. Analisaram-se quinze músicas de cada género musical, com o intuito de se chegar a uma proporção do uso que cada nota tem em cada um dos casos. Na segunda fase, desenvolveu-se o software que compõe as músicas com implementação de um algoritmo genético. Além disso, foi também desenvolvida uma interface gráfica que permite ao utilizador a escolha do género musical que pretende compor. O algoritmo genético começa por gerar uma população inicial de potenciais soluções de acordo com a escolha do utilizador, realizando, de seguida, o ciclo que caracteriza o algoritmo genético. A população inicial é constituída por soluções que seguem as regras que foram implementadas de acordo com os dados recolhidos ao longo da primeira fase. Foi também implementada uma interface de avaliação, através da qual, o utilizador pode ouvir cada uma das músicas para posterior avaliação em termos de fitness. O estado de evolução do algoritmo é apresentado, numa segunda interface, a qual facilita a clareza e justiça na avaliação ao longo de todo o processo. Esta última apresenta informação sobre a média das fitness da geração anterior e actual, sendo assim possível ter uma noção da evolução do algoritmo, no sentido de se obterem resultados satisfatórios no que diz respeito às composições musicais.

Sistema de apoio ao utilizador de transportes públicos

Nos dias de hoje usar o transporte público para nos deslocarmos de uma determinada origem para um determinado destino é uma realidade na vida da maioria das pessoas. Muitas destas deslocações fazem parte da rotina diária do cidadão, que depende destes transportes para as suas atividades do dia-a-dia. Nos últimos anos, o número de cidadãos que usa os transportes públicos como meio de deslocação tem vindo a aumentar consideravelmente. Contudo, a maioria dos operadores de transportes públicos pecam pela falta de pontualidade dos seus serviços, e pela falta de informação disponível ao cidadão acerca dos horários dos mesmos em tempo real. Tendo este problema em conta, foi desenvolvida uma solução capaz de realizar uma previsão do tempo de chegada de um transporte público, ao longo de todo o seu serviço. Previsão essa que é atualizada ao longo do percurso de forma a reduzir a margem de erro da informação apresentada. Com esta informação o cidadão pode planear melhor o seu dia e decidir qual é a melhor altura para se deslocar para a paragem, evitando ao máximo a perda de tempo à espera do seu transporte público. A solução final foi desenvolvida com a ajuda da empresa BEWARE e teve como objetivo a criação de uma aplicação web capaz de apresentar os tempos de espera dos autocarros em diferentes tipos de vista, bem como o acompanhamento do mesmo ao longo do percurso. Toda a informação utilizada na aplicação web foi criada por dois serviços de apoio que efetuam o controlo do autocarro ao longo do percurso, bem como os cálculos da previsão dos tempos de espera. O projeto foi dividido em quatro constituintes que foram repetidas durante o desenvolvimento da solução. A primeira constou na análise do problema, no levantamento e definição dos requisitos. A segunda incluiu o desenvolvimento de um algoritmo capaz de validar a posição do autocarro ao longo do seu percurso, detetando a paragem onde este se encontra e a hora de chegada à mesma. A terceira abrangeu o desenvolvimento de um algoritmo capaz de prever o tempo de chegada de um autocarro às paragens definidas na sua rota, recorrendo ao histórico de viagens realizadas anteriormente. A quarta consistiu no desenvolvimento da aplicação web, implementando todas as funcionalidades necessárias para que a aplicação consiga realizar o acompanhamento do autocarro no percurso, a consulta dos tempos de chegada e da previsão dos tempos às paragens seguintes recorrendo a três tipos de vistas diferentes, e a possibilidade de agendar notificações de forma a receber no email as previsões dos tempos de chegada nos dias e horas mais significativos para o utilizador.

Recycling old screen-printed electrodes with newly designed plastic antibodies on the wall of carbon nanotubes as sensory element for in situ detection of bacterial toxins in water

Using low cost portable devices that enable a single analytical step for screening environmental contaminants is today a demanding issue. This concept is here tried out by recycling screen-printed electrodes that were to be disposed of and by choosing as sensory element a low cost material offering specific response for an environmental contaminant. Microcystins (MCs) were used as target analyte, for being dangerous toxins produced by cyanobacteria released into water bodies. The sensory element was a plastic antibody designed by surface imprinting with carefully selected monomers to ensure a specific response. These were designed on the wall of carbon nanotubes, taking advantage of their exceptional electrical properties. The stereochemical ability of the sensory material to detect MCs was checked by preparing blank materials where the imprinting stage was made without the template molecule. The novel sensory material for MCs was introduced in a polymeric matrix and evaluated against potentiometric measurements. Nernstian response was observed from 7.24 × 10−10 to 1.28 × 10−9 M in buffer solution (10 mM HEPES, 150 mM NaCl, pH 6.6), with average slopes of −62 mVdecade−1 and detection capabilities below 1 nM. The blank materials were unable to provide a linear response against log(concentration), showing only a slight potential change towards more positive potentials with increasing concentrations (while that ofthe plastic antibodies moved to more negative values), with a maximum rate of +33 mVdecade−1. The sensors presented good selectivity towards sulphate, iron and ammonium ions, and also chloroform and tetrachloroethylene (TCE) and fast response (<20 s). This concept was successfully tested on the analysis of spiked environmental water samples. The sensors were further applied onto recycled chips, comprehending one site for the reference electrode and two sites for different selective membranes, in a biparametric approach for “in situ” analysis.

Efficient Legendre spectral tau algorithm for solving two-sided space-time Caputo fractional advection-dispersion equation

In this paper we present the operational matrices of the left Caputo fractional derivative, right Caputo fractional derivative and Riemann–Liouville fractional integral for shifted Legendre polynomials. We develop an accurate numerical algorithm to solve the two-sided space–time fractional advection–dispersion equation (FADE) based on a spectral shifted Legendre tau (SLT) method in combination with the derived shifted Legendre operational matrices. The fractional derivatives are described in the Caputo sense. We propose a spectral SLT method, both in temporal and spatial discretizations for the two-sided space–time FADE. This technique reduces the two-sided space–time FADE to a system of algebraic equations that simplifies the problem. Numerical results carried out to confirm the spectral accuracy and efficiency of the proposed algorithm. By selecting relatively few Legendre polynomial degrees, we are able to get very accurate approximations, demonstrating the utility of the new approach over other numerical methods.

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.

A multi-objective model for scheduling of short-term incentive-based demand response programs offered by electricity retailers

In this paper, we formulate the electricity retailers’ short-term decision-making problem in a liberalized retail market as a multi-objective optimization model. Retailers with light physical assets, such as generation and storage units in the distribution network, are considered. Following advances in smart grid technologies, electricity retailers are becoming able to employ incentive-based demand response (DR) programs in addition to their physical assets to effectively manage the risks of market price and load variations. In this model, the DR scheduling is performed simultaneously with the dispatch of generation and storage units. The ultimate goal is to find the optimal values of the hourly financial incentives offered to the end-users. The proposed model considers the capacity obligations imposed on retailers by the grid operator. The profit seeking retailer also has the objective to minimize the peak demand to avoid the high capacity charges in form of grid tariffs or penalties. The non-dominated sorting genetic algorithm II (NSGA-II) is used to solve the multi-objective problem. It is a fast and elitist multi-objective evolutionary algorithm. A case study is solved to illustrate the efficient performance of the proposed methodology. Simulation results show the effectiveness of the model for designing the incentive-based DR programs and indicate the efficiency of NSGA-II in solving the retailers’ multi-objective problem.

Mechanical properties of chemically modified portuguese pinewood

To turn wood into a construction material with enhanced properties, many methods of chemical modification have been developed in the last few decades. In this work, mechanical properties of pine wood were chemically modified, compared and evaluated. Maritime pine wood (Pinus pinaster) was modified with four chemical processes: 1,3-dimethylol-4,5- dihydroxyethyleneurea, N-methylol melamine formaldehyde, tetra-alkoxysilane and wax. The following mechanical properties were assessed experimentally: Modulus of elasticity measured statically, stiffness stabilization efficiency in different climates (30 and 87% of relative humidity), modulus of rupture, work maximum load, impact bending strength, compression, tensile and shear strength at indoor conditions (65% of relative humidity). In both types of active principle of modification, cell wall or lumen fill, no significant changes on the bending stiffness (modulus of elasticity) were found. In the remaining properties analysed significant changes in the modified wood-material took place compared to unmodified wood control: - Cell wall modification was the most effective method to achieve high stiffness stabilization efficiency (up to 60%) and also increased compression strength (up to 230%). However, modulus of rupture, tensile, shear and the impact bending strength were reduced by both resins, but in a varying extent, where the N-methylol melamine formaldehyde endured less reduction than 1,3-dimethylol-4,5-dihydroxyethyleneurea resin. In the latter, reduction up to 60% can take place. - In the lumen fill modification: tetra-alkoxysilane has no effect in the mechanical properties. Although, a slight increase in shear strength parallel to the grain was found. Wax specimens have shown a slight increase in bending strength, compression, tensile and shear strength as well as in the absorption energy capacity.