# Allocating Small Transporters to Large Jobs
## 4 The Homogeneous Transporter Allocation Problem  
In this section, we consider the special case of \((\mathrm{TAP})\) in which all transporters have the same filling time \(\kappa\). We call instances of \((\mathrm{TAP})\) that fulfill this condition _homogeneous_. Note that in this case, the saturating transporter cardinality \(N_{\mathcal{R}}^{*}(j)\) of job \(j\) can be computed in \(O(1)\) by the equation:  
\[N_{\mathcal{R}}^{*}(j):=\left\lceil\frac{\delta(j)}{\kappa}\right\rceil+1. \tag{4}\]  
That means that the saturating transporter cardinality of all jobs can be computed in \(O(N_{J})\) instead of \(O\big{(}(N_{R}+N_{J})\cdot\log[N_{R}]\big{)}\) as in the general case. By definition, if we assign \(\overline{Y}_{j}(\overline{X})=\sum_{r}\overline{X}_{r_{j}}\geq N_{\mathcal{R }}^{*}(j)\) transporters to a job \(j\), then the job \(j\) is saturated and its completion time is \(\mathrm{C}^{\mathrm{sat}}(j)\). Otherwise, every period takes duration \(\delta(j)+\kappa\) while the effective completion time is only \(\overline{Y}_{j}\cdot\kappa\), and the job \(j\) is idle for the remaining \(\delta(j)+\kappa-\overline{Y}_{j}\cdot\kappa\) time units per period. Then, the job completion time is:  
\[C(j,\overline{X})= \begin{cases}C^{\text{sat}}(j)\cdot\big{(}\delta(j)+\kappa \big{)}\,/\,\big{(}\kappa\cdot\overline{Y}_{j}(\overline{X})\big{)}&\text{if } \overline{Y}_{j}<N_{\mathcal{R}}^{*}(j),\\ C^{\text{sat}}(j)&\text{if }\overline{Y}_{j}\geq N_{\mathcal{R}}^{*}(j).\end{cases}  \tag{5}\]  
In what follows, we show that for a homogeneous instance of (TAP), the full frontier of Pareto optimal solutions can be computed in \(\mathcal{O}\big{(}(N_{R}+N_{J})\cdot\log[N_{J}]\big{)}\) time. Consider algorithm (Hom), which computes the Pareto frontier in the following steps:  
1. The first Pareto solution is achieved by assigning one transporter to every job;
2. Add one more transporter to any job with maximum completion time according to Equation (5);
3. If step 2 decreased the makespan, then the new solution is a Pareto solution;
4. If any job with maximum completion time is saturated, or if all transporters are used, stop; otherwise, return to step 2. The following theorem shows that algorithm (Hom) computes the frontier of Pareto optimal solutions in full. Theorem 2.2: _If every transporter has the same filling time, Algorithm (Hom) computes a Pareto solution to (TAP) at every step in which the makespan decreases. Moreover, each Pareto solution is found by algorithm (Hom)._  
Proof: We prove, equivalently, that at the \(k\)-th step (including the step where the first solution is computed), Algorithm (Hom) computes a solution of minimum makespan amongst all solutions in which exactly \(N_{J}+k-1\) transporters are used. That means that if the makespan decreases in the \(k\)-th step, the achieved solution is Pareto optimal, since any fewer number of used transporters can only achieve a strictly larger makespan. In addition, since all possible numbers of used transporters are tested once, no Pareto optimal solution is missed. It remains to be shown that indeed, the solution computed in the \(k\)-th step has a minimum makespan amongst all solutions in which exactly \(N_{J}+k-1\) transporters are used. Suppose that at the \(k\)-th step, the assignment is not minimizing the makespan over every solution using \(k\) transporters. Let \((\overline{Y}_{j_{1}},\ldots\overline{Y}_{j_{N_{J}}})\) be the number of transporters assigned to the jobs at this step. Consider an optimal assignment of \(k\) transporters \((\overline{Y}_{j_{1}}^{*},\ldots\overline{Y}_{j_{N_{J}}}^{*})\) minimizing the makespan. Pick the first iteration where the algorithm assigns a transporter to a job \(j_{i}\) such that the number \(\overline{Y}_{j_{i}}^{*}\) of the optimal solution is being exceeded. By definition, the completion time of the optimal solution is greater or equal to the completion time of \(j_{i}\) when using \(\overline{Y}_{j_{i}}^{*}\) transporters.