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

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

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

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

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

Popis výsledku anglicky

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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

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

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

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

Rok uplatnění

2020

Kód důvěrnosti údajů

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

Název periodika

European Journal of Operational Research

ISSN

0377-2217

e-ISSN

1872-6860

Svazek periodika

284

Číslo periodika v rámci svazku

2

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

15

Strana od-do

445-459

Kód UT WoS článku

000527271500005

EID výsledku v databázi Scopus

2-s2.0-85080093906