UAV mission scheduling with completion time, flight distance, and resource consumption constraints

Abstract

Unmanned aerial vehicles (UAVs) are widely used in various military and civilian applications. UAV mission scheduling is a key issue in UAV applications and a central topic in UAV research. UAV task scheduling should include several constraints into consideration, such as completion time constraint, flight distance constraint, and resource consumption constraint. Furthermore, UAV task scheduling should be studied within the traditional framework of combinatorial optimisation. In this paper, we consider optimal mission scheduling for heterogeneous UAVs with completion time, flight distance, and resource consumption constraints. The contributions of the paper are summarised as follows. We define two combinatorial optimisation problems, namely, the NFTM (number of finished tasks maximisation) problem and the RFTM (reward of finished tasks maximisation) problem. We construct an algorithmic framework for both NFTM and RFTM problems, so that our heuristic algorithms (four for NFTM and two for RFTM) can be presented in a unified way. We derive upper bounds for optimal solutions, so that our heuristic solutions can be compared with optimal solutions. We experimentally evaluate the performance of our heuristic algorithms. To the best of our knowledge, this is the first paper studying UAV mission scheduling with time, distance, and resource constraints as combinatorial optimisation problems.

Keywords:

• Algorithmic framework
• combinatorial optimisation
• heterogeneous UAVs
• heuristic algorithm
• mission scheduling

1. Introduction

1.1. Background

Unmanned aerial vehicles (UAVs), also called drones, are widely used in various military and civilian applications, such as construction inspection, disaster management, forest restoration, precision agriculture, remote sensing, search and rescue, security and surveillance, traffic monitoring (SCE). UAVs have created a new type of distributed systems and dynamic environments (Machovec et al., 2023).

UAV mission scheduling is a key issue in UAV applications and a central topic in UAV research. A typical scenario involves multiple heterogeneous UAVs (with different initial locations, flight speeds, maximum flight distances, maximum flight times, and maximum resource consumptions) and multiple heterogeneous tasks (with different positions, processing times, deadlines, resource requests, and rewards). UAVs are actually mobile and location-sensitive (Tan et al., 2021) servers with limited energy capacity (C.-I. Li et al., 2021), which move around to process tasks. UAV mission scheduling is essentially to dispatch UAVs to fly, process, and complete tasks with various optimisation objectives under various conditions and constraints.

UAV task scheduling (especially for rescue missions (Alhaqbani et al., 2021) and other similar tasks) should include several constraints into consideration, such as completion time constraint, flight distance constraint, and resource consumption constraint. (1) Completion time constraint – For a time-critical task, there is a deadline to complete the task. For instance, in disaster rescue, the survival time of a victim is very limited. (2) Flight distance constraint – A UAV has certain flight distance limitation due to limited energy supply (fuel or electricity). (3) Resource consumption constraint – A UAV can only carry a certain amount of resources required and requested by tasks due to limited capacity and space. Furthermore, UAV task scheduling should be studied within the traditional framework of combinatorial optimisation (K. Li, 2023).

1.2. Related work

It has been pointed out that there are two main considerations in UAV mission scheduling, i.e. task assignment and flight planning (Bellingham et al., 2003; Peng et al., 2021; Sebbane, 2021). Extensive research has been conducted in task assignment [including such methods as fish-inspired algorithm (Alhaqbani et al., 2021), autonomous task allocation (Aljalaud & Kurdi, 2021), leader-follower coalition (J. Chen & Sun, 2011), dynamic grouping allocation (X. Chen et al. 2019), distributed task allocation (Cui et al., 2022), decentralised auction algorithm (Hu & Yang, 2018), double-layer deep reinforcement learning (Mao et al., 2022), human-agent collaboration (Ramchurn et al., 2015), mixed integer linear program (Schumacher et al., 2003), negotiation (Sujit et al., 2006), simulation-based system (Sung et al., 2019), team-based approach (Venugopalan et al., 2015), quantum genetic algorithm (Z. Wang & Yan, 2021), digital twin (Yi et al., 2023), and clone selection (Zhang & Chen, 2021)] and flight planning [including such methods as decentralised algorithm (Bertuccelli et al., 2009), neural network (Filho et al., 2022), auction algorithm (Fu et al., 2019), cooperative planning (L. Geng et al. 2014), particle swarm optimisation (N. Geng et al., 2021), simulated annealing and local search (Ozkan, 2021), auction bidding and resolution (Sullivan et al. 2019), distributed particle swarm optimisation (Y. Wang et al., 2019), online algorithm (Yao & Ansari, 2020), deep migration reinforcement learning (Yin et al., 2022), and bat algorithm (Zhou et al., 2021)]. It is also noticed that the two problems of task allocation and route planning should be considered together (Yan et al., 2021).

A combinatorial optimisation approach has been adopted in K. Li (2023), where task scheduling on heterogeneous UAVs was treated as NP-hard optimisation problems and heuristic algorithms were designed and analysed. However, task completion time constraint, UAV flight distance constraint, and UAV resource consumption constraint were not taken into account.

1.3. Contributions

In this paper, we consider optimal (rescue) mission scheduling for heterogeneous UAVs with completion time (e.g. survival time), flight distance, and resource consumption constraints. The contributions of the paper are summarised as follows.

• We define two combinatorial optimisation problems, namely, the NFTM (number of finished tasks maximisation) problem and the RFTM (reward of finished tasks maximisation) problem.

• We construct an algorithmic framework for both NFTM and RFTM problems, so that our heuristic algorithms (four for NFTM and two for RFTM) can be presented in a unified way.

• We derive upper bounds for optimal solutions, so that our heuristic solutions can be compared with optimal solutions.

• We experimentally evaluate the performance of our heuristic algorithms.

To the best of our knowledge, this is the first paper studying UAV mission scheduling with time, distance, and resource constraints as combinatorial optimisation problems.

The rest of the paper is organised as follows. In Section 2, we present preliminary information, including a UAV mission scheduling model and our problem definitions. In Section 3, we develop our heuristic algorithms. In Section 4, we derive upper bounds for optimal solutions. In Section 5, we conduct an experimental performance evaluation for our heuristic algorithms. In Section 6, we summarise the paper.

2. Preliminaries

In this section, we present preliminary information, including a UAV mission scheduling model and our problem definitions. Table A1 lists all the notations and definitions used in the paper.

2.1. Scheduling model

In this section, we describe our UAV mission scheduling model.

Our model includes m UAVs: $u_1,u_2,\dots ,u_m$, and n missions (tasks) in a three-dimensional space.

A UAV is specified as $u_i=\left(\mathit{p}\mathit{o}\mathit{s}\mathit{i}\mathit{t}\mathit{i}\mathit{o}\mathit{n}\right(u_i),\mathit{s}\mathit{p}\mathit{e}\mathit{e}\mathit{d}(u_i),\mathit{m}\mathit{a}\mathit{x}\mathit{d}\mathit{i}\mathit{s}\mathit{t}\mathit{a}\mathit{n}\mathit{c}\mathit{e}(u_i),\mathit{m}\mathit{a}\mathit{x}\mathit{r}\mathit{e}\mathit{s}\mathit{o}\mathit{u}\mathit{r}\mathit{c}\mathit{e}(u_i\left)\right)$, where $\mathit{p}\mathit{o}\mathit{s}\mathit{i}\mathit{t}\mathit{i}\mathit{o}\mathit{n}\left(u_i\right)$ is the initial location of $u_i$, $\mathit{s}\mathit{p}\mathit{e}\mathit{e}\mathit{d}\left(u_i\right)$ is the flight speed of $u_i$, $\mathit{m}\mathit{a}\mathit{x}\mathit{d}\mathit{i}\mathit{s}\mathit{t}\mathit{a}\mathit{n}\mathit{c}\mathit{e}\left(u_i\right)$ is the maximum flight distance of $u_i$, and $\mathit{m}\mathit{a}\mathit{x}\mathit{r}\mathit{e}\mathit{s}\mathit{o}\mathit{u}\mathit{r}\mathit{c}\mathit{e}\left(u_i\right)$ is the maximum resource consumption of $u_i$. For convenience, we also define $\mathit{m}\mathit{a}\mathit{x}\mathit{t}\mathit{i}\mathit{m}\mathit{e}\left(u_i\right)$ to be the maximum flight time of $u_i$, which is $\mathit{m}\mathit{a}\mathit{x}\mathit{d}\mathit{i}\mathit{s}\mathit{t}\mathit{a}\mathit{n}\mathit{c}\mathit{e}\left(u_i\right)/\mathit{s}\mathit{p}\mathit{e}\mathit{e}\mathit{d}\left(u_i\right)$.

