# Allocating Small Transporters to Large Jobs
## 3 Structural Results
### NP-Hardness of \((\mathrm{TAP})\)  
Unfortunately, \((\mathrm{TAP})\) is NP-hard in the strong sense, i.e., not solvable in time polynomial in the size of the input, even if the input is encoded in unary encoding, unless \(\mathrm{P}=\mathrm{NP}\), cf. [11]. In fact, we prove below that for an instance of \((\mathrm{TAP})\) it is, in general, strongly NP-hard to compute even a single point on the Pareto frontier. Let \((\mathrm{TAP}_{C^{*}}(n_{r}))\)be the decision version of (TAP) with target makespan \(C^{*}\). That is, given an instance of \((\text{TAP})\) and a target makespan \(C^{*}\), the task for \((\text{TAP}_{C^{*}}(n_{r}))\) is to decide if there exists an assignment of transporters to jobs such that the makespan is at most \(C^{*}\), and at most, \(n_{r}\) transporters are used. Theorem 1: \((\text{TAP}_{C^{*}}(n_{r}))\) _is NP-complete in the strong sense, even if \(C^{*}\) is chosen as the minimum possible makespan, i.e., \(C^{*}=\max_{j}\{C^{\text{sat}}(j)\}\). Moreover, it remains NP-complete in the strong sense, even if all jobs have the same return time and/or saturated processing time. Finally, it remains NP-complete in the strong sense even if it reduces to the decision if a saturating assignment exists, i.e., with parameters \(C^{*}=C^{\text{sat}}(1)=C^{\text{sat}}(2)=\ldots=C^{\text{sat}}(N_{J})\) and \(n_{r}=N_{R}\)._  
Proof: Reduction from three-partition problem, which is NP-complete in the strong sense [11]: Given a multiset \(S\) of \(n=3\cdot m\) positive integers, can \(S\) be partitioned into \(m\) triplets \(S_{1}\), \(S_{2},\ldots,S_{m}\) such that the sum of the numbers in each subset is equal? The subsets \(S_{1}\), \(S_{2},\ldots,S_{m}\) must form a partition of \(S\) in the sense that they are disjoint and they cover \(S\). Let \(B\) denote the (desired) sum of each subset \(S_{i}\), or equivalently, let the total sum of the numbers in \(S\) be \(m\cdot B\). The three-partition problem remains strongly NP-complete when every integer in \(S\) is strictly between \(\frac{B}{4}\) and \(\frac{B}{2}\). Let (I) be an arbitrary instance of three-partition with \(S=s_{1},\ldots,s_{3\cdot m}\) and \(\sum_{i}s_{i}=m\cdot B\) and \(B/4<s_{i}<B/2\). Let \(M\) be an arbitrary large positive integer with \(M>m\cdot B\). Let \(S^{\prime}\) be the multiset defined by \(S+K\) with \(K\) being the multiset \(\{M,\ldots,M\}\) with \(|K|=2\cdot m\). Hence, \(|S^{\prime}|=5\cdot m\). In the following, we refer to the elements from \(K\) as the _large_ elements. Define now an instance of \((\text{TAP}_{C^{*}}(n_{r}))\) with the set of resources \(\mathcal{R}\) with filling times \(\kappa(t_{i})=s^{\prime}_{i}\). The job set \(\mathcal{J}\) has cardinality \(m\) and the return times \(\delta(j)=B+M\) and saturated processing times \(C^{\text{sat}}(j)=B+M+M\) for all jobs \(j\in\mathcal{J}:=\{j_{1},\ldots,j_{m}\}\). Note that, by construction, all jobs have the same return time and the same saturated processing time. We need to prove the following:  
\[(I)\text{ has a solution }\Leftrightarrow(\text{TAP}_{B+M+M}(5\cdot m))\text{ has answer yes.}\]  
\(\Rightarrow\): Given a solution \(S_{1},\ldots,S_{m}\) (i.e., a set of triplets with the desired properties) to the three-partition instance (I), we can easily construct a solution to (TAP) by first assigning the transporters with the filling times corresponding to \(S_{i}\) to the job \(j_{i}\). Then, each job is additionally assigned to two of the transporters of size \(M\). Since by definition \(\sum_{c\in S_{i}}s=B\), the return time of \(B+M\) is covered exactly by the four smallest elements, meaning each job is saturated and no idle time occurs. By definition of the saturated processing times, this means the makespan of the constructed solution is exactly \(B+M+M\). \(\Leftarrow\): Let \(\overline{X}_{r,j}\) be a solution to \((\text{TAP})\) with makespan \(B+M+M\) and \(5\cdot m\) resources used. By definition of our instance, all \(m\) jobs must be saturated in order to reach makespan \(B+M+M\).