The utilization bound of static-priority preemptive partitioned multiprocessor scheduling is 50%

This paper studies static-priority preemptive scheduling on a multiprocessor using partitioned scheduling. We propose a new scheduling algorithm and prove that if the proposed algorithm is used and if less than 50% of the capacity is requested then all deadlines are met. It is known that for every static-priority multiprocessor scheduling algorithm, there is a task set that misses a deadline although the requested capacity is arbitrary close to 50%.

Implementation of a dominance protocol for wireless medium access

Consider the problem of scheduling sporadic message transmission requests with deadlines. For wired channels, this has been achieved successfully using the CAN bus. For wireless channels, researchers have recently proposed a similar solution; a collision-free medium access control (MAC) protocol that implements static-priority scheduling. Unfortunately no implementation has been reported, yet. We implement and evaluate it to find that the implementation indeed is collision-free and prioritized. This allows us to develop schedulability analysis for the implementation. We measure the response times of messages in our implementation and find that our new response-time analysis indeed offers an upper bound on the response times. This enables a new class of wireless real-time systems with timeliness guarantees for sporadic messages and it opens-up a new research area: schedulability analysis for wireless networks.

Collision-free prioritized medium access in the presence of hidden nodes without relying on out-of-band signaling

Consider the problem of sharing a wireless channel between a set of computer nodes. Hidden nodes exist and there is no base station. Each computer node hosts a set of sporadic message streams where a message stream releases messages with real-time deadlines. We propose a collision-free wireless medium access control (MAC) protocol which implements staticpriority scheduling. The MAC protocol allows multiple masters and is fully distributed. It neither relies on synchronized clocks nor out-of-band signaling; it is an adaptation to a wireless channel of the dominance protocol used in the CAN bus. But unlike that protocol, our protocol does not require a node having the ability to receive an incoming bit from the channel while transmitting to the channel. Our protocol has the key feature of not only being prioritized and collision-free but also dealing successfully with hidden nodes. This key feature enables schedulability analysis of sporadic message streams in multihop networks.

Run-time monitoring approach for the shark kernel

Typically common embedded systems are designed with high resource constraints. Static designs are often chosen to address very specific use cases. On contrast, a dynamic design must be used if the system must supply a real-time service where the input may contain factors of indeterminism. Thus, adding new functionality on these systems is often accomplished by higher development time, tests and costs, since new functionality push the system complexity and dynamics to a higher level. Usually, these systems have to adapt themselves to evolving requirements and changing service requests. In this perspective, run-time monitoring of the system behaviour becomes an important requirement, allowing to dynamically capturing the actual scheduling progress and resource utilization. For this to succeed, operating systems need to expose their internal behaviour and state, making it available to the external applications, usually using a run-time monitoring mechanism. However, such mechanism can impose a burden in the system itself if not wisely used. In this paper we explore this problem and propose a framework, which is intended to provide this run-time mechanism whilst achieving code separation, run-time efficiency and flexibility for the final developer.

Partial utility-driven scheduling for flexible SLA and pricing arbitration in clouds

Cloud SLAs compensate customers with credits when average availability drops below certain levels. This is too inflexible because consumers lose non-measurable amounts of performance being only compensated later, in next charging cycles. We propose to schedule virtual machines (VMs), driven by range-based non-linear reductions of utility, different for classes of users and across different ranges of resource allocations: partial utility. This customer-defined metric, allows providers transferring resources between VMs in meaningful and economically efficient ways. We define a comprehensive cost model incorporating partial utility given by clients to a certain level of degradation, when VMs are allocated in overcommitted environments (Public, Private, Community Clouds). CloudSim was extended to support our scheduling model. Several simulation scenarios with synthetic and real workloads are presented, using datacenters with different dimensions regarding the number of servers and computational capacity. We show the partial utility-driven driven scheduling allows more VMs to be allocated. It brings benefits to providers, regarding revenue and resource utilization, allowing for more revenue per resource allocated and scaling well with the size of datacenters when comparing with an utility-oblivious redistribution of resources. Regarding clients, their workloads’ execution time is also improved, by incorporating an SLA-based redistribution of their VM’s computational power.

Impact of a price-maker pumped storage hydro unit on the integration of wind energy in power systems

The increasing integration of larger amounts of wind energy into power systems raises important operational issues, such as the balance between power generation and demand. The pumped storage hydro (PSH) units are one possible solution to mitigate this problem, once they can store the excess of energy in the periods of higher generation and lower demand. However, the behaviour of a PSH unit may differ considerably from the expected in terms of wind power integration when it operates in a liberalized electricity market under a price-maker context. In this regard, this paper models and computes the optimal PSH weekly scheduling in a price-taker and price-maker scenarios, either when the PSH unit operates in standalone and integrated in a portfolio of other generation assets. Results show that the price-maker standalone PSH will integrate less wind power in comparison with the price-taker situation. Moreover, when the PSH unit is integrated in a portfolio with a base load power plant, the role of the price elasticity of demand may completely change the operational profile of the PSH unit. (C) 2014 Elsevier Ltd. All rights reserved.