Let $L=(t_1,t_2,\dots ,t_n)$ be a list of tasks. A task is specified as $t_j=\left(\mathit{p}\mathit{o}\mathit{s}\mathit{i}\mathit{t}\mathit{i}\mathit{o}\mathit{n}\right(t_j),\mathit{p}\mathit{t}\mathit{i}\mathit{m}\mathit{e}(t_j),\mathit{d}\mathit{e}\mathit{a}\mathit{d}\mathit{l}\mathit{i}\mathit{n}\mathit{e}(t_j),\mathit{r}\mathit{e}\mathit{q}\mathit{u}\mathit{e}\mathit{s}\mathit{t}(t_j),reward(t_j\left)\right)$, where $\mathit{p}\mathit{o}\mathit{s}\mathit{i}\mathit{t}\mathit{i}\mathit{o}\mathit{n}\left(t_j\right)$ is the position of $t_j$, $\mathit{p}\mathit{t}\mathit{i}\mathit{m}\mathit{e}\left(t_j\right)$ is the processing time of $t_j$, $\mathit{d}\mathit{e}\mathit{a}\mathit{d}\mathit{l}\mathit{i}\mathit{n}\mathit{e}\left(t_j\right)$ is time deadline to complete $t_j$, $\mathit{r}\mathit{e}\mathit{q}\mathit{u}\mathit{e}\mathit{s}\mathit{t}\left(t_j\right)$ is the amount of resource request of $t_j$, and $\mathit{r}\mathit{e}\mathit{w}\mathit{a}\mathit{r}\mathit{d}\left(t_j\right)$ is the reward of completing $t_j$.

Our scheduling problems essentially find $\mathit{r}\mathit{o}\mathit{u}\mathit{t}\mathit{e}\left(u_i\right)$, i.e. the flight route of $u_i$, for all i. A flight route is actually $(t_{i,1},t_{i,2},\dots ,t_{i,n_i})$, i.e. a sequence of tasks.

Let $\mathit{d}\mathit{i}\mathit{s}\mathit{t}(p,q)$ be the distance between locations p and q.

For a $\mathit{r}\mathit{o}\mathit{u}\mathit{t}\mathit{e}\left(u_i\right)=(t_{i,1},t_{i,2},\dots ,t_{i,n_i})$ of $u_i$, the total flight distance of $u_i$ is $\mathit{d}\mathit{i}\mathit{s}\mathit{t}\mathit{a}\mathit{n}\mathit{c}\mathit{e}\left(u_i\right)=\mathit{d}\mathit{i}\mathit{s}\mathit{t}\left(\mathit{p}\mathit{o}\mathit{s}\mathit{i}\mathit{t}\mathit{i}\mathit{o}\mathit{n}\right(u_i),\mathit{p}\mathit{o}\mathit{s}\mathit{i}\mathit{t}\mathit{i}\mathit{o}\mathit{n}(t_{i,1}\left)\right)+\sum _{k=1}^{n_i-1}\mathit{d}\mathit{i}\mathit{s}\mathit{t}\left(\mathit{p}\mathit{o}\mathit{s}\mathit{i}\mathit{t}\mathit{i}\mathit{o}\mathit{n}\right(t_{i,k}),\mathit{p}\mathit{o}\mathit{s}\mathit{i}\mathit{t}\mathit{i}\mathit{o}\mathit{n}(t_{i,k+1}\left)\right).$The total flight time of $u_i$ is $\mathit{f}\mathit{t}\mathit{i}\mathit{m}\mathit{e}\left(u_i\right)=\mathit{d}\mathit{i}\mathit{s}\mathit{t}\mathit{a}\mathit{n}\mathit{c}\mathit{e}\left(u_i\right)/\mathit{s}\mathit{p}\mathit{e}\mathit{e}\mathit{d}\left(u_i\right).$The total processing time of $u_i$ is $\mathit{p}\mathit{t}\mathit{i}\mathit{m}\mathit{e}\left(u_i\right)=\sum _{k=1}^{n_i}\mathit{p}\mathit{t}\mathit{i}\mathit{m}\mathit{e}\left(t_{i,k}\right).$The total time of $u_i$ is the total flight time + the total processing time: $\mathit{t}\mathit{i}\mathit{m}\mathit{e}\left(u_i\right)=\mathit{f}\mathit{t}\mathit{i}\mathit{m}\mathit{e}\left(u_i\right)+\mathit{p}\mathit{t}\mathit{i}\mathit{m}\mathit{e}\left(u_i\right).$The total resource consumption of $u_i$ is $\mathit{r}\mathit{e}\mathit{s}\mathit{o}\mathit{u}\mathit{r}\mathit{c}\mathit{e}\left(u_i\right)=\sum _{k=1}^{n_i}\mathit{r}\mathit{e}\mathit{q}\mathit{u}\mathit{e}\mathit{s}\mathit{t}\left(t_{i,k}\right).$Initially, the current location of $u_i$ is $\mathit{l}\mathit{o}\mathit{c}\mathit{a}\mathit{t}\mathit{i}\mathit{o}\mathit{n}\left(u_i\right)=\mathit{p}\mathit{o}\mathit{s}\mathit{i}\mathit{t}\mathit{i}\mathit{o}\mathit{n}\left(u_i\right),$and when $u_i$ moves to $t_{i,k}$, $\mathit{l}\mathit{o}\mathit{c}\mathit{a}\mathit{t}\mathit{i}\mathit{o}\mathit{n}\left(u_i\right)=\mathit{p}\mathit{o}\mathit{s}\mathit{i}\mathit{t}\mathit{i}\mathit{o}\mathit{n}\left(t_{i,k}\right).$The completion time of $t_{i,k}$ is $\begin{array}{rl}\mathit{c}\mathit{t}\mathit{i}\mathit{m}\mathit{e}\left(t_{i,k}\right)& =\frac{1}{speed\left(u_i\right)}\left(\mathit{d}\mathit{i}\mathit{s}\mathit{t}\right(\mathit{p}\mathit{o}\mathit{s}\mathit{i}\mathit{t}\mathit{i}\mathit{o}\mathit{n}\left(u_i\right),\mathit{p}\mathit{o}\mathit{s}\mathit{i}\mathit{t}\mathit{i}\mathit{o}\mathit{n}\left(t_{i,1}\right))\phantom{\sum _{k^{\prime }=1}^{k-1}}\\ & +\sum _{k^{\prime }=1}^{k-1}\mathit{d}\mathit{i}\mathit{s}\mathit{t}\left(\mathit{p}\mathit{o}\mathit{s}\mathit{i}\mathit{t}\mathit{i}\mathit{o}\mathit{n}\right(t_{i,k^{\prime }}),\mathit{p}\mathit{o}\mathit{s}\mathit{i}\mathit{t}\mathit{i}\mathit{o}\mathit{n}(t_{i,k^{\prime }+1}\left)\right))+\sum _{k^{\prime }=1}^k\mathit{p}\mathit{t}\mathit{i}\mathit{m}\mathit{e}\left(t_{i,k^{\prime }}\right).\end{array}$Let F be the set of finished tasks, i.e. $F=\left\{t_j|\mathit{c}\mathit{t}\mathit{i}\mathit{m}\mathit{e}\right(t_j)\le \mathit{d}\mathit{e}\mathit{a}\mathit{d}\mathit{l}\mathit{i}\mathit{n}\mathit{e}(t_j\left)\right\}.$Let N be the number of finished tasks, i.e. $N=|F|.$Let R the total reward of finished tasks, i.e. $R=\sum _{t_j\in F}\mathit{r}\mathit{e}\mathit{w}\mathit{a}\mathit{r}\mathit{d}\left(t_j\right).$

2.2. Optimization problems

In this section, we define our combinatorial optimisation problems.

We define two UAV mission scheduling problems.

The first problem is called number of finished tasks maximisation (NFTM). Given m heterogeneous UAVs and a list of tasks, the NFTM problem is to maximise the number of finished tasks, such that the completion of each task does not exceed its time deadline, the total flight distance of a UAV does not exceed its maximum flight distance, and the total resource consumption of a UAV does not exceed its maximum resource consumption.

Problem 2.1

Number of Finished Tasks Maximization (NFTM)

• Input: m UAVs: $u_1,u_2,\dots ,u_m$, where $u_i=\left(\mathit{p}\mathit{o}\mathit{s}\mathit{i}\mathit{t}\mathit{i}\mathit{o}\mathit{n}\right(u_i),\mathit{s}\mathit{p}\mathit{e}\mathit{e}\mathit{d}(u_i),\mathit{m}\mathit{a}\mathit{x}\mathit{d}\mathit{i}\mathit{s}\mathit{t}\mathit{a}\mathit{n}\mathit{c}\mathit{e}(u_i),\mathit{m}\mathit{a}\mathit{x}\mathit{r}\mathit{e}\mathit{s}\mathit{o}\mathit{u}\mathit{r}\mathit{c}\mathit{e}(u_i\left)\right)$, and a list of tasks $L=(t_1,t_2,\dots ,t_n)$, where $t_j=\left(\mathit{p}\mathit{o}\mathit{s}\mathit{i}\mathit{t}\mathit{i}\mathit{o}\mathit{n}\right(t_j),\mathit{p}\mathit{t}\mathit{i}\mathit{m}\mathit{e}(t_j),\mathit{d}\mathit{e}\mathit{a}\mathit{d}\mathit{l}\mathit{i}\mathit{n}\mathit{e}(t_j),\mathit{r}\mathit{e}\mathit{q}\mathit{u}\mathit{e}\mathit{s}\mathit{t}(t_j\left)\right)$.

