Grouping tasks to save energy in a cyclic scheduling problem: A complexity study

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21730%2F20%3A00341186" target="_blank" >RIV/68407700:21730/20:00341186 - isvavai.cz</a>

Result on the web

<a href="https://doi.org/10.1016/j.ejor.2020.01.005" target="_blank" >https://doi.org/10.1016/j.ejor.2020.01.005</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.ejor.2020.01.005" target="_blank" >10.1016/j.ejor.2020.01.005</a>

Result language

angličtina

Original language name

Grouping tasks to save energy in a cyclic scheduling problem: A complexity study

Original language description

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 super-task 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 NP-complete 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.

Czech name

—

Czech description

—

Type

J_imp - Article in a specialist periodical, which is included in the Web of Science database

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

Result was created during the realization of more than one project. More information in the Projects tab.

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year

2020

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Name of the periodical

European Journal of Operational Research

ISSN

0377-2217

e-ISSN

1872-6860

Volume of the periodical

284

Issue of the periodical within the volume

2

Country of publishing house

NL - THE KINGDOM OF THE NETHERLANDS

Number of pages

15

Pages from-to

445-459

UT code for WoS article

000527271500005

EID of the result in the Scopus database

2-s2.0-85080093906