Scheduling for gathering multitype data with local computations

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.