Scheduling for gathering multitype data with local computations

Joanna Berlińska and Bartłomiej Przybylski

European Journal of Operational Research, 2021, vol. 294, issue 2, 453-459

Abstract: In this paper, we analyze scheduling gathering multitype data in a star network. Certain numbers of datasets of different types have to be collected on a single computer, either by downloading them from remote nodes, or by producing them locally. The time required to download a dataset depends on its type and initial location, and the time needed to produce a dataset depends only on its type. The scheduling problem is to decide which datasets should be downloaded from which nodes, and how many datasets of each type should be generated locally, in order to minimize the total time necessary for gathering all data. We show that this problem is NP-hard, indicate special cases solvable in polynomial time, and propose a fully polynomial time approximation scheme for a special case which is still NP-hard. For the general case, we present an integer linear programming formulation, a dynamic programming algorithm and a polynomial 2-approximation algorithm. The performance of these algorithms is tested in computational experiments.

Keywords: Scheduling; Data gathering networks; Local computations; Makespan (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221721000734
Full text for ScienceDirect subscribers only

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:eee:ejores:v:294:y:2021:i:2:p:453-459

DOI: 10.1016/j.ejor.2021.01.043

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().