• Output: $\mathit{r}\mathit{o}\mathit{u}\mathit{t}\mathit{e}\left(u_i\right)$ for all i, such that N is maximised and $\mathit{c}\mathit{t}\mathit{i}\mathit{m}\mathit{e}\left(t_j\right)\le \mathit{d}\mathit{e}\mathit{a}\mathit{d}\mathit{l}\mathit{i}\mathit{n}\mathit{e}\left(t_j\right)$ for all j, $\mathit{d}\mathit{i}\mathit{s}\mathit{t}\mathit{a}\mathit{n}\mathit{c}\mathit{e}\left(u_i\right)\le \mathit{m}\mathit{a}\mathit{x}\mathit{d}\mathit{i}\mathit{s}\mathit{t}\mathit{a}\mathit{n}\mathit{c}\mathit{e}\left(u_i\right)$ for all i, and $\mathit{r}\mathit{e}\mathit{s}\mathit{o}\mathit{u}\mathit{r}\mathit{c}\mathit{e}\left(u_i\right)\le \mathit{m}\mathit{a}\mathit{x}\mathit{d}\mathit{i}\mathit{s}\mathit{t}\mathit{a}\mathit{n}\mathit{c}\mathit{e}\left(u_i\right)$ for all i.

We would like to mention that the NFTM problem is NP-hard even if there is no distance and resource consideration, i.e. $\mathit{m}\mathit{a}\mathit{x}\mathit{d}\mathit{i}\mathit{s}\mathit{t}\mathit{a}\mathit{n}\mathit{c}\mathit{e}\left(u_i\right)=\mathrm{\infty }$ and $\mathit{m}\mathit{a}\mathit{x}\mathit{r}\mathit{e}\mathit{s}\mathit{o}\mathit{u}\mathit{r}\mathit{c}\mathit{e}\left(u_i\right)=\mathrm{\infty }$ for all i, and $\mathit{r}\mathit{e}\mathit{q}\mathit{u}\mathit{e}\mathit{s}\mathit{t}\left(t_j\right)=0$ for all j, and all tasks have a common time deadline, i.e. $\mathit{d}\mathit{e}\mathit{a}\mathit{d}\mathit{l}\mathit{i}\mathit{n}\mathit{e}\left(t_j\right)=D$ for all j (K. Li 2023).

The second problem is called reward of finished tasks maximisation (RFTM). Given m heterogeneous UAVs and a list of tasks, the RFTM problem is to maximise the total reward of finished tasks, such that the completion of each task does not exceed its time deadline, the total flight distance of a UAV does not exceed its maximum flight distance, and the total resource consumption of a UAV does not exceed its maximum resource consumption.

Problem 2.2

Reward of Finished Tasks Maximization (RFTM)

• Input: m UAVs: $u_1,u_2,\dots ,u_m$, where $u_i=\left(\mathit{p}\mathit{o}\mathit{s}\mathit{i}\mathit{t}\mathit{i}\mathit{o}\mathit{n}\right(u_i),\mathit{s}\mathit{p}\mathit{e}\mathit{e}\mathit{d}(u_i),\mathit{m}\mathit{a}\mathit{x}\mathit{d}\mathit{i}\mathit{s}\mathit{t}\mathit{a}\mathit{n}\mathit{c}\mathit{e}(u_i),\mathit{m}\mathit{a}\mathit{x}\mathit{r}\mathit{e}\mathit{s}\mathit{o}\mathit{u}\mathit{r}\mathit{c}\mathit{e}(u_i\left)\right)$, and a list of tasks $L=(t_1,t_2,\dots ,t_n)$, where $t_j=\left(\mathit{p}\mathit{o}\mathit{s}\mathit{i}\mathit{t}\mathit{i}\mathit{o}\mathit{n}\right(t_j),\mathit{p}\mathit{t}\mathit{i}\mathit{m}\mathit{e}(t_j),\mathit{d}\mathit{e}\mathit{a}\mathit{d}\mathit{l}\mathit{i}\mathit{n}\mathit{e}(t_j),\mathit{r}\mathit{e}\mathit{q}\mathit{u}\mathit{e}\mathit{s}\mathit{t}(t_j),reward(t_j\left)\right)$.

• Output: $\mathit{r}\mathit{o}\mathit{u}\mathit{t}\mathit{e}\left(u_i\right)$ for all i, such that R is maximised and $\mathit{c}\mathit{t}\mathit{i}\mathit{m}\mathit{e}\left(t_j\right)\le \mathit{d}\mathit{e}\mathit{a}\mathit{d}\mathit{l}\mathit{i}\mathit{n}\mathit{e}\left(t_j\right)$ for all j, $\mathit{d}\mathit{i}\mathit{s}\mathit{t}\mathit{a}\mathit{n}\mathit{c}\mathit{e}\left(u_i\right)\le \mathit{m}\mathit{a}\mathit{x}\mathit{d}\mathit{i}\mathit{s}\mathit{t}\mathit{a}\mathit{n}\mathit{c}\mathit{e}\left(u_i\right)$ for all i, and $\mathit{r}\mathit{e}\mathit{s}\mathit{o}\mathit{u}\mathit{r}\mathit{c}\mathit{e}\left(u_i\right)\le \mathit{m}\mathit{a}\mathit{x}\mathit{d}\mathit{i}\mathit{s}\mathit{t}\mathit{a}\mathit{n}\mathit{c}\mathit{e}\left(u_i\right)$ for all i.

It is clear that NFTM is a special case of RFTM (when all rewards are identical). Therefore, the RFTM problem is also NP-hard.

3. Heuristic algorithms

In this section, we develop our heuristic algorithms.

3.1. An algorithmic framework

In this section, we present an algorithmic framework for both NFTM and RFTM, such that our heuristic algorithms (four for NFTM and two for RFTM) can be presented in a unified way.

Algorithmic Framework

 

 

for (each $u_i$) do (1)

$\mathit{r}\mathit{o}\mathit{u}\mathit{t}\mathit{e}\left(u_i\right)\leftarrow$ an empty list; (2)

$\mathit{t}\mathit{i}\mathit{m}\mathit{e}\left(u_i\right)\leftarrow 0$; (3)

$\mathit{d}\mathit{i}\mathit{s}\mathit{t}\mathit{a}\mathit{n}\mathit{c}\mathit{e}\left(u_i\right)\leftarrow 0$; (4)

$\mathit{r}\mathit{e}\mathit{s}\mathit{o}\mathit{u}\mathit{r}\mathit{c}\mathit{e}\left(u_i\right)\leftarrow 0$; (5)

$\mathit{l}\mathit{o}\mathit{c}\mathit{a}\mathit{t}\mathit{i}\mathit{o}\mathit{n}\left(u_i\right)\leftarrow \mathit{p}\mathit{o}\mathit{s}\mathit{i}\mathit{t}\mathit{i}\mathit{o}\mathit{n}\left(u_i\right)$; (6)

end do; (7)

for (each $t_j$) do (8)

calculate $\mathit{b}\mathit{e}\mathit{s}\mathit{t}\left(t_j\right)$; (9)

end do; (10)

$N\leftarrow 0$; (11)

$R\leftarrow 0$; (12)

while (there is still task in L) do (13)

if ($\mathit{b}\mathit{e}\mathit{s}\mathit{t}\left(t_j\right)$ is undefined for all $t_j$ in L) (14)

break; (15)

find $t_j$ such that $\mathit{g}\mathit{a}\mathit{i}\mathit{n}\left(\mathit{b}\mathit{e}\mathit{s}\mathit{t}\right(t_j),t_j)$ is the (minimum for NFTM)/(maximum for

RFTM); (16)

$u_i\leftarrow \mathit{b}\mathit{e}\mathit{s}\mathit{t}\left(t_j\right)$; (17)

append $t_j$ to $\mathit{r}\mathit{o}\mathit{u}\mathit{t}\mathit{e}\left(u_i\right)$; (18)

remove $t_j$ from L; (19)

$N\leftarrow N+1$; (20)

$R\leftarrow R+\mathit{r}\mathit{e}\mathit{w}\mathit{a}\mathit{r}\mathit{d}\left(t_j\right)$; (21)

$\mathit{t}\mathit{i}\mathit{m}\mathit{e}\left(u_i\right)\leftarrow \mathit{t}\mathit{i}\mathit{m}\mathit{e}\left(u_i\right)+\mathit{f}\mathit{t}\mathit{i}\mathit{m}\mathit{e}(u_i,t_j)+\mathit{p}\mathit{t}\mathit{i}\mathit{m}\mathit{e}\left(t_j\right)$; (22)

$\mathit{d}\mathit{i}\mathit{s}\mathit{t}\mathit{a}\mathit{n}\mathit{c}\mathit{e}\left(u_i\right)\leftarrow \mathit{d}\mathit{i}\mathit{s}\mathit{t}\mathit{a}\mathit{n}\mathit{c}\mathit{e}\left(u_i\right)+\mathit{d}\mathit{i}\mathit{s}\mathit{t}\left(\mathit{l}\mathit{o}\mathit{c}\mathit{a}\mathit{t}\mathit{i}\mathit{o}\mathit{n}\right(u_i),\mathit{p}\mathit{o}\mathit{s}\mathit{i}\mathit{t}\mathit{i}\mathit{o}\mathit{n}(t_j\left)\right)$; (23)

