文献类型：期刊文献

英文题名：Exact andApproximation Algorithms fortheMulti-depot Data Mule Scheduling withHandling Time andTime Span Constraints

作者：Liu, Minqin[1]; Yu, Wei[1]; Liu, Zhaohui[1]; Guo, Xinmeng[1]

机构：[1] School of Mathematics, East China University of Science and Technology, Shanghai, 200237, China

年份：2024

卷号：14461 LNCS

起止页码：129

外文期刊名：Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

收录：EI(收录号：20235215288625)

语种：英文

外文关键词：Data handling - Polynomial approximation - Wireless sensor networks

摘要：In this paper, we investigate the data mule scheduling with handling time and time span constraints (DMSTC) in which the goal is to minimize the number of data mules dispatched from a depot that are used to serve target sensors located on a wireless sensor network. Each target sensor is associated with a handling time and each dispatched data mule must return to the original depot before time span D. We also study a variant of the DMSTC in which the objective is to minimize the total travel distance of the data mules dispatched. We give exact and approximation algorithms for the DMSTC on a path and their multi-depot version. For the first objective, we show an O(n4) polynomial time algorithm for the uniform 2-depot DMSTC on a path where at least one depot is on the endpoint (n indicates the number of target sensors). And we present a new 2-approximation algorithm for the non-uniform DMSTC on a path. For the second objective, we derive an O((n+ k)2) -time algorithm for the uniform multi-depot DMSTC on a path, where k is the number of depots. For the non-uniform multi-depot DMSTC on a path or cycle, we give a 2-approximation algorithm. ? 2024, The Author(s), under exclusive license to Springer Nature Switzerland AG.