# Fair Task Allocation When Cost of Task Is Multidimensional
## 3 Problem Solution
### Finding an Approximate Maximin Fair Allocation  
We allocate tasks to UAVs by employing an improved Round-Robin algorithm. To make the algorithm easier to understand, we briefly show some of the main steps of the algorithm through an algorithm flowchart.  
The detailed process of the algorithm will be described in the following and the pseudocode of the algorithm has been shown in Algorithm 1.  
1. Input and Output In the input phase, we enter a set \(N\) containing \(n\) UAVs and a set \(M\) containing \(m\) tasks. For each UAV, it cotains the UAV's preference on three types of cost from tasks and the UAV's weights for costs. In addition, the relationship between different types of cost, which have been defined in Equations (7) and (8), are also be entered. The output is allocated task set \(P_{i}\) for each \(U_{i}\).
2. Importance assessment Line 3-5 in Algorithm 1 calculated the proportion of time cost, energy cost, and service cost in total cost. Although some information is unknown, we are able to calculate the minimum proportion of each type of cost.  
3. Task selection Line 6-18 in Algorithm 1 indicate that the UAVs select a task based on their preferences. In each round, each UAV selects only one task which has minimal cost on it. Lines 19-20 indicate the loop termination when all tasks are allocated.  
**Example 7**.: (_Continues from Example 6) Here, we assume that the task set with \(2\) tasks \(M=\{T[1],T[2]\}\) to be allocated to the UAV set with \(2\) UAVs \(N=\{U_{1},U_{2}\}\). It is known that each unit of time cost generates \(1\)-\(2\) units of energy cost and service life cost._  
_In first round, \(U_{1}\) chooses a task. Because the weight of \(U_{1}\) is (\(0.2\), \(0.2\), \(0.6\)), then according to the \(3\)-\(5\) lines of Algorithm 1, we can calculate that \(\beta_{1}(t)=1/9;\beta_{1}(e)=1/8;\beta_{1}(l)=1/2\). As \(\beta_{1}(l)\) is the biggest of \(\{\beta_{1}(t);\beta_{1}(e);\beta_{1}(l)\}\), \(U_{1}\) selects the task according to its preferences in life cost._  
_Then, \(P_{1}\gets P_{1}\cup\{T[1]\}\) and \(M\gets M\setminus\{T[1]\}\)._  
_Similarly, all UAVs in set \(N\) select a task in the manner described above cyclically until \(M\) is empty._  
```
0:\(n\) UAVs, \(m\) tasks
0: An allocation \(P=(P_{1},P_{2},...,P_{n})\)
1:\(i=1\)
2:while\(i\leq n\)do
3:\(\beta_{i}(t)=\frac{w_{i}(t)}{w_{i}(t)+w_{i}(e)\cdot K_{\ell x}+w_{i}(l)\cdot K _{\ell j}}\)
4:\(\beta_{i}(e)=\frac{w_{i}(e)\cdot k_{\ell x}}{w_{i}(t)+w_{i}(e)\cdot k_{\ell x} +w_{i}(l)\cdot K_{\ell j}}\)
5:\(\beta_{i}(l)=\frac{w_{i}(l)\cdot k_{\ell j}}{w_{i}(t)+w_{i}(e)\cdot K_{\ell x} +w_{i}(l)\cdot k_{\ell j}}\)
6:if\(\beta_{i}(t)=max\{\beta_{i}(t),\beta_{i}(e),\beta_{i}(l)\}\)then
7:\(T[j]\leftarrow\) the task has minimal time cost on \(i\) in \(M\)
8:elseif\(\beta_{i}(e)=max\{\beta_{i}(t),\beta_{i}(e),\beta_{i}(l)\}\)then
9:\(T[j]\leftarrow\) the task has minimal energy cost on \(i\) in \(M\)
10:else
11:\(T[j]\leftarrow\) the task has minimal service life cost on \(i\) in \(M\)
12:endif
13:\(P_{i}\gets P_{i}\cup\{T[j]\}\)
14:\(M\gets M\setminus\{T[j]\}\)
15:if\(M=\emptyset\)then
16: break
17:elseif\(i>n\)then
18:\(i=1\)
19:else
20:\(i=i+1\)
21:endif
22:endwhile
23:Return \(P\)
```  
**Algorithm 1** Improved Round-Robin Algorithm