$\mathit{r}\mathit{e}\mathit{s}\mathit{o}\mathit{u}\mathit{r}\mathit{c}\mathit{e}\left(u_i\right)\leftarrow \mathit{r}\mathit{e}\mathit{s}\mathit{o}\mathit{u}\mathit{r}\mathit{c}\mathit{e}\left(u_i\right)+\mathit{r}\mathit{e}\mathit{q}\mathit{u}\mathit{e}\mathit{s}\mathit{t}\left(t_j\right)$; (24)

$\mathit{l}\mathit{o}\mathit{c}\mathit{a}\mathit{t}\mathit{i}\mathit{o}\mathit{n}\left(u_i\right)\leftarrow \mathit{p}\mathit{o}\mathit{s}\mathit{i}\mathit{t}\mathit{i}\mathit{o}\mathit{n}\left(t_j\right)$; (25)

update $\mathit{g}\mathit{a}\mathit{i}\mathit{n}(u_i,t_j)$ and $\mathit{b}\mathit{e}\mathit{s}\mathit{t}\left(t_j\right)$ for all $t_j$ in L; (26)

end do; (27)

return N for NFTM or R for RFTM. (28)

 

We define a condition: $\begin{array}{rl}\mathit{f}\mathit{e}\mathit{a}\mathit{s}\mathit{i}\mathit{b}\mathit{l}\mathit{e}(u_i,t_j)& =\left(\mathit{t}\mathit{i}\mathit{m}\mathit{e}\right(u_i)+\mathit{f}\mathit{t}\mathit{i}\mathit{m}\mathit{e}(u_i,t_j)+\mathit{p}\mathit{t}\mathit{i}\mathit{m}\mathit{e}(t_j)\le \mathit{d}\mathit{e}\mathit{a}\mathit{d}\mathit{l}\mathit{i}\mathit{n}\mathit{e}(t_j\left)\right)\\ & \mathrm{a}\mathrm{n}\mathrm{d}\left(\mathit{d}\mathit{i}\mathit{s}\mathit{t}\mathit{a}\mathit{n}\mathit{c}\mathit{e}\right(u_i)+\mathit{d}\mathit{i}\mathit{s}\mathit{t}(location\left(u_i\right),position\left(t_j\right))\le \mathit{m}\mathit{a}\mathit{x}\mathit{d}\mathit{i}\mathit{s}\mathit{t}\mathit{a}\mathit{n}\mathit{c}\mathit{e}(u_i\left)\right)\\ & \mathrm{a}\mathrm{n}\mathrm{d}\left(\mathit{r}\mathit{e}\mathit{s}\mathit{o}\mathit{u}\mathit{r}\mathit{c}\mathit{e}\right(u_i)+\mathit{r}\mathit{e}\mathit{q}\mathit{u}\mathit{e}\mathit{s}\mathit{t}(t_j)\le \mathit{m}\mathit{a}\mathit{x}\mathit{r}\mathit{e}\mathit{s}\mathit{o}\mathit{u}\mathit{r}\mathit{c}\mathit{e}(u_i\left)\right),\end{array}$which means that based on its current situation, $u_i$ can flight to $t_j$ and process $t_j$, without violating any time deadline, flight distance, or resource consumption constraint.

Let $\mathit{g}\mathit{a}\mathit{i}\mathit{n}(u_i,t_j)$ be an evaluation function of $u_i$ and $t_j$, only if $\mathit{f}\mathit{e}\mathit{a}\mathit{s}\mathit{i}\mathit{b}\mathit{l}\mathit{e}(u_i,t_j)$ is true. The exact definition of $\mathit{g}\mathit{a}\mathit{i}\mathit{n}(u_i,t_j)$ depends on a specific algorithm.

We define $\mathit{b}\mathit{e}\mathit{s}\mathit{t}\left(t_j\right)$ to be the $u_i$ with the minimum/maximum $\mathit{g}\mathit{a}\mathit{i}\mathit{n}(u_i,t_j)$: $u_i=\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{m}\mathrm{i}\mathrm{n}/\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{m}\mathrm{a}\mathrm{x}\left\{gain\right(u_i,t_j\left)\right\},\mathrm{f}\mathrm{o}\mathrm{r}\mathrm{a}\mathrm{l}\mathrm{l}{u}_i\text{such that}\mathit{f}\mathit{e}\mathit{a}\mathit{s}\mathit{i}\mathit{b}\mathit{l}\mathit{e}(u_i,t_j)=\text{true},$where, for NFTM, we choose the minimum, and for RFTM, we choose the maximum. Note that $\mathit{b}\mathit{e}\mathit{s}\mathit{t}\left(t_j\right)$ is undefined, if there is no $u_i$ such that $\mathit{f}\mathit{e}\mathit{a}\mathit{s}\mathit{i}\mathit{b}\mathit{l}\mathit{e}(u_i,t_j)$ is true.

All our heuristic algorithms follow the same algorithmic framework. Lines (1)–(12) initialise the UAVs and the tasks. The main body of the algorithm is in lines (13)–(27). In each repetition of the while-loop, the $t_j$ which has the minimum $\mathit{g}\mathit{a}\mathit{i}\mathit{n}\left(\mathit{b}\mathit{e}\mathit{s}\mathit{t}\right(t_j),t_j)$ for NFTM or the maximum $\mathit{g}\mathit{a}\mathit{i}\mathit{n}\left(\mathit{b}\mathit{e}\mathit{s}\mathit{t}\right(t_j),t_j)$ for RFTM is identified (line (16)), i.e. a greedy method is adopted. Task $t_j$ is then assigned to $u_i=\mathit{b}\mathit{e}\mathit{s}\mathit{t}\left(t_j\right)$ (lines (17)–(21)), and the status of $u_i$ is updated (lines (22)–(25)). All remaining tasks also update their status (line (26)). The while-loop is repeated until there is no more task to schedule (line (13)) or no task can be scheduled anymore due to time deadline, flight distance, and resource consumption constraints (lines (14)–(15)).

It is clear that the most time-consuming step is line (26), which takes $O\left(mn\right)$ time. Since the while-loop can be repeated n times, the overall time complexity of the algorithm is $O\left(m{n}^2\right)$.

3.2. Algorithms for NFTM

In this section, we present four heuristic algorithms for the NFTM problem. Each algorithm has its own $\mathit{g}\mathit{a}\mathit{i}\mathit{n}(u_i,t_j)$.

• Algorithm 1: Earliest Deadline First (EDF) $\mathit{g}\mathit{a}\mathit{i}\mathit{n}(u_i,t_j)=\left(\mathit{d}\mathit{e}\mathit{a}\mathit{d}\mathit{l}\mathit{i}\mathit{n}\mathit{e}\right(t_j),\mathit{d}\mathit{i}\mathit{s}\mathit{t}(\mathit{l}\mathit{o}\mathit{c}\mathit{a}\mathit{t}\mathit{i}\mathit{o}\mathit{n}\left(u_i\right),\mathit{p}\mathit{o}\mathit{s}\mathit{i}\mathit{t}\mathit{i}\mathit{o}\mathit{n}\left(t_j\right))\times \mathit{r}\mathit{e}\mathit{q}\mathit{u}\mathit{e}\mathit{s}\mathit{t}(t_j\left)\right).$

• Algorithm 2: Shortest Distance First (SDF) $\mathit{g}\mathit{a}\mathit{i}\mathit{n}(u_i,t_j)=\left(\mathit{d}\mathit{i}\mathit{s}\mathit{t}\right(\mathit{l}\mathit{o}\mathit{c}\mathit{a}\mathit{t}\mathit{i}\mathit{o}\mathit{n}\left(u_i\right),\mathit{p}\mathit{o}\mathit{s}\mathit{i}\mathit{t}\mathit{i}\mathit{o}\mathit{n}\left(t_j\right)),\mathit{d}\mathit{e}\mathit{a}\mathit{d}\mathit{l}\mathit{i}\mathit{n}\mathit{e}(t_j)\times \mathit{r}\mathit{e}\mathit{q}\mathit{u}\mathit{e}\mathit{s}\mathit{t}(t_j\left)\right).$

• Algorithm 3: Least Request First (LQF) $\mathit{g}\mathit{a}\mathit{i}\mathit{n}(u_i,t_j)=\left(\mathit{r}\mathit{e}\mathit{q}\mathit{u}\mathit{e}\mathit{s}\mathit{t}\right(t_j),\mathit{d}\mathit{e}\mathit{a}\mathit{d}\mathit{l}\mathit{i}\mathit{n}\mathit{e}(t_j)\times \mathit{d}\mathit{i}\mathit{s}\mathit{t}(\mathit{l}\mathit{o}\mathit{c}\mathit{a}\mathit{t}\mathit{i}\mathit{o}\mathit{n}\left(u_i\right),\mathit{p}\mathit{o}\mathit{s}\mathit{i}\mathit{t}\mathit{i}\mathit{o}\mathit{n}\left(t_j\right)\left)\right).$

