Grouping tasks to save energy in a cyclic scheduling problem: a complexity study Abstract   This paper is motivated by the repetitive and periodic transmission of messages in Wireless Sensor Networks (WSNs) given by the ZigBee standard. In order to save energy, communication tasks are grouped in time. The WSN applications, such as control loops used in production lines, impose deadlines on the message delivery time.  By introducing a grouping constraint, this paper extends the polynomial cyclic scheduling problem of building a periodic schedule with uniform precedence constraints and no resource constraints. We consider that each task belongs to one group, and each group is to be scheduled as a supertask in every period. We show two examples issued from different applications of such grouping constraints, using uniform constraints to model the deadlines expressed in the number of periods. We tackle the feasibility problem (the existence of a periodic schedule), which has shown to be independent of the processing times. We propose a graph formulation of the problem using the retiming technique.  In the ZigBee case, we prove that the particular tree structure of the groups and of the uniform precedences based upon the communication tree, lead to a polynomial algorithm to solve the problem. But the general problem is proven to be NPcomplete even if no additional resource constraints are considered, and unit processing times are assumed. This extension of the cyclic scheduling leads to a new range of grouping problems with applications, not only in communication networks but also in production and logistics scheduling.

Scheduling Periodic and Aperiodic Tasks with Time, Energy Harvesting and Precedence Constraints on Multicore Systems Abstract   This paper deals with the realtime scheduling problem of multicore systems powered by renewable energy harvested from environment. They handle two types of software tasks which are mapped to cores statically and not allowed to migrate. A task can be periodic which may depend on other tasksxe2x80x99 results, or aperiodic which is added to the system to cope with external interruptions. The uncertainty of energy availability in energy harvesting systems makes realtime scheduling more challenging because energy constraints can be violated to ensure realtime performance. A novel scheduling strategy is proposed to effectively compute deadlines allowing for tasks and messages to meet related constraints. This method consists of two phases, i) the first one defines different time slots each of which is characterized by energy and frequency parameters to cope with the energy availability issue, and ii) the second one calculates the deadlines ensuring realtime system feasibility by considering the invocation of aperiodic task execution and task precedence constraints. The originality of the current work compared with related studies is that it deals with multicore, periodic and aperiodic tasks, dependency, energy harvesting, and realtime aspects simultaneously.