Prelegent: dr Joanna Berlińska
Miejsce: Sala seminaryjna B1-7/8
Data i godzina: 12 marca 2019 r., g. 12:30
Abstract: We study scheduling in a data gathering network consisting of a set of worker nodes and a single base station. The workers produce datasets that have to be sent to the base station for processing. Each dataset can be released at a different moment. The time required to transfer a dataset to the base station, and the time necessary to process it, are proportional to the dataset size. At most one worker can communicate with the base station at a time, and hence, the network works in a flow shop mode. A dataset transfer or processing can be preempted at any time and resumed later at no cost. Each dataset is assigned a due date by which it should be fully processed by the base station. The scheduling problem is to organize the communication and computation in the network so that the maximum dataset lateness is minimized. We prove that this problem is strongly NP-hard, and show some special cases that can be solved in polynomial time. A branch-and-bound algorithm and several polynomial-time heuristics are proposed for the general version of the problem. The performance of the algorithms is tested in a series of computational experiments.