文献类型：期刊文献

英文题名：Approximation and polynomial algorithms for the data mule scheduling with handling time and time span constraints

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

机构：[1]East China Univ Sci & Technol, Sch Math, 130 Meilong Rd, Shanghai 200237, Peoples R China

年份：2022

卷号：178

外文期刊名：INFORMATION PROCESSING LETTERS

收录：;EI(收录号：20222912372910);WOS:【SCI-EXPANDED(收录号:WOS:000860690400005)】；

基金：Acknowledgements This research is supported by the National Natural Science Foundation of China (Nos. 11671135 and 11871213) and the Natural Science Foundation of Shanghai (No. 19ZR1411800) .

语种：英文

外文关键词：data mule scheduling; handling time; time span constraint; approximation algorithms; polynomial algorithms

摘要：In this paper, we address the data mule scheduling problem with time constraints (DMSTC) in which the aim is to dispatch from a depot the minimum number of data mules to serve target sensors located on a network. Each target sensor is associated with a handling time and each dispatched data mule must return to the depot before time span D. Our main contribution is as follows. First, we give the first constant-factor 2-approximation algorithm and a bicriteria polynomial time approximation scheme (PTAS) for the DMSTC defined on a tree. The former result resolves an open problem proposed in the literature (Chen et al., 2020 [4]). This is achieved by an approximation preserving reduction from the DMSTC to the distance constrained vehicle routing problem, i.e. a special case of the DMSTC with zero handling times. Second, we show that our approximation preserving reduction can be extended to the multi-depot version of the DMSTC and derive a similar bicriteria PTAS for the multi-depot DMSTC on a tree if the number of depots is a fixed constant. Finally, we consider the uniform DMSTC, which is a particular case of the DMSTC with all handling times identical, and develop the first non-trivial polynomial algorithms for the uniform DMSTC define on several classes of special networks, including spiders, paths and cycles. (c) 2022 Elsevier B.V. All rights reserved.