Exact and Approximation Algorithms for the Multi-depot Data Mule Scheduling with Handling Time and Time Span Constraints

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(n^4)\) 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.