Heuristics for scheduling data gathering with limited base station memory

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

Annals of Operations Research, 2020, vol. 285, issue 1, No 7, 149-159

Abstract: Abstract In this paper, we analyze scheduling in data gathering networks with limited base station memory. The network nodes hold datasets that have to be gathered and processed by a single base station. A dataset transfer can only start if sufficient amount of memory is available at the base station. As soon as a node starts sending a dataset, the base station allocates a block of memory of corresponding size. The memory is released when computations on the dataset finish. We prove that minimizing the total data gathering and processing time is strongly NP-hard. As this problem is a special case of a specific resource constrained flow shop scheduling problem, for which an exact exponential algorithm is known, we propose several simple polynomial-time heuristics and two groups of local search algorithms, and test their performance in computational experiments. We show that the local search algorithms produce very good schedules, and one of the simple heuristics delivers solutions of comparable quality in a very short time.

Keywords: Scheduling; Data gathering network; Limited memory; Flow shop (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/s10479-019-03185-3 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:annopr:v:285:y:2020:i:1:d:10.1007_s10479-019-03185-3

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

DOI: 10.1007/s10479-019-03185-3

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

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