Scheduling in data gathering networks with background communications

Joanna Berlińska ()
Additional contact information
Joanna Berlińska: Adam Mickiewicz University, Poznań

Journal of Scheduling, 2020, vol. 23, issue 6, No 6, 691 pages

Abstract: Abstract In this work, we study scheduling in star data gathering networks with background communications. The worker nodes of the network hold datasets that have to be transferred directly to the base station. The communication speed of each link changes with time, due to other applications using the network, independently of the speeds of other links. Our goal is to gather all data within the minimum time. We show that while the preemptive version of this problem can be solved in polynomial time, the non-preemptive variant is strongly NP-hard. We propose for it an exact exponential algorithm based on dynamic programming, several polynomial time heuristics and local search algorithms. Theoretical performance guarantees and the existence of dominance relations between the heuristics are studied. The performance of the proposed algorithms is also tested in a series of computational experiments.

Keywords: Scheduling; Data gathering networks; Variable communication speed (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10951-020-00648-5 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jsched:v:23:y:2020:i:6:d:10.1007_s10951-020-00648-5

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10951

DOI: 10.1007/s10951-020-00648-5

Access Statistics for this article

Journal of Scheduling is currently edited by Edmund Burke and Michael Pinedo

More articles in Journal of Scheduling from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().