TY - JOUR
T1 - Scheduling data gathering with background communications and a processing stage
AU - Berlińska, Joanna
AU - Mor, Baruch
N1 - Publisher Copyright:
© 2022 Elsevier Ltd
PY - 2022/9
Y1 - 2022/9
N2 - A data gathering network is a distributed computer system where the workers have to transfer data to a node called the base station, which is responsible for their processing. Wireless sensor networks monitoring the environment or wired systems executing computations are examples of such networks. We analyze scheduling in data gathering networks with background communications. It is assumed that at most one worker can communicate with the base station at a time, and hence, the network works in a flow shop mode. The speed of each communication link may change in time because of various processes using the network. Communication and computation preemptions are possible. The objective is to minimize the time required to gather and process all data. We prove that this problem is strongly NP-hard and indicate several polynomially solvable cases. Heuristic algorithms are proposed and tested using computational experiments. On the basis of the obtained results, we identify the algorithms that perform best in specific types of networks.
AB - A data gathering network is a distributed computer system where the workers have to transfer data to a node called the base station, which is responsible for their processing. Wireless sensor networks monitoring the environment or wired systems executing computations are examples of such networks. We analyze scheduling in data gathering networks with background communications. It is assumed that at most one worker can communicate with the base station at a time, and hence, the network works in a flow shop mode. The speed of each communication link may change in time because of various processes using the network. Communication and computation preemptions are possible. The objective is to minimize the time required to gather and process all data. We prove that this problem is strongly NP-hard and indicate several polynomially solvable cases. Heuristic algorithms are proposed and tested using computational experiments. On the basis of the obtained results, we identify the algorithms that perform best in specific types of networks.
KW - Data gathering networks
KW - Flow shop
KW - Scheduling
KW - Variable communication speed
UR - http://www.scopus.com/inward/record.url?scp=85135532352&partnerID=8YFLogxK
U2 - 10.1016/j.cie.2022.108467
DO - 10.1016/j.cie.2022.108467
M3 - ???researchoutput.researchoutputtypes.contributiontojournal.article???
AN - SCOPUS:85135532352
SN - 0360-8352
VL - 171
JO - Computers and Industrial Engineering
JF - Computers and Industrial Engineering
M1 - 108467
ER -