## 5 R-DPAP: Resource-Constrained Directed Path Allocation Problems
### Theoretical Complexity  
**Proposition 3**. : _The R-DPAP-util-dec problem, which consists in determining whether, for a given \(R\)-DPAP problem, there exists an allocation \(\pi\) and start time functions \(\tau_{\pi,g}\) such that \(\pi\) is valid and utilitarian evaluation \(u(\pi)\) is greater than or equal to a given value, is NP-complete._  
Proof. : Given an R-DPAP, an allocation \(\pi\) for it, a start time function \(\tau_{\pi,g}\) for each graph \(g\), and a utility lower bound \(L\), verifying that the scheduling constraints are satisfied and that  
Figure 5: Orbit slot allocation problem involving two satellites \(sat_{1}\) and \(sat_{2}\) and two agents A and B that each have one request, denoted a and b, respectively. Two observation slots with a duration equal to 2 must be allocated for each request (represented by _[_2_]_ in each observation slot). The first orbit slot of each request should be around time 3 and the second one around time 9. (**a**) Graphs \(g_{\text{a}}\) and \(g_{\text{b}}\) representing the requests and resources of Example 4. (**b**) Description of the resources, time windows, and durations associated with the vertices of graphs \(g_{\text{a}}\) and \(g_{\text{b}}\). Figure 6: Valid allocation example, \(\pi_{\text{ev}}\), for the R-DPAP described in Example 4. (**a**) Illustration of allocation \(\pi_{\text{ex}}\) with the paths selected for graphs \(g_{\text{a}}\) and \(g_{\text{b}}\). (**b**) Start dates that allow the selection of the nodes of \(\pi_{\text{ex}}\) without any conflict in resources. \(u(\pi)\) is greater than or equal to \(L\) is polynomial. This proves that R-DPAP-util-dec is in class NP. To prove the NP-completeness of R-DPAP-util-dec, we rely on the fact that the one-machine scheduling problem with release dates and due dates in which the objective is to minimize the maximum lateness of jobs is NP-complete [21]. Let \(\langle A,P,R,D\rangle\) be such a problem where:  
* \(A=\{a_{1},\ldots,a_{n}\}\) is a set of activities;
* \(P:A\rightarrow\mathbb{N}\) is a function that assigns a processing time to each activity of \(A\);
* \(R:A\rightarrow\mathbb{N}\) is a function that assigns a release date to each activity of \(A\);
* \(D:A\rightarrow\mathbb{N}\) is a function that assigns a due date to each activity of \(A\). The objective of the problem is to define a function \(\sigma:A\rightarrow\mathbb{N}\) that assigns a start date \(\sigma(a)\) to each activity \(a\) in \(A\) such that:  
* the release dates are satisfied, i.e., \(\forall a\in A\), \(\sigma(a)\geq R(a)\);
* the machine performs at most one activity at each time step, i.e., \(\forall a_{i},a_{j}\in A^{2}\) with \(i\
eq j\), either \(\sigma(a_{i})+R(a_{i})\leq\sigma(a_{j})\) or \(\sigma(a_{j})+R(a_{j})\leq\sigma(a_{i})\) holds;
* the maximum lateness \(L_{max}\) is minimized, where \(L_{max}=\max_{i=1}^{n}(\sigma(a_{i})+P(a_{i})-D(a_{i}))\). In the associated decision problem, we consider a bound \(l\), and the objective is to decide if it is possible to define \(\sigma\) such that \(L_{max}\leq l\). Such a problem can be transformed to an R-DPAP as follows:  
* we consider a unique resource \(r\);
* we consider an agent \(\mathit{agent}_{a}\) for each activity \(a\) in \(A\);
* for each activity \(a\) in \(A\), we consider the graph \(g_{a}\) (illustrated in Figure 7a) that belongs to agent \(\mathit{agent}_{a}\) and that has the following features:
* its set of vertices is composed of three nodes: \(s_{a}\), \(t_{a}\), and \(v_{a}\);
* its set of edges is composed of \((s_{a},v_{a})\) with a utility equal to \(1\), and \((s_{a},t_{a})\), \((v_{a},t_{a})\) that both have a null utility;
* as illustrated in Figure 7b, node \(v_{a}\) requires resource \(r\) during \(D(a)\) time units within time window \([R(a),D(a)+l]\);
* the obtained R-DPAP is \(\langle\{\mathit{agent}_{a}\mid a\in A\},\{r\},\{g_{a}\mid a\in A\},\mu\rangle\), with \(\mu\) a function that assigns, for each activity \(a\) in A, agent \(\mathit{agent}_{a}\) to graph \(g_{a}\).