Renewable power forecast to scheduling of thermal units

In this work is discussed the importance of the renewable production forecast in an island environment. A probabilistic forecast based on kernel density estimators is proposed. The aggregation of these forecasts, allows the determination of thermal generation amount needed to schedule and operating a power grid of an island with high penetration of renewable generation. A case study based on electric system of S. Miguel Island is presented. The results show that the forecast techniques are an imperative tool help the grid management.

Multi-criteria optimization manipulator trajectory planning

In the last twenty years genetic algorithms (GAs) were applied in a plethora of fields such as: control, system identification, robotics, planning and scheduling, image processing, and pattern and speech recognition (Bäck et al., 1997). In robotics the problems of trajectory planning, collision avoidance and manipulator structure design considering a single criteria has been solved using several techniques (Alander, 2003). Most engineering applications require the optimization of several criteria simultaneously. Often the problems are complex, include discrete and continuous variables and there is no prior knowledge about the search space. These kind of problems are very more complex, since they consider multiple design criteria simultaneously within the optimization procedure. This is known as a multi-criteria (or multiobjective) optimization, that has been addressed successfully through GAs (Deb, 2001). The overall aim of multi-criteria evolutionary algorithms is to achieve a set of non-dominated optimal solutions known as Pareto front. At the end of the optimization procedure, instead of a single optimal (or near optimal) solution, the decision maker can select a solution from the Pareto front. Some of the key issues in multi-criteria GAs are: i) the number of objectives, ii) to obtain a Pareto front as wide as possible and iii) to achieve a Pareto front uniformly spread. Indeed, multi-objective techniques using GAs have been increasing in relevance as a research area. In 1989, Goldberg suggested the use of a GA to solve multi-objective problems and since then other researchers have been developing new methods, such as the multi-objective genetic algorithm (MOGA) (Fonseca & Fleming, 1995), the non-dominated sorted genetic algorithm (NSGA) (Deb, 2001), and the niched Pareto genetic algorithm (NPGA) (Horn et al., 1994), among several other variants (Coello, 1998). In this work the trajectory planning problem considers: i) robots with 2 and 3 degrees of freedom (dof ), ii) the inclusion of obstacles in the workspace and iii) up to five criteria that are used to qualify the evolving trajectory, namely the: joint traveling distance, joint velocity, end effector / Cartesian distance, end effector / Cartesian velocity and energy involved. These criteria are used to minimize the joint and end effector traveled distance, trajectory ripple and energy required by the manipulator to reach at destination point. Bearing this ideas in mind, the paper addresses the planning of robot trajectories, meaning the development of an algorithm to find a continuous motion that takes the manipulator from a given starting configuration up to a desired end position without colliding with any obstacle in the workspace. The chapter is organized as follows. Section 2 describes the trajectory planning and several approaches proposed in the literature. Section 3 formulates the problem, namely the representation adopted to solve the trajectory planning and the objectives considered in the optimization. Section 4 studies the algorithm convergence. Section 5 studies a 2R manipulator (i.e., a robot with two rotational joints/links) when the optimization trajectory considers two and five objectives. Sections 6 and 7 show the results for the 3R redundant manipulator with five goals and for other complementary experiments are described, respectively. Finally, section 8 draws the main conclusions.

Analysis of the domain of applicability of an algorithm for a resources system selection problem for Distributed/Agile/Virtual Enterprises integration

The process of resources systems selection takes an important part in Distributed/Agile/Virtual Enterprises (D/A/V Es) integration. However, the resources systems selection is still a difficult matter to solve in a D/A/VE, as it is pointed out in this paper. Globally, we can say that the selection problem has been equated from different aspects, originating different kinds of models/algorithms to solve it. In order to assist the development of a web prototype tool (broker tool), intelligent and flexible, that integrates all the selection model activities and tools, and with the capacity to adequate to each D/A/V E project or instance (this is the major goal of our final project), we intend in this paper to show: a formulation of a kind of resources selection problem and the limitations of the algorithms proposed to solve it. We formulate a particular case of the problem as an integer programming, which is solved using simplex and branch and bound algorithms, and identify their performance limitations (in terms of processing time) based on simulation results. These limitations depend on the number of processing tasks and on the number of pre-selected resources per processing tasks, defining the domain of applicability of the algorithms for the problem studied. The limitations detected open the necessity of the application of other kind of algorithms (approximate solution algorithms) outside the domain of applicability founded for the algorithms simulated. However, for a broker tool it is very important the knowledge of algorithms limitations, in order to, based on problem features, develop and select the most suitable algorithm that guarantees a good performance.

