## 3 Description of the Problem  
Let \(J_{1}\),..., \(J_{n}\) be a set of \(n\) tasks (e.g., flights) that must be carried out periodically by a fleet of drones, and let \(p\) denote a given period length. Associated with task \(J_{i}\) are non-negative real numbers \(a_{i}\) and \(b_{i}\) such that \(a_{i}<p\) and \(b_{i}<p\), where \(a_{i}\) and \(b_{i}\) are the start  
Figure 1: Schematic diagram of the proposed fast algorithm.  
and finish times of task \(J_{i}\) in the time interval \([0,\,p)\), respectively. If \(a_{i}<b_{i}\), then the \(k\)th iteration (or instance) of task \(J_{i}\) is executed in the time interval \([a_{i}+kp,\,b_{i}+kp)\). If \(a_{i}>b_{i}\), then the \(k\)th iteration of task \(J_{i}\) is performed in the time interval \([a_{i}+kp,\,b_{i}+(k+1)p)\), for \(k=0,\,1,\,2,\,\ldots\). Thus, the times \(a_{i},\,b_{i},\,i=1,\,\ldots,\,n\), define a predetermined periodic schedule for all tasks.  
Any task can be conducted by any autonomous vehicle, and any vehicle can carry out any task. We use this assumption to simplify the presentation of our algorithm, though, in fact, the proposed general graph approach can be extended to handle multiple aircraft types and efficiently solve other combinatorial problems. There is a known setup time \(r_{ij}\) between the sequential processing of instances of task \(J_{i}\) and task \(J_{j}\) by the same vehicle. The setup time \(r_{ij}\) is the required delay between the arrival of flight \(J_{i}\) and the departure of flight \(J_{j}\), assuming the same aircraft is used for both flights. It is allowed that the arrival site \(s\) for flight \(J_{i}\) may differ from the departure site \(t\) for flight \(J_{j}\); in this case, the setup time \(r_{ij}\) will include the deadhead time from \(s\) to \(t\).  
Unlike the known models mentioned above, this study takes into account not only the size of the fleet but also the environmental _benefit_ (profit) accrued from using the UAV fleet, which depends on the fleet size and the assignment of tasks performed by the vehicles. Suppose that profit \(e_{ij}\) is accrued from the use of a UAV when performing task \(J_{j}\) following task \(J_{i}\); this quantity is known in advance, while the number of vehicles and the assignment of tasks to vehicles are the decision variables that need to be found.  
Let \(K\) be the (unknown) number of vehicles required to meet a periodic fixed schedule, and let \(E\) be the total environmental profit obtained by all vehicles over period \(p\). Then our problem to be solved is the following:  
**Problem 1**.: _Assign tasks to vehicles so as to maximize the ratio._  
\[E/K\ =\ \frac{\mbox{Total environmental benefit accrued from the use of the UAV fleet over period $p$}}{\mbox{Number of vehicles required to meet a fixed schedule of tasks}},\]  
_That is, to maximize the average benefit obtained by the fleet of vehicles over the period for a given task schedule, which is defined by the known times \(\{a_{i},\,b_{i},\,i=1,\,\ldots\,n\}\)._  
**Remark 1**.: _In the verbal formulation of Problem 1 above, we do not reveal the explicit dependence of the total environmental benefit on the distribution of vehicles among tasks. This will be explained and formalized below in Problems **4** and **FAP** in the following sections._  
**Remark 2**.: _The reader may notice that the problem under consideration in its current formulation resembles the well-known vehicle allocation problem. The latter problem, in its various forms, is known to be NP-hard (see, for example, [8; 20; 25; 26]). However, in this paper, we will prove that the problem under study can be solved in polynomial time; this is because this problem has a special structure that greatly reduces the problem's complexity._