Task assignment algorithms for two-type heterogeneous multiprocessors

Consider the problem of assigning implicit-deadline sporadic tasks on a heterogeneous multiprocessor platform comprising two different types of processors—such a platform is referred to as two-type platform. We present two low degree polynomial time-complexity algorithms, SA and SA-P, each providing the following guarantee. For a given two-type platform and a task set, if there exists a task assignment such that tasks can be scheduled to meet deadlines by allowing them to migrate only between processors of the same type (intra-migrative), then (i) using SA, it is guaranteed to find such an assignment where the same restriction on task migration applies but given a platform in which processors are 1+α/2 times faster and (ii) SA-P succeeds in finding a task assignment where tasks are not allowed to migrate between processors (non-migrative) but given a platform in which processors are 1+α times faster. The parameter 0<α≤1 is a property of the task set; it is the maximum of all the task utilizations that are no greater than 1. We evaluate average-case performance of both the algorithms by generating task sets randomly and measuring how much faster processors the algorithms need (which is upper bounded by 1+α/2 for SA and 1+α for SA-P) in order to output a feasible task assignment (intra-migrative for SA and non-migrative for SA-P). In our evaluations, for the vast majority of task sets, these algorithms require significantly smaller processor speedup than indicated by their theoretical bounds. Finally, we consider a special case where no task utilization in the given task set can exceed one and for this case, we (re-)prove the performance guarantees of SA and SA-P. We show, for both of the algorithms, that changing the adversary from intra-migrative to a more powerful one, namely fully-migrative, in which tasks can migrate between processors of any type, does not deteriorate the performance guarantees. For this special case, we compare the average-case performance of SA-P and a state-of-the-art algorithm by generating task sets randomly. In our evaluations, SA-P outperforms the state-of-the-art by requiring much smaller processor speedup and by running orders of magnitude faster.

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.

Análise numérica e experimental de um modelo dinâmico da ponte ferroviária de Antuã

Mestrado em Engenharia Civil – Ramo Estruturas

Impact of Distributed Generation in the Transmission System Expansion Planning

In this work, the impact of distributed generation in the transmission expansion planning will be simulated through the performance of an optimization process for three different scenarios: the first without distributed generation, the second with distributed generation equivalent to 1% of the load, and the third with 5% of distributed generation. For modeling the expanding problem the load flow linearized method using genetic algorithms for optimization has been chosen. The test circuit used is a simplification of the south eastern Brazilian electricity system with 46 buses.

Data Mining Approach to support the Generation of Realistic Scenarios for Multi-Agent simulation of Electricity Markets

This paper presents the Realistic Scenarios Generator (RealScen), a tool that processes data from real electricity markets to generate realistic scenarios that enable the modeling of electricity market players’ characteristics and strategic behavior. The proposed tool provides significant advantages to the decision making process in an electricity market environment, especially when coupled with a multi-agent electricity markets simulator. The generation of realistic scenarios is performed using mechanisms for intelligent data analysis, which are based on artificial intelligence and data mining algorithms. These techniques allow the study of realistic scenarios, adapted to the existing markets, and improve the representation of market entities as software agents, enabling a detailed modeling of their profiles and strategies. This work contributes significantly to the understanding of the interactions between the entities acting in electricity markets by increasing the capability and realism of market simulations.

Electricity markets modeling considering complex contracts and aggregators

All over the world, the liberalization of electricity markets, which follows different paradigms, has created new challenges for those involved in this sector. In order to respond to these challenges, electric power systems suffered a significant restructuring in its mode of operation and planning. This restructuring resulted in a considerable increase of the electric sector competitiveness. Particularly, the Ancillary Services (AS) market has been target of constant renovations in its operation mode as it is a targeted market for the trading of services, which have as main objective to ensure the operation of electric power systems with appropriate levels of stability, safety, quality, equity and competitiveness. In this way, with the increasing penetration of distributed energy resources including distributed generation, demand response, storage units and electric vehicles, it is essential to develop new smarter and hierarchical methods of operation of electric power systems. As these resources are mostly connected to the distribution network, it is important to consider the introduction of this kind of resources in AS delivery in order to achieve greater reliability and cost efficiency of electrical power systems operation. The main contribution of this work is the design and development of mechanisms and methodologies of AS market and for energy and AS joint market, considering different management entities of transmission and distribution networks. Several models developed in this work consider the most common AS in the liberalized market environment: Regulation Down; Regulation Up; Spinning Reserve and Non-Spinning Reserve. The presented models consider different rules and ways of operation, such as the division of market by network areas, which allows the congestion management of interconnections between areas; or the ancillary service cascading process, which allows the replacement of AS of superior quality by lower quality of AS, ensuring a better economic performance of the market. A major contribution of this work is the development an innovative methodology of market clearing process to be used in the energy and AS joint market, able to ensure viable and feasible solutions in markets, where there are technical constraints in the transmission network involving its division into areas or regions. The proposed method is based on the determination of Bialek topological factors and considers the contribution of the dispatch for all services of increase of generation (energy, Regulation Up, Spinning and Non-Spinning reserves) in network congestion. The use of Bialek factors in each iteration of the proposed methodology allows limiting the bids in the market while ensuring that the solution is feasible in any context of system operation. Another important contribution of this work is the model of the contribution of distributed energy resources in the ancillary services. In this way, a Virtual Power Player (VPP) is considered in order to aggregate, manage and interact with distributed energy resources. The VPP manages all the agents aggregated, being able to supply AS to the system operator, with the main purpose of participation in electricity market. In order to ensure their participation in the AS, the VPP should have a set of contracts with the agents that include a set of diversified and adapted rules to each kind of distributed resource. All methodologies developed and implemented in this work have been integrated into the MASCEM simulator, which is a simulator based on a multi-agent system that allows to study complex operation of electricity markets. In this way, the developed methodologies allow the simulator to cover more operation contexts of the present and future of the electricity market. In this way, this dissertation offers a huge contribution to the AS market simulation, based on models and mechanisms currently used in several real markets, as well as the introduction of innovative methodologies of market clearing process on the energy and AS joint market. This dissertation presents five case studies; each one consists of multiple scenarios. The first case study illustrates the application of AS market simulation considering several bids of market players. The energy and ancillary services joint market simulation is exposed in the second case study. In the third case study it is developed a comparison between the simulation of the joint market methodology, in which the player bids to the ancillary services is considered by network areas and a reference methodology. The fourth case study presents the simulation of joint market methodology based on Bialek topological distribution factors applied to transmission network with 7 buses managed by a TSO. The last case study presents a joint market model simulation which considers the aggregation of small players to a VPP, as well as complex contracts related to these entities. The case study comprises a distribution network with 33 buses managed by VPP, which comprises several kinds of distributed resources, such as photovoltaic, CHP, fuel cells, wind turbines, biomass, small hydro, municipal solid waste, demand response, and storage units.

Mode-Controlled Data-Flow Modeling of Real-Time Memory Controllers

Accepted in 13th IEEE Symposium on Embedded Systems for Real-Time Multimedia (ESTIMedia 2015), Amsterdam, Netherlands.

Modeling Vegetable Fractals by means of Fractional-order Equations

This paper characterizes four ‘fractal vegetables’: (i) cauliflower (brassica oleracea var. Botrytis); (ii) broccoli (brassica oleracea var. italica); (iii) round cabbage (brassica oleracea var. capitata) and (iv) Brussels sprout (brassica oleracea var. gemmifera), by means of electrical impedance spectroscopy and fractional calculus tools. Experimental data is approximated using fractional-order models and the corresponding parameters are determined with a genetic algorithm. The Havriliak-Negami five-parameter model fits well into the data, demonstrating that classical formulae can constitute simple and reliable models to characterize biological structures.

New Concepts Towards the Synthesis of Digital Circuits Through Genetic Algorithms

This paper analyses the performance of a Genetic Algorithm using two new concepts, namely a static fitness function including a discontinuity measure and a fractional-order dynamic fitness function, for the synthesis of combinational logic circuits. In both cases, experiments reveal superior results in terms of speed and convergence to achieve a solution.

Dynamical Analysis of Non-Repetitive Trajectories in Robotic Manipulation

A new method for the study and optimization of manu«ipulator trajectories is developed. The novel feature resides on the modeling formulation. Standard system desciptions are based on a set of differential equations which, in general, require laborious computations and may be difficult to analyze. Moreover, the derived algorithms are suited to "deterministic" tasks, such as those appearing in a repetitivework, and are not well adapted to a "random" operation that occurs in intelligent systems interacting with a non-structured and changing environment. These facts motivate the development of alternative models based on distinct concepts. The proposed embedding of statistics and Fourier trasnform gives a new perspective towards the calculation and optimization of the robot trajectories in manipulating tasks.

Environmental modeling with precision navigation using ROAZ autonomous surface vehicle

The use of robotic vehicles for environmental modeling is discussed. This paper presents diverse results in autonomous marine missions with the ROAZ autonomous surface vehicle. The vehicle can perform autonomous missions while gathering marine data with high inertial and positioning precision. The underwater world is an, economical and environmental, asset that need new tools to study and preserve it. ROAZ is used in marine environment missions since it can sense and monitor the surface and underwater scenarios. Is equipped with a diverse set of sensors, cameras and underwater sonars that generate 3D environmental models. It is used for study the marine life and possible underwater wrecks that can pollute or be a danger to marine navigation. The 3D model and integration of multibeam and sidescan sonars represent a challenge in nowadays. Adding that it is important that robots can explore an area and make decisions based on their surroundings and goals. Regard that, autonomous robotic systems can relieve human beings of repetitive and dangerous tasks.

Towards a Mobile Three-dimensional Modelling System for Underground Structures

Robotica 2012: 12th International Conference on Autonomous Robot Systems and Competitions April 11, 2012, Guimarães, Portugal

Multi-agent simulation of competitive electricity markets: Autonomous systems cooperation for European market modeling

The electricity market restructuring, and its worldwide evolution into regional and even continental scales, along with the increasing necessity for an adequate integration of renewable energy sources, is resulting in a rising complexity in power systems operation. Several power system simulators have been developed in recent years with the purpose of helping operators, regulators, and involved players to understand and deal with this complex and constantly changing environment. The main contribution of this paper is given by the integration of several electricity market and power system models, respecting to the reality of different countries. This integration is done through the development of an upper ontology which integrates the essential concepts necessary to interpret all the available information. The continuous development of Multi-Agent System for Competitive Electricity Markets platform provides the means for the exemplification of the usefulness of this ontology. A case study using the proposed multi-agent platform is presented, considering a scenario based on real data that simulates the European Electricity Market environment, and comparing its performance using different market mechanisms. The main goal is to demonstrate the advantages that the integration of various market models and simulation platforms have for the study of the electricity markets’ evolution.

Testing Nelder-Mead Based Repulsion Algorithms for Multiple Roots of Nonlinear Systems via a Two-Level Factorial Design of Experiments

This paper addresses the challenging task of computing multiple roots of a system of nonlinear equations. A repulsion algorithm that invokes the Nelder-Mead (N-M) local search method and uses a penalty-type merit function based on the error function, known as 'erf', is presented. In the N-M algorithm context, different strategies are proposed to enhance the quality of the solutions and improve the overall efficiency. The main goal of this paper is to use a two-level factorial design of experiments to analyze the statistical significance of the observed differences in selected performance criteria produced when testing different strategies in the N-M based repulsion algorithm. The main goal of this paper is to use a two-level factorial design of experiments to analyze the statistical significance of the observed differences in selected performance criteria produced when testing different strategies in the N-M based repulsion algorithm.