Scheduling a cutting and treatment stainless steel sheet line with self-management capabilities

With advancement in computer science and information technology, computing systems are becoming increasingly more complex with an increasing number of heterogeneous components. They are thus becoming more difficult to monitor, manage, and maintain. This process has been well known as labor intensive and error prone. In addition, traditional approaches for system management are difficult to keep up with the rapidly changing environments. There is a need for automatic and efficient approaches to monitor and manage complex computing systems. In this paper, we propose an innovative framework for scheduling system management by combining Autonomic Computing (AC) paradigm, Multi-Agent Systems (MAS) and Nature Inspired Optimization Techniques (NIT). Additionally, we consider the resolution of realistic problems. The scheduling of a Cutting and Treatment Stainless Steel Sheet Line will be evaluated. Results show that proposed approach has advantages when compared with other scheduling systems

Wind-CSP short-term coordination by Milp approach

This paper is on the maximization of total profit in a day-ahead market for a price-taker producer needing a short-term scheduling for wind power plants coordination with concentrated solar power plants, having thermal energy storage systems. The optimization approach proposed for the maximization of profit is a mixed-integer linear programming problem. The approach considers not only transmission grid constraints, but also technical operating constraints on both wind and concentrated solar power plants. Then, an improved short-term scheduling coordination is provided due to the more accurate modelling presented in this paper. Computer simulation results based on data for the Iberian wind and concentrated solar power plants illustrate the coordination benefits and show the effectiveness of the approach.

Adaptive tackling of the swinging problem for a 2 DOF crane – payload system

The control of a crane carrying its payload by an elastic string corresponds to a task in which precise, indirect control of a subsystem dynamically coupled to a directly controllable subsystem is needed. This task is interesting since the coupled degree of freedom has little damping and it is apt to keep swinging accordingly. The traditional approaches apply the input shaping technology to assist the human operator responsible for the manipulation task. In the present paper a novel adaptive approach applying fixed point transformations based iterations having local basin of attraction is proposed to simultaneously tackle the problems originating from the imprecise dynamic model available for the system to be controlled and the swinging problem, too. The most important phenomenological properties of this approach are also discussed. The control considers the 4th time-derivative of the trajectory of the payload. The operation of the proposed control is illustrated via simulation results.

Meta-heuristics self-parameterization in a multi-agent scheduling system using case-based reasoning

This paper proposes a novel agent-based approach to Meta-Heuristics self-configuration. Meta-heuristics are algorithms with parameters which need to be set up as efficient as possible in order to unsure its performance. A learning module for self-parameterization of Meta-heuristics (MH) in a Multi-Agent System (MAS) for resolution of scheduling problems is proposed in this work. The learning module is based on Case-based Reasoning (CBR) and two different integration approaches are proposed. A computational study is made for comparing the two CBR integration perspectives. Finally, some conclusions are reached and future work outlined.

Reverse problem-based learning - a case study with a Braille machine

Engineering Education includes not only teaching theoretical fundamental concepts but also its verification during practical lessons in laboratories. The usual strategies to carry out this action are frequently based on Problem Based Learning, starting from a given state and proceeding forward to a target state. The possibility or the effectiveness of this procedure depends on previous states and if the present state was caused or resulted from earlier ones. This often happens in engineering education when the achieved results do not match the desired ones, e.g. when programming code is being developed or when the cause of the wrong behavior of an electronic circuit is being identified. It is thus important to also prepare students to proceed in the reverse way, i.e. given a start state generate the explanation or even the principles that underlie it. Later on, this sort of skills will be important. For instance, to a doctor making a patient?s story or to an engineer discovering the source of a malfunction. This learning methodology presents pedagogical advantages besides the enhanced preparation of students to their future work. The work presented on his document describes an automation project developed by a group of students in an engineering polytechnic school laboratory. The main objective was to improve the performance of a Braille machine. However, in a scenario of Reverse Problem-Based learning, students had first to discover and characterize the entire machine's function before being allowed (and being able) to propose a solution for the existing problem.

Positive radial solutions of the Dirichlet problem for the Minkowski-Curvature equation in a ball

We study the existence and multiplicity of positive radial solutions of the Dirichlet problem for the Minkowski-curvature equation { -div(del upsilon/root 1-vertical bar del upsilon vertical bar(2)) in B-R, upsilon=0 on partial derivative B-R,B- where B-R is a ball in R-N (N >= 2). According to the behaviour off = f (r, s) near s = 0, we prove the existence of either one, two or three positive solutions. All results are obtained by reduction to an equivalent non-singular one-dimensional problem, to which variational methods can be applied in a standard way.