Unified overhead-aware schedulability analysis for slot-based task-splitting

Hard real- time multiprocessor scheduling has seen, in recent years, the flourishing of semi-partitioned scheduling algorithms. This category of scheduling schemes combines elements of partitioned and global scheduling for the purposes of achieving efficient utilization of the system’s processing resources with strong schedulability guarantees and with low dispatching overheads. The sub-class of slot-based “task-splitting” scheduling algorithms, in particular, offers very good trade-offs between schedulability guarantees (in the form of high utilization bounds) and the number of preemptions/migrations involved. However, so far there did not exist unified scheduling theory for such algorithms; each one was formulated in its own accompanying analysis. This article changes this fragmented landscape by formulating a more unified schedulability theory covering the two state-of-the-art slot-based semi-partitioned algorithms, S-EKG and NPS-F (both fixed job-priority based). This new theory is based on exact schedulability tests, thus also overcoming many sources of pessimism in existing analysis. In turn, since schedulability testing guides the task assignment under the schemes in consideration, we also formulate an improved task assignment procedure. As the other main contribution of this article, and as a response to the fact that many unrealistic assumptions, present in the original theory, tend to undermine the theoretical potential of such scheduling schemes, we identified and modelled into the new analysis all overheads incurred by the algorithms in consideration. The outcome is a new overhead-aware schedulability analysis that permits increased efficiency and reliability. The merits of this new theory are evaluated by an extensive set of experiments.

Dynamic cluster scheduling for cluster-tree WSNs

While Cluster-Tree network topologies look promising for WSN applications with timeliness and energy-efficiency requirements, we are yet to witness its adoption in commercial and academic solutions. One of the arguments that hinder the use of these topologies concerns the lack of flexibility in adapting to changes in the network, such as in traffic flows. This paper presents a solution to enable these networks with the ability to self-adapt their clusters’ duty-cycle and scheduling, to provide increased quality of service to multiple traffic flows. Importantly, our approach enables a network to change its cluster scheduling without requiring long inaccessibility times or the re-association of the nodes. We show how to apply our methodology to the case of IEEE 802.15.4/ZigBee cluster-tree WSNs without significant changes to the protocol. Finally, we analyze and demonstrate the validity of our methodology through a comprehensive simulation and experimental validation using commercially available technology on a Structural Health Monitoring application scenario.

Compositional multiprocessor scheduling: the GMPR interface

Composition is a practice of key importance in software engineering. When real-time applications are composed, it is necessary that their timing properties (such as meeting the deadlines) are guaranteed. The composition is performed by establishing an interface between the application and the physical platform. Such an interface typically contains information about the amount of computing capacity needed by the application. For multiprocessor platforms, the interface should also present information about the degree of parallelism. Several interface proposals have recently been put forward in various research works. However, those interfaces are either too complex to be handled or too pessimistic. In this paper we propose the generalized multiprocessor periodic resource model (GMPR) that is strictly superior to the MPR model without requiring a too detailed description. We then derive a method to compute the interface from the application specification. This method has been implemented in Matlab routines that are publicly available.

Plataforma de gestão de guias de programação de TV digital

Com o consumismo de mais variedade e qualidade de informação, assim como, produtos interativos, surgiu a necessidade de apresentar mais conteúdos, para além da programação de televisão comum. Com os avanços tecnológicos ligados à indústria da televisão e sua distribuição nos lares portugueses pelos operadores de TV, a quantidade de oferta de canais deixou de ser um foco, passando a ser prioritário a melhoria da experiência do cliente. Com a introdução de novas funcionalidades nas caixas recetoras de sinais de transmissão de canais, como por exemplo, a capacidade de apresentar informações adicionais sobre os programas, desde da sua apresentação em modo trailer até ao elenco detalhado que o compõe, os clientes podem ter uma nova experiência de interação com os serviços de TV. A funcionalidade de gravação agendada de programas levou ao próximo ponto de melhoria de experiência do cliente. As gravações que resultavam em programas indevidamente cortados, quer no seu início quer no seu fim, foi um dos motivos que levou os operadores de TV a procurarem um melhor serviço de gestão de guias de programação digitais. A InfoPortugal, entidade detentora do seguinte projeto e EPG Provider de algumas operadoras de TV nacionais, viu-se obrigada a atualizar os seu sistemas de distribuição de conteúdos, para responder à evolução dos requisitos dos seus clientes.

An integer programming framework for sequencing cutting patterns based on interval graph completion

We derived a framework in integer programming, based on the properties of a linear ordering of the vertices in interval graphs, that acts as an edge completion model for obtaining interval graphs. This model can be applied to problems of sequencing cutting patterns, namely the minimization of open stacks problem (MOSP). By making small modifications in the objective function and using only some of the inequalities, the MOSP model is applied to another pattern sequencing problem that aims to minimize, not only the number of stacks, but also the order spread (the minimization of the stack occupation problem), and the model is tested.

An integer programming model for the minimum interval graph completion problem

The minimum interval graph completion problem consists of, given a graph G = ( V, E ), finding a supergraph H = ( V, E ∪ F ) that is an interval graph, while adding the least number of edges |F| . We present an integer programming formulation for solving the minimum interval graph completion problem recurring to a characteri- zation of interval graphs that produces a linear ordering of the maximal cliques of the solution graph.

Optimal scheduling of aircrafts’ engines repair process

We address a real world scheduling problem concerning the repair process of aircrafts’ engines by TAP - Maintenance & Engineering (TAP-ME). TAP-ME is the maintenance, repair and overhaul organization of TAP Portugal, Portugal’s leading airline, which employs about 4000 persons to provide maintenance and engineering services in aircraft, engines and components. TAP-ME is aiming to optimize its maintenance services, focusing on the reduction of the engines repair turnaround time.

Increase of the Delivered Power Probability in Distribution Networks using Pareto DC Programming

A methodology to increase the probability of delivering power to any load point through the identification of new investments in distribution network components is proposed in this paper. The method minimizes the investment cost as well as the cost of energy not supplied in the network. A DC optimization model based on mixed integer non-linear programming is developed considering the Pareto front technique in order to identify the adequate investments in distribution networks components which allow increasing the probability of delivering power for any customer in the distribution system at the minimum possible cost for the system operator, while minimizing the energy not supplied cost. Thus, a multi-objective problem is formulated. To illustrate the application of the proposed methodology, the paper includes a case study which considers a 180 bus distribution network

Constrained Consumption Shifting Management in the Distributed Energy Resources Scheduling Considering Demand Response

Demand response concept has been gaining increasing importance while the success of several recent implementations makes this resource benefits unquestionable. This happens in a power systems operation environment that also considers an intensive use of distributed generation. However, more adequate approaches and models are needed in order to address the small size consumers and producers aggregation, while taking into account these resources goals. The present paper focuses on the demand response programs and distributed generation resources management by a Virtual Power Player that optimally aims to minimize its operation costs taking the consumption shifting constraints into account. The impact of the consumption shifting in the distributed generation resources schedule is also considered. The methodology is applied to three scenarios based on 218 consumers and 4 types of distributed generation, in a time frame of 96 periods.

Distributed energy resources scheduling considering real-time resources forecast

Energy resource scheduling is becoming increasingly important, such as the use of more distributed generators and electric vehicles connected to the distribution network. This paper proposes a methodology to be used by Virtual Power Players (VPPs), regarding the energy resource scheduling in smart grids and considering day-ahead, hour-ahead and realtime time horizons. This method considers that energy resources are managed by a VPP which establishes contracts with their owners. The full AC power flow calculation included in the model takes into account network constraints. In this paper, distribution function errors are used to simulate variations between time horizons, and to measure the performance of the proposed methodology. A 33-bus distribution network with large number of distributed resources is used.

Real-time Energy Resource Scheduling considering a Real Portuguese Scenario

The development in power systems and the introduction of decentralized generation and Electric Vehicles (EVs), both connected to distribution networks, represents a major challenge in the planning and operation issues. This new paradigm requires a new energy resources management approach which considers not only the generation, but also the management of loads through demand response programs, energy storage units, EVs and other players in a liberalized electricity markets environment. This paper proposes a methodology to be used by Virtual Power Players (VPPs), concerning the energy resource scheduling in smart grids, considering day-ahead, hour-ahead and real-time scheduling. The case study considers a 33-bus distribution network with high penetration of distributed energy resources. The wind generation profile is based on a real Portuguese wind farm. Four scenarios are presented taking into account 0, 1, 2 and 5 periods (hours or minutes) ahead of the scheduling period in the hour-ahead and realtime scheduling.

Quantum-based Particle Swarm Optimization Application to Studies of Aggregated Consumption Shifting and Generation Scheduling in Smart Grids

Demand response programs and models have been developed and implemented for an improved performance of electricity markets, taking full advantage of smart grids. Studying and addressing the consumers’ flexibility and network operation scenarios makes possible to design improved demand response models and programs. The methodology proposed in the present paper aims to address the definition of demand response programs that consider the demand shifting between periods, regarding the occurrence of multi-period demand response events. The optimization model focuses on minimizing the network and resources operation costs for a Virtual Power Player. Quantum Particle Swarm Optimization has been used in order to obtain the solutions for the optimization model that is applied to a large set of operation scenarios. The implemented case study illustrates the use of the proposed methodology to support the decisions of the Virtual Power Player in what concerns the duration of each demand response event.

A New Heuristic Providing an Effective Initial Solution for a Simulated Annealing approach to Energy Resource Scheduling in Smart Grids

An intensive use of dispersed energy resources is expected for future power systems, including distributed generation, especially based on renewable sources, and electric vehicles. The system operation methods and tool must be adapted to the increased complexity, especially the optimal resource scheduling problem. Therefore, the use of metaheuristics is required to obtain good solutions in a reasonable amount of time. This paper proposes two new heuristics, called naive electric vehicles charge and discharge allocation and generation tournament based on cost, developed to obtain an initial solution to be used in the energy resource scheduling methodology based on simulated annealing previously developed by the authors. The case study considers two scenarios with 1000 and 2000 electric vehicles connected in a distribution network. The proposed heuristics are compared with a deterministic approach and presenting a very small error concerning the objective function with a low execution time for the scenario with 2000 vehicles.

Resource Scheduling in Residential Microgrids Considering Energy Selling to External Players

The operation of distribution networks has been facing changes with the implementation of smart grids and microgrids, and the increasing use of distributed generation. The specific case of distribution networks that accommodate residential buildings, small commerce, and distributed generation as the case of storage and PV generation lead to the concept of microgrids, in the cases that the network is able to operate in islanding mode. The microgrid operator in this context is able to manage the consumption and generation resources, also including demand response programs, obtaining profits from selling electricity to the main network. The present paper proposes a methodology for the energy resource scheduling considering power flow issues and the energy buying and selling from/to the main network in each bus of the microgrid. The case study uses a real distribution network with 25 bus, residential and commercial consumers, PV generation, and storage.

Aplicação de um modelo de programação linear inteira mista (PLIM) na expansão da rede de distribuição de energia elétrica em Angola

Em Angola, apenas cerca de 30% da população tem acesso à energia elétrica, nível que decresce para valores inferiores a 10% em zonas rurais mais remotas. Este problema é agravado pelo facto de, na maioria dos casos, as infraestruturas existentes se encontrarem danificadas ou não acompanharem o desenvolvimento da região. Em particular na capital angolana, Luanda que, sendo a menor província de Angola, é a que regista atualmente a maior densidade populacional. Com uma população de cerca de 5 milhões de habitantes, não só há frequentemente problemas relacionados com a falha do fornecimento de energia elétrica como há ainda uma percentagem considerável de municípios onde a rede elétrica ainda nem sequer chegou. O governo de Angola, no seu esforço de crescimento e aproveitamento das suas enormes potencialidades, definiu o setor energético como um dos fatores críticos para o desenvolvimento sustentável do país, tendo assumido que este é um dos eixos prioritários até 2016. Existem objetivos claros quanto à reabilitação e expansão das infraestruturas do setor elétrico, aumentando a capacidade instalada do país e criando uma rede nacional adequada, com o intuito não só de melhorar a qualidade e fiabilidade da rede já existente como de a aumentar. Este trabalho de dissertação consistiu no levantamento de dados reais relativamente à rede de distribuição de energia elétrica de Luanda, na análise e planeamento do que é mais premente fazer relativamente à sua expansão, na escolha dos locais onde é viável localizar novas subestações, na modelação adequada do problema real e na proposta de uma solução ótima para a expansão da rede existente. Depois de analisados diferentes modelos matemáticos aplicados ao problema de expansão de redes de distribuição de energia elétrica encontrados na literatura, optou-se por um modelo de programação linear inteira mista (PLIM) que se mostrou adequado. Desenvolvido o modelo do problema, o mesmo foi resolvido por recurso a software de otimização Analytic Solver e CPLEX. Como forma de validação dos resultados obtidos, foi implementada a solução de rede no simulador PowerWorld 8.0 OPF, software este que permite a simulação da operação do sistema de trânsito de potências.