# Allocating Small Transporters to Large Jobs
## 4 The Homogeneous Transporter Allocation Problem
However, by construction, at this point in time, the algorithm assignment is such that the completion time of every job is smaller than or equal to this duration. This contradicts the assumption that the maximum completion time with \(\overline{Y}^{*}\) is strictly lower than with \(\overline{X}\), hence that \(\overline{Y}^{*}\) is optimal. Additionally, Algorithm (Hom) has the runtime as claimed above. Theorem 2.3: _Algorithm (Hom) runs in time \(\mathcal{O}\big{(}(N_{R}+N_{J})\cdot\log[N_{J}]\big{)}\)._  
Proof: We first compute the partial assignment of one transporter per job in \(\mathcal{O}(N_{J})\). Then, for at most \(N_{R}\) iterations, we adjust the longest job and reorder the sorted list. Computing the completion time of a job takes \(\mathcal{O}(1)\) time by Equation (5). If we store job completion times in a heap data structure in \(\mathcal{O}(N_{J}\cdot\log[N_{J}])\), then every iteration is performed in \(\mathcal{O}(\log[N_{J}])\). Thus, the total time complexity is \(\mathcal{O}((N_{R}+N_{J})\cdot\log[N_{J}])\). Together, Theorems 2.2 and 2.3 prove our initial proposition. **Corollary 1**. : _For a homogeneous instance of \((\mathrm{TAP})\), the full frontier of Pareto optimal solutions can be computed in \(\mathcal{O}((N_{R}+N_{I})\cdot\log[N_{I}])\) time._  
Note that in the homogeneous \((\mathrm{TAP})\), the set of transporters can be encoded in \(\log[N_{R}]\) space by simply encoding the number of transporters (all transporters are of the same type). Thus, technically, a runtime of \(\mathcal{O}\big{(}(N_{R}+N_{I})\cdot\log[N_{I}]\big{)}\) is not polynomial in the input length. On the other hand, for a generic instance, a Pareto frontier has \(\mathcal{O}(N_{R})\) points, so it cannot be put out in less than \(\mathcal{O}(N_{R})\) steps. In scheduling, this is usually referred to as a high-multiplicity problem, see [28]. One way to resolve this issue is to show that any single Pareto point can be computed in polynomial time (with an algorithm that is at most logarithmic in \(N_{R}\)). For our algorithm, note that any single iteration of step 2 runs in \(\mathcal{O}(\log[N_{I}])\) time and that a new Pareto point is found at least every \(N_{I}\) such iterations (after each job is assigned one more transporter). Thus, our algorithm moves from one Pareto point to the next in polynomial time. Still, in order to compute a particular point, using at most \(m\) transporters, with Algorithm \((\mathrm{HOM})\), we need \(\mathcal{O}\big{(}(m+N_{I})\cdot\log[N_{I}]\big{)}\) steps, which is not polynomial when \(m=\mathcal{O}(N_{R})\). Instead, one can compute for a given makespan exactly the number of transporters needed to be assigned to each job via Equation (5) and then check if the total number of transporters does not exceed the given upper bound. For any given makespan, this check can be run in \(\mathcal{O}(N_{I})\) time, running one computation for each job. Then, via binary search using this computation at each step, one obtains a polynomial algorithm to compute a particular point on the Pareto frontier. To be precise, the obtained algorithm runs in \(\mathcal{O}\big{(}N_{I}\cdot\log[\max_{j}\{C(j,1)\}]\big{)}\), where \(C(j,1)\) denotes the processing time of a job when exactly one transporter is assigned to it. However, our primary goal is to compute the Pareto frontier as a whole, for which Algorithm \((\mathrm{HOM})\) is better suited than iteratively using the suggested binary search algorithm, which would take \(\mathcal{O}\big{(}N_{R}\cdot N_{I}\cdot\log[\max_{j}\{C(j,1)\}]\big{)}\) time.