• Algorithm 4: EDF-SDF-LQF $\mathit{g}\mathit{a}\mathit{i}\mathit{n}(u_i,t_j)=\left(\mathit{d}\mathit{e}\mathit{a}\mathit{d}\mathit{l}\mathit{i}\mathit{n}\mathit{e}\right(t_j)\times \mathit{d}\mathit{i}\mathit{s}\mathit{t}(\mathit{l}\mathit{o}\mathit{c}\mathit{a}\mathit{t}\mathit{i}\mathit{o}\mathit{n}\left(u_i\right),\mathit{p}\mathit{o}\mathit{s}\mathit{i}\mathit{t}\mathit{i}\mathit{o}\mathit{n}\left(t_j\right))\times \mathit{r}\mathit{e}\mathit{q}\mathit{u}\mathit{e}\mathit{s}\mathit{t}(t_j),j).$

Note that the result of $\mathit{g}\mathit{a}\mathit{i}\mathit{n}(u_i,t_j)$ is a pair of values to break ties. To compare a pair, we define $(u_1,u_2)<(v_1,v_2)$ if and only if $(u_1<v_1)$, or, $(u_1=v_1)$ and $(u_2<v_2)$.

3.3. Algorithms for RFTM

In this section, we present two heuristic algorithms for the RFTM problem. Each algorithm has its own $\mathit{g}\mathit{a}\mathit{i}\mathit{n}(u_i,t_j)$.

• Algorithm 5: Highest Reward First (HRF) $\mathit{g}\mathit{a}\mathit{i}\mathit{n}(u_i,t_j)=\left(\mathit{r}\mathit{e}\mathit{w}\mathit{a}\mathit{r}\mathit{d}\right(t_j),1/(\mathit{d}\mathit{e}\mathit{a}\mathit{d}\mathit{l}\mathit{i}\mathit{n}\mathit{e}\left(t_j\right)\times \mathit{d}\mathit{i}\mathit{s}\mathit{t}\left(location\right(u_i),position(t_j\left)\right)\times \mathit{r}\mathit{e}\mathit{q}\mathit{u}\mathit{e}\mathit{s}\mathit{t}\left(t_j\right)\left)\right).$

• Algorithm 6: EDF-SDF-LQF-HRF $\begin{array}{rl}\mathit{g}\mathit{a}\mathit{i}\mathit{n}(u_i,t_j)& =\left(\mathit{r}\mathit{e}\mathit{w}\mathit{a}\mathit{r}\mathit{d}\right(t_j\left)/\right(\mathit{d}\mathit{e}\mathit{a}\mathit{d}\mathit{l}\mathit{i}\mathit{n}\mathit{e}\left(t_j\right)\times \mathit{d}\mathit{i}\mathit{s}\mathit{t}\left(\mathit{l}\mathit{o}\mathit{c}\mathit{a}\mathit{t}\mathit{i}\mathit{o}\mathit{n}\right(u_i),\mathit{p}\mathit{o}\mathit{s}\mathit{i}\mathit{t}\mathit{i}\mathit{o}\mathit{n}(t_j\left)\right)\\ & \times \mathit{r}\mathit{e}\mathit{q}\mathit{u}\mathit{e}\mathit{s}\mathit{t}\left(t_j\right)),1/j).\end{array}$

Note that Algorithms 5 and 6 become Algorithm 4 if all rewards are identical.

Similarly, to compare a pair, we define $(u_1,u_2)>(v_1,v_2)$ if and only if $(u_1>v_1)$, or, $(u_1=v_1)$ and $(u_2>v_2)$.

4. Upper bounds

In this section, we derive upper bounds for optimal solutions.

4.1. An upper bound for NFTM

In this section, we derive an upper bound for the optimal solution $N^{\ast }$ of the NFTM problem. We give three possible upper bounds and then take the minimum of them.

We define $N_t$ to be the number of $t_j$'s such that $\underset{1\le i\le m}{min}\left\{\mathit{d}\mathit{i}\mathit{s}\mathit{t}\right(\mathit{p}\mathit{o}\mathit{s}\mathit{i}\mathit{t}\mathit{i}\mathit{o}\mathit{n}\left(u_i\right),\mathit{p}\mathit{o}\mathit{s}\mathit{i}\mathit{t}\mathit{i}\mathit{o}\mathit{n}\left(t_j\right)\left)/\mathit{s}\mathit{p}\mathit{e}\mathit{e}\mathit{d}\right(u_i\left)\right\}+\mathit{p}\mathit{t}\mathit{i}\mathit{m}\mathit{e}\left(t_j\right)\le \mathit{d}\mathit{e}\mathit{a}\mathit{d}\mathit{l}\mathit{i}\mathit{n}\mathit{e}\left(t_j\right),$where the left-hand side is the minimum possible completion time of $t_j$. It is clear that $N\le N_t$.

We define $\mathit{D}\mathit{i}\mathit{s}\mathit{t}\mathit{a}\mathit{n}\mathit{c}\mathit{e}=\sum _{i=1}^m\mathit{m}\mathit{a}\mathit{x}\mathit{d}\mathit{i}\mathit{s}\mathit{t}\mathit{a}\mathit{n}\mathit{c}\mathit{e}\left(u_i\right).$Let $\mathit{d}\mathit{i}\mathit{s}\mathit{t}\left(t_j\right)$ be the minimum distance to reach $t_j$, i.e. $\mathit{d}\mathit{i}\mathit{s}\mathit{t}\left(t_j\right)=min\left\{\underset{1\le i\le m}{min}\right\{\mathit{d}\mathit{i}\mathit{s}\mathit{t}\left(\mathit{p}\mathit{o}\mathit{s}\mathit{i}\mathit{t}\mathit{i}\mathit{o}\mathit{n}\right(u_i),\mathit{p}\mathit{o}\mathit{s}\mathit{i}\mathit{t}\mathit{i}\mathit{o}\mathit{n}(t_j\left)\right)\},\underset{j^{\prime }\ne j}{min}\{\mathit{d}\mathit{i}\mathit{s}\mathit{t}\left(position\right(t_{j^{\prime }}),\mathit{p}\mathit{o}\mathit{s}\mathit{i}\mathit{t}\mathit{i}\mathit{o}\mathit{n}(t_j\left)\right)\left\}\right\},$where only those $u_i$'s with $\mathit{d}\mathit{i}\mathit{s}\mathit{t}\left(\mathit{p}\mathit{o}\mathit{s}\mathit{i}\mathit{t}\mathit{i}\mathit{o}\mathit{n}\right(u_i),\mathit{p}\mathit{o}\mathit{s}\mathit{i}\mathit{t}\mathit{i}\mathit{o}\mathit{n}(t_j\left)\right)/\mathit{s}\mathit{p}\mathit{e}\mathit{e}\mathit{d}\left(u_i\right)+\mathit{p}\mathit{t}\mathit{i}\mathit{m}\mathit{e}\left(t_j\right)\le \mathit{d}\mathit{e}\mathit{a}\mathit{d}\mathit{l}\mathit{i}\mathit{n}\mathit{e}\left(t_j\right)$are considered. Assume that $\mathit{d}\mathit{i}\mathit{s}\mathit{t}\left(t_1\right)<\mathit{d}\mathit{i}\mathit{s}\mathit{t}\left(t_2\right)<\cdots <\mathit{d}\mathit{i}\mathit{s}\mathit{t}\left(t_n\right).$Let $N_d=k$, where k is the largest integer satisfying: $\mathit{d}\mathit{i}\mathit{s}\mathit{t}\left(t_1\right)+\mathit{d}\mathit{i}\mathit{s}\mathit{t}\left(t_2\right)+\cdots +\mathit{d}\mathit{i}\mathit{s}\mathit{t}\left(t_k\right)\le \mathit{D}\mathit{i}\mathit{s}\mathit{t}\mathit{a}\mathit{n}\mathit{c}\mathit{e}.$It is clear that $N\le N_d$.

We define $\mathit{R}\mathit{e}\mathit{s}\mathit{o}\mathit{u}\mathit{r}\mathit{c}\mathit{e}=\sum _{i=1}^m\mathit{m}\mathit{a}\mathit{x}\mathit{r}\mathit{e}\mathit{s}\mathit{o}\mathit{u}\mathit{r}\mathit{c}\mathit{e}\left(u_i\right).$Assume that $\mathit{r}\mathit{e}\mathit{q}\mathit{u}\mathit{e}\mathit{s}\mathit{t}\left(t_1\right)<\mathit{r}\mathit{e}\mathit{q}\mathit{u}\mathit{e}\mathit{s}\mathit{t}\left(t_2\right)<\cdots <\mathit{r}\mathit{e}\mathit{q}\mathit{u}\mathit{e}\mathit{s}\mathit{t}\left(t_n\right),$where each $t_j$ satisfies $\underset{1\le i\le m}{min}\left\{\mathit{d}\mathit{i}\mathit{s}\mathit{t}\right(\mathit{p}\mathit{o}\mathit{s}\mathit{i}\mathit{t}\mathit{i}\mathit{o}\mathit{n}\left(u_i\right),\mathit{p}\mathit{o}\mathit{s}\mathit{i}\mathit{t}\mathit{i}\mathit{o}\mathit{n}\left(t_j\right)\left)/\mathit{s}\mathit{p}\mathit{e}\mathit{e}\mathit{d}\right(u_i\left)\right\}+\mathit{p}\mathit{t}\mathit{i}\mathit{m}\mathit{e}\left(t_j\right)\le \mathit{d}\mathit{e}\mathit{a}\mathit{d}\mathit{l}\mathit{i}\mathit{n}\mathit{e}\left(t_j\right).$Let $N_r=k$, where k is the largest integer satisfying: $\mathit{r}\mathit{e}\mathit{q}\mathit{u}\mathit{e}\mathit{s}\mathit{t}\left(t_1\right)+\mathit{r}\mathit{e}\mathit{q}\mathit{u}\mathit{e}\mathit{s}\mathit{t}\left(t_2\right)+\cdots +\mathit{r}\mathit{e}\mathit{q}\mathit{u}\mathit{e}\mathit{s}\mathit{t}\left(t_k\right)\le \mathit{R}\mathit{e}\mathit{s}\mathit{o}\mathit{u}\mathit{r}\mathit{c}\mathit{e}.$It is clear that $N\le N_r$.

To summarise, we get an upper bound for the NFTM problem: $N^{\ast }\le N_{ub}=min\{N_t,N_d,N_r\}$.

4.2. An upper bound for RFTM

In this section, we derive an upper bound for the optimal solution $R^{\ast }$ of the RFTM problem. We give three possible upper bounds and then take the minimum of them.

Let $time\left(t_j\right)$ be the minimum time to reach $t_j$ + the processing time of $t_j$: $\mathit{t}\mathit{i}\mathit{m}\mathit{e}\left(t_j\right)=\mathit{d}\mathit{i}\mathit{s}\mathit{t}\left(t_j\right)/\underset{1\le i\le m}{max}\left\{\mathit{s}\mathit{p}\mathit{e}\mathit{e}\mathit{d}\right(u_i\left)\right\}+\mathit{p}\mathit{t}\mathit{i}\mathit{m}\mathit{e}\left(t_j\right).$We define $\mathit{T}\mathit{i}\mathit{m}\mathit{e}=\sum _{i=1}^m\mathit{m}\mathit{a}\mathit{x}\mathit{t}\mathit{i}\mathit{m}\mathit{e}\left(u_i\right).$Assume that $\mathit{r}\mathit{e}\mathit{w}\mathit{a}\mathit{r}\mathit{d}\left(t_1\right)/\mathit{t}\mathit{i}\mathit{m}\mathit{e}\left(t_1\right)>\mathit{r}\mathit{e}\mathit{w}\mathit{a}\mathit{r}\mathit{d}\left(t_2\right)/\mathit{t}\mathit{i}\mathit{m}\mathit{e}\left(t_2\right)>\cdots >\mathit{r}\mathit{e}\mathit{w}\mathit{a}\mathit{r}\mathit{d}\left(t_n\right)/\mathit{t}\mathit{i}\mathit{m}\mathit{e}\left(t_n\right),$where each $t_j$ satisfies $\underset{1\le i\le m}{min}\left\{\mathit{d}\mathit{i}\mathit{s}\mathit{t}\right(\mathit{p}\mathit{o}\mathit{s}\mathit{i}\mathit{t}\mathit{i}\mathit{o}\mathit{n}\left(u_i\right),\mathit{p}\mathit{o}\mathit{s}\mathit{i}\mathit{t}\mathit{i}\mathit{o}\mathit{n}\left(t_j\right)\left)/\mathit{s}\mathit{p}\mathit{e}\mathit{e}\mathit{d}\right(u_i\left)\right\}+\mathit{p}\mathit{t}\mathit{i}\mathit{m}\mathit{e}\left(t_j\right)\le \mathit{d}\mathit{e}\mathit{a}\mathit{d}\mathit{l}\mathit{i}\mathit{n}\mathit{e}\left(t_j\right).$k is the largest integer satisfying: $\mathit{t}\mathit{i}\mathit{m}\mathit{e}\left(t_1\right)+\mathit{t}\mathit{i}\mathit{m}\mathit{e}\left(t_2\right)+\cdots +\mathit{t}\mathit{i}\mathit{m}\mathit{e}\left(t_k\right)\le \mathit{T}\mathit{i}\mathit{m}\mathit{e}.$Let $\begin{array}{rl}{R}_t& =\mathit{r}\mathit{e}\mathit{w}\mathit{a}\mathit{r}\mathit{d}\left(t_1\right)+\mathit{r}\mathit{e}\mathit{w}\mathit{a}\mathit{r}\mathit{d}\left(t_2\right)+\cdots +\mathit{r}\mathit{e}\mathit{w}\mathit{a}\mathit{r}\mathit{d}\left(t_k\right)\\ & +\left(\mathit{r}\mathit{e}\mathit{w}\mathit{a}\mathit{r}\mathit{d}\right(t_{k+1}\left)/\mathit{t}\mathit{i}\mathit{m}\mathit{e}\right(t_{k+1}\left)\right)(\mathit{T}\mathit{i}\mathit{m}\mathit{e}-(\mathit{t}\mathit{i}\mathit{m}\mathit{e}\left(t_1\right)+\mathit{t}\mathit{i}\mathit{m}\mathit{e}\left(t_2\right)+\cdots +\mathit{t}\mathit{i}\mathit{m}\mathit{e}\left(t_k\right)).\end{array}$It is clear that $R\le R_t$.

Assume that $\mathit{r}\mathit{e}\mathit{w}\mathit{a}\mathit{r}\mathit{d}\left(t_1\right)/\mathit{d}\mathit{i}\mathit{s}\mathit{t}\left(t_1\right)>\mathit{r}\mathit{e}\mathit{w}\mathit{a}\mathit{r}\mathit{d}\left(t_2\right)/\mathit{d}\mathit{i}\mathit{s}\mathit{t}\left(t_2\right)>\cdots >\mathit{r}\mathit{e}\mathit{w}\mathit{a}\mathit{r}\mathit{d}\left(t_n\right)/dist\left(t_n\right),$where each $t_j$ satisfies $\underset{1\le i\le m}{min}\left\{\mathit{d}\mathit{i}\mathit{s}\mathit{t}\right(\mathit{p}\mathit{o}\mathit{s}\mathit{i}\mathit{t}\mathit{i}\mathit{o}\mathit{n}\left(u_i\right),\mathit{p}\mathit{o}\mathit{s}\mathit{i}\mathit{t}\mathit{i}\mathit{o}\mathit{n}\left(t_j\right)\left)/\mathit{s}\mathit{p}\mathit{e}\mathit{e}\mathit{d}\right(u_i\left)\right\}+\mathit{p}\mathit{t}\mathit{i}\mathit{m}\mathit{e}\left(t_j\right)\le \mathit{d}\mathit{e}\mathit{a}\mathit{d}\mathit{l}\mathit{i}\mathit{n}\mathit{e}\left(t_j\right).$k is the largest integer satisfying: $\mathit{d}\mathit{i}\mathit{s}\mathit{t}\left(t_1\right)+\mathit{d}\mathit{i}\mathit{s}\mathit{t}\left(t_2\right)+\cdots +\mathit{d}\mathit{i}\mathit{s}\mathit{t}\left(t_k\right)\le \mathit{D}\mathit{i}\mathit{s}\mathit{t}\mathit{a}\mathit{n}\mathit{c}\mathit{e}.$Let $\begin{array}{rl}{R}_d& =\mathit{r}\mathit{e}\mathit{w}\mathit{a}\mathit{r}\mathit{d}\left(t_1\right)+\mathit{r}\mathit{e}\mathit{w}\mathit{a}\mathit{r}\mathit{d}\left(t_2\right)+\cdots +\mathit{r}\mathit{e}\mathit{w}\mathit{a}\mathit{r}\mathit{d}\left(t_k\right)\\ & +\left(reward\right(t_{k+1}\left)/\mathit{d}\mathit{i}\mathit{s}\mathit{t}\right(t_{k+1}\left)\right)(\mathit{D}\mathit{i}\mathit{s}\mathit{t}\mathit{a}\mathit{n}\mathit{c}\mathit{e}-(\mathit{d}\mathit{i}\mathit{s}\mathit{t}\left(t_1\right)+\mathit{d}\mathit{i}\mathit{s}\mathit{t}\left(t_2\right)+\cdots +\mathit{d}\mathit{i}\mathit{s}\mathit{t}\left(t_k\right)).\end{array}$It is clear that $R\le R_d$.

Assume that $\mathit{r}\mathit{e}\mathit{w}\mathit{a}\mathit{r}\mathit{d}\left(t_1\right)/\mathit{r}\mathit{e}\mathit{q}\mathit{u}\mathit{e}\mathit{s}\mathit{t}\left(t_1\right)>\mathit{r}\mathit{e}\mathit{w}\mathit{a}\mathit{r}\mathit{d}\left(t_2\right)/\mathit{r}\mathit{e}\mathit{q}\mathit{u}\mathit{e}\mathit{s}\mathit{t}\left(t_2\right)>\cdots >\mathit{r}\mathit{e}\mathit{w}\mathit{a}\mathit{r}\mathit{d}\left(t_n\right)/request\left(t_n\right),$where each $t_j$ satisfies $\underset{1\le i\le m}{min}\left\{\mathit{d}\mathit{i}\mathit{s}\mathit{t}\right(\mathit{p}\mathit{o}\mathit{s}\mathit{i}\mathit{t}\mathit{i}\mathit{o}\mathit{n}\left(u_i\right),\mathit{p}\mathit{o}\mathit{s}\mathit{i}\mathit{t}\mathit{i}\mathit{o}\mathit{n}\left(t_j\right)\left)/\mathit{s}\mathit{p}\mathit{e}\mathit{e}\mathit{d}\right(u_i\left)\right\}+\mathit{p}\mathit{t}\mathit{i}\mathit{m}\mathit{e}\left(t_j\right)\le \mathit{d}\mathit{e}\mathit{a}\mathit{d}\mathit{l}\mathit{i}\mathit{n}\mathit{e}\left(t_j\right).$k is the largest integer satisfying: $\mathit{r}\mathit{e}\mathit{q}\mathit{u}\mathit{e}\mathit{s}\mathit{t}\left(t_1\right)+\mathit{r}\mathit{e}\mathit{q}\mathit{u}\mathit{e}\mathit{s}\mathit{t}\left(t_2\right)+\cdots +\mathit{r}\mathit{e}\mathit{q}\mathit{u}\mathit{e}\mathit{s}\mathit{t}\left(t_k\right)\le \mathit{R}\mathit{e}\mathit{s}\mathit{o}\mathit{u}\mathit{r}\mathit{c}\mathit{e}.$Let $\begin{array}{rl}{R}_r& =\mathit{r}\mathit{e}\mathit{w}\mathit{a}\mathit{r}\mathit{d}\left(t_1\right)+\mathit{r}\mathit{e}\mathit{w}\mathit{a}\mathit{r}\mathit{d}\left(t_2\right)+\cdots +\mathit{r}\mathit{e}\mathit{w}\mathit{a}\mathit{r}\mathit{d}\left(t_k\right)\\ & +\left(\mathit{r}\mathit{e}\mathit{w}\mathit{a}\mathit{r}\mathit{d}\right(t_{k+1}\left)/\mathit{r}\mathit{e}\mathit{q}\mathit{u}\mathit{e}\mathit{s}\mathit{t}\right(t_{k+1}\left)\right)(\mathit{R}\mathit{e}\mathit{s}\mathit{o}\mathit{u}\mathit{r}\mathit{c}\mathit{e}-(\mathit{r}\mathit{e}\mathit{q}\mathit{u}\mathit{e}\mathit{s}\mathit{t}\left(t_1\right)+\mathit{r}\mathit{e}\mathit{q}\mathit{u}\mathit{e}\mathit{s}\mathit{t}\left(t_2\right)\\ & +\cdots +\mathit{r}\mathit{e}\mathit{q}\mathit{u}\mathit{e}\mathit{s}\mathit{t}\left(t_k\right)).\end{array}$It is clear that $R\le R_r$.

To summarise, we get an upper bound for the RFTM problem: $R^{\ast }\le R_{ub}=min\{R_t,R_d,R_r\}$.

5. Experimental performance evaluation

In this section, we conduct an experimental performance evaluation for our heuristic algorithms.

5.1. Parameter setting

Assume that a three-dimensional space $[-3000,3000]\times [-3000,3000]\times [0,300]$ has coordinates measured in meters (m). A position is specified as $(x,y,z)$. The distance between two positions $p_1=(x_1,y_1,z_1)$ and $p_2=(x_2,y_2,z_2)$ is $\mathit{d}\mathit{i}\mathit{s}\mathit{t}(p_1,p_2)=\sqrt{(x_1-x_2{)}^2+(y_1-y_2{)}^2+(z_1-z_2{)}^2}.$We consider m = 4 UAVs with the following parameters. The $\mathit{p}\mathit{o}\mathit{s}\mathit{i}\mathit{t}\mathit{i}\mathit{o}\mathit{n}\left(u_i\right)$'s are $(d,0,100)$, $(0,d,100)$, $(-d,0,100)$, $(0,-d,100)$, where d = 2000 m. The $\mathit{s}\mathit{p}\mathit{e}\mathit{e}\mathit{d}\left(u_i\right)$'s are i.i.d. random variables uniformly distributed in the range $[20,30]$ m/s. The $\mathit{m}\mathit{a}\mathit{x}\mathit{t}\mathit{i}\mathit{m}\mathit{e}\left(u_i\right)$'s are i.i.d. random variables uniformly distributed in the range $[1,2]$ hours, i.e. $[3600,7200]$ seconds. The $\mathit{m}\mathit{a}\mathit{x}\mathit{d}\mathit{i}\mathit{s}\mathit{t}\mathit{a}\mathit{n}\mathit{c}\mathit{e}\left(u_i\right)$'s are i.i.d. random variables uniformly distributed in the range $[72,216]$ km, i.e. $[72000,216000]$ m. The $\mathit{m}\mathit{a}\mathit{x}\mathit{r}\mathit{e}\mathit{s}\mathit{o}\mathit{u}\mathit{r}\mathit{c}\mathit{e}\left(u_i\right)$'s are i.i.d. random variables uniformly distributed in the range $[0.8,1.2]\times 10.5\times \left(n/m\right)$, where $10.5=(1+20)/2$.

The number of tasks is $n=20,40,\dots ,200$. The $\mathit{p}\mathit{o}\mathit{s}\mathit{i}\mathit{t}\mathit{i}\mathit{o}\mathit{n}\left(t_j\right)$'s are i.i.d. random variables uniformly distributed in the space $[-3000,3000]\times [-3000,3000]\times [0,300]$. The $\mathit{p}\mathit{t}\mathit{i}\mathit{m}\mathit{e}\left(t_j\right)$'s are i.i.d. random variables uniformly distributed in the range $[\tau ,2\tau ]$, where $\tau =30$, 50, 70, 90 s. The $\mathit{d}\mathit{e}\mathit{a}\mathit{d}\mathit{l}\mathit{i}\mathit{n}\mathit{e}\left(t_j\right)$'s are i.i.d. random variables uniformly distributed in the range $[600,6000]$ s, i.e. $[10,100]$ min. The $\mathit{r}\mathit{e}\mathit{q}\mathit{u}\mathit{e}\mathit{s}\mathit{t}\left(t_j\right)$'s are i.i.d. random variables uniformly distributed in the set $\{1,2,\dots ,20\}$. The $\mathit{r}\mathit{e}\mathit{w}\mathit{a}\mathit{r}\mathit{d}\left(t_j\right)$'s are i.i.d. random variables uniformly distributed in the set $\{1,2,\dots ,10\}$.

5.2. Simulation results

In this section, we show our simulation results.

In Tables 1–6, we demonstrate our experimental data for the six algorithms respectively. In each table, for each combination of n and τ, we generate M = 500 random samples of input (i.e. m random UAVs and n random tasks), execute the corresponding algorithm, calculate the upper bound $N_{ub}$ or $R_{ub}$, and record the ratio $N/N_{ub}$ or $R/R_{ub}$. The average of the M ratios is shown in the table, together with the maximum 99% confidence interval of all the data in the table.

Table 1. Simulation results of algorithm EDF (99% Confidence Interval $=\pm$0.46928%).

n	$\tau =30$	$\tau =50$	$\tau =70$	$\tau =90$
20	0.96879	0.96879	0.96879	0.96879
40	0.98300	0.98174	0.98313	0.98269
60	0.98621	0.98779	0.98669	0.98743
80	0.98874	0.98708	0.98900	0.98782
100	0.98894	0.98999	0.98904	0.98138
120	0.98874	0.98923	0.98095	0.91100
140	0.99018	0.98584	0.92321	0.80585
160	0.98890	0.95761	0.83408	0.71618
180	0.98612	0.89413	0.75084	0.64512
200	0.97099	0.82152	0.68318	0.58864

Table 2. Simulation results of algorithm SDF (99% Confidence Interval $=\pm$0.56354%).

n	$\tau =30$	$\tau =50$	$\tau =70$	$\tau =90$
20	0.96427	0.96304	0.96122	0.95682
40	0.98077	0.97127	0.95773	0.94147
60	0.97686	0.95861	0.93333	0.90358
80	0.96766	0.93646	0.90027	0.86006
100	0.95532	0.91155	0.86334	0.81139
120	0.93995	0.88432	0.82392	0.76838
140	0.92456	0.85614	0.79140	0.72371
160	0.90604	0.83067	0.75564	0.68581
180	0.89036	0.80217	0.72295	0.64858
200	0.87328	0.77614	0.69010	0.61395

Table 3. Simulation results of algorithm LQF (99% Confidence Interval $=\pm$0.65958%).

n	$\tau =30$	$\tau =50$	$\tau =70$	$\tau =90$
20	0.94659	0.94899	0.94869	0.94594
40	0.97213	0.96499	0.95492	0.94350
60	0.96773	0.94442	0.91920	0.89714
80	0.94702	0.90696	0.87351	0.82865
100	0.91255	0.86458	0.81323	0.76968
120	0.88618	0.82171	0.76416	0.71238
140	0.85169	0.78143	0.72001	0.66233
160	0.81928	0.74586	0.67831	0.61639
180	0.79194	0.71003	0.63661	0.57572
200	0.75945	0.67618	0.59904	0.53799

Table 4. Simulation results of algorithm EDF-SDF-LQF (99% Confidence Interval $=\pm$0.51538%).

n	$\tau =30$	$\tau =50$	$\tau =70$	$\tau =90$
20	0.95972	0.95982	0.95821	0.95772
40	0.98237	0.98140	0.97977	0.97578
60	0.98684	0.98371	0.97479	0.95891
80	0.98823	0.97656	0.95413	0.91940
100	0.98442	0.96106	0.91993	0.87167
120	0.97905	0.93774	0.88147	0.81223
140	0.96626	0.90575	0.83333	0.75970
160	0.95241	0.87554	0.79106	0.71064
180	0.93625	0.84094	0.74889	0.66408
200	0.91596	0.81025	0.70996	0.62270

Table 5. Simulation results of algorithm HRF (99% Confidence Interval $=\pm$0.61934%).

n	$\tau =30$	$\tau =50$	$\tau =70$	$\tau =90$
20	0.98581	0.98542	0.98431	0.98157
40	0.99186	0.98774	0.97966	0.97129
60	0.98514	0.97326	0.95532	0.93622
80	0.97147	0.94784	0.92281	0.89399
100	0.95395	0.92390	0.88792	0.85624
120	0.93422	0.89484	0.85166	0.81520
140	0.91448	0.86560	0.82076	0.77901
160	0.89281	0.83922	0.79080	0.75529
180	0.87456	0.81260	0.76273	0.74092
200	0.85233	0.79053	0.74130	0.73689

Table 6. Simulation results of algorithm EDF-SDF-LQF-HRF (99% Confidence Interval $=\pm$0.66539%).

n	$\tau =30$	$\tau =50$	$\tau =70$	$\tau =90$
20	0.96337	0.96337	0.96350	0.96547
40	0.98614	0.98675	0.98471	0.98190
60	0.99171	0.98761	0.98031	0.96884
80	0.99172	0.98093	0.96153	0.93703
100	0.98772	0.96713	0.93266	0.89437
120	0.98198	0.94844	0.90143	0.84890
140	0.97118	0.92401	0.86701	0.80946
160	0.95940	0.90033	0.83054	0.77652
180	0.94628	0.87335	0.80160	0.76125
200	0.93124	0.84747	0.77305	0.74723

We have the following observations.

• For the NFTM problem, when n and τ are small, Algorithm EDF has the best performance in the sense that it has the highest $N/N_{ub}$ ratio. As n and τ increase, Algorithm EDF-SDF-LQF performs the best.

• For the RFTM problem, Algorithm EDF-SDF-LQF-HRF consistently has the best performance in the sense that it has the highest $R/R_{ub}$ ratio.

• For all algorithms, as n and τ increase, the ratios $N/N_{ub}$ and $R/R_{ub}$ decrease, because the number of completed tasks decreases due to more tasks missing their time deadlines and insufficient flight distance and resource supplies.

• Since N and R are compared with $N_{ub}$ and $R_{ub}$ respectively, the actual performance ratios $N/N^{\ast }$ or $R/R^{\ast }$ should be higher than those in the tables.

6. Summary

For the first time in the literature, we have investigated optimal task scheduling for heterogeneous UAVs with completion time, flight distance, and resource consumption constraints within the framework of combinatorial optimisation. Our study has three unique features. First, we consider multiple resource and requirement constraints simultaneously. Second, we develop an algorithmic framework for all our heuristic algorithms. Third, we compare our heuristic solutions with optimal solutions.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Appendix

Table A1. Notations and definitions.

Notation	Definition
m	number of UAVs
n	number of tasks
$u_i$	a UAV
$\mathit{p}\mathit{o}\mathit{s}\mathit{i}\mathit{t}\mathit{i}\mathit{o}\mathit{n}\left(u_i\right)$	initial location of $u_i$
$\mathit{s}\mathit{p}\mathit{e}\mathit{e}\mathit{d}\left(u_i\right)$	flight speed of $u_i$
$\mathit{m}\mathit{a}\mathit{x}\mathit{d}\mathit{i}\mathit{s}\mathit{t}\mathit{a}\mathit{n}\mathit{c}\mathit{e}\left(u_i\right)$	the maximum flight distance of $u_i$
$\mathit{m}\mathit{a}\mathit{x}\mathit{r}\mathit{e}\mathit{s}\mathit{o}\mathit{u}\mathit{r}\mathit{c}\mathit{e}\left(u_i\right)$	the maximum resource consumption of $u_i$
$\mathit{m}\mathit{a}\mathit{x}\mathit{t}\mathit{i}\mathit{m}\mathit{e}\left(u_i\right)$	the maximum flight time of $u_i$
$\mathit{r}\mathit{o}\mathit{u}\mathit{t}\mathit{e}\left(u_i\right)$	flight route of $u_i$, $=(t_{i,1},t_{i,2},\dots ,t_{i,n_i})$, a sequence of tasks
$\mathit{d}\mathit{i}\mathit{s}\mathit{t}\mathit{a}\mathit{n}\mathit{c}\mathit{e}\left(u_i\right)$	total flight distance of $u_i$
$\mathit{f}\mathit{t}\mathit{i}\mathit{m}\mathit{e}\left(u_i\right)$	total flight time of $u_i$
$\mathit{p}\mathit{t}\mathit{i}\mathit{m}\mathit{e}\left(u_i\right)$	total processing time of $u_i$
$\mathit{t}\mathit{i}\mathit{m}\mathit{e}\left(u_i\right)$	total time of $u_i$, i.e.(total flight time + total processing time) of $u_i$
$\mathit{r}\mathit{e}\mathit{s}\mathit{o}\mathit{u}\mathit{r}\mathit{c}\mathit{e}\left(u_i\right)$	total resource consumption of $u_i$
$\mathit{l}\mathit{o}\mathit{c}\mathit{a}\mathit{t}\mathit{i}\mathit{o}\mathit{n}\left(u_i\right)$	current location of $u_i$
L	a list of tasks
$t_j$	a task
$\mathit{p}\mathit{o}\mathit{s}\mathit{i}\mathit{t}\mathit{i}\mathit{o}\mathit{n}\left(t_j\right)$	position of $t_j$
$\mathit{p}\mathit{t}\mathit{i}\mathit{m}\mathit{e}\left(t_j\right)$	processing time of $t_j$
$\mathit{d}\mathit{e}\mathit{a}\mathit{d}\mathit{l}\mathit{i}\mathit{n}\mathit{e}\left(t_j\right)$	time deadline to complete $t_j$
$\mathit{r}\mathit{e}\mathit{q}\mathit{u}\mathit{e}\mathit{s}\mathit{t}\left(t_j\right)$	amount of resource request of $t_j$
$\mathit{r}\mathit{e}\mathit{w}\mathit{a}\mathit{r}\mathit{d}\left(t_j\right)$	reward of completing $t_j$
$\mathit{c}\mathit{t}\mathit{i}\mathit{m}\mathit{e}\left(t_j\right)$	completion time of $t_j$
$\mathit{d}\mathit{i}\mathit{s}\mathit{t}\left(t_j\right)$	the minimum distance to reach $t_j$
$\mathit{t}\mathit{i}\mathit{m}\mathit{e}\left(t_j\right)$	the minimum time to reach $t_j$ + the processing time of $t_j$
$\mathit{b}\mathit{e}\mathit{s}\mathit{t}\left(t_j\right)$	the $u_i$ with the minimum/maximum $\mathit{g}\mathit{a}\mathit{i}\mathit{n}(u_i,t_j)$
$\mathit{d}\mathit{i}\mathit{s}\mathit{t}(p,q)$	distance between locations p and q
$\mathit{f}\mathit{t}\mathit{i}\mathit{m}\mathit{e}(u_i,t_j)$	flight time from $u_i$ to $t_j$
F	the set of finished tasks
N	the number of finished tasks
$N^{\ast }$	the optimal solution of the NFTM problem
$N_t,N_d,N_r,N_{ub}$	upper bounds for $N^{\ast }$
R	the total reward of finished tasks
$R^{\ast }$	the optimal solution of the RFTM problem
$R_t,R_d,R_r,R_{ub}$	upper bounds for $R^{\ast }$
$\mathit{D}\mathit{i}\mathit{s}\mathit{t}\mathit{a}\mathit{n}\mathit{c}\mathit{e}$	the sum of $\mathit{m}\mathit{a}\mathit{x}\mathit{d}\mathit{i}\mathit{s}\mathit{t}\mathit{a}\mathit{n}\mathit{c}\mathit{e}\left(u_i\right)$ for all $u_i$'s
$\mathit{R}\mathit{e}\mathit{s}\mathit{o}\mathit{u}\mathit{r}\mathit{c}\mathit{e}$	the sum of $\mathit{m}\mathit{a}\mathit{x}\mathit{r}\mathit{e}\mathit{s}\mathit{o}\mathit{u}\mathit{r}\mathit{c}\mathit{e}\left(u_i\right)$ for all $u_i$'s
$\mathit{T}\mathit{i}\mathit{m}\mathit{e}$	the sum of $\mathit{m}\mathit{a}\mathit{x}\mathit{t}\mathit{i}\mathit{m}\mathit{e}\left(u_i\right)$ for all $u_i$'s