Summary: 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.