# Allocating Small Transporters to Large Jobs
## Abbreviations  
The following abbreviations are used in this manuscript:  
\[\begin{array}{ll}(\mathrm{TAP})&\mathrm{Transporter\ Assignment\ Problem}\\ (\mathrm{TAP}_{C^{*}}(n_{r}))&\mathrm{Decision\ version\ of\ the\ Transporter\ Assignment\ Problem}\\ (\mathrm{STAP})&\mathrm{Saturated\ Transporter\ Assignment\ Problem}\\ \mathcal{O}&\mathrm{Complexity\ order\ of\ the\ algorithm}\\ (\mathrm{Hom})&\mathrm{Our\ algorithm\ for\ (\mathrm{TAP})\ with\ homogeneous\ transporters}\\ (\mathrm{sGR}i)&\mathrm{Heuristic\ for\ (\mathrm{(STAP)}\), greedily assigning a transporter to the job with maximum\ idle time per period}\\ (\mathrm{sGR}e)&\mathrm{Heuristic\ for\ (\mathrm{(STAP)}\), greedily assigning a transporter to the job with maximum\ makespan}\\ (\mathrm{sGJ})&\mathrm{Heuristic\ for\ (\mathrm{(STAP)}\), greedily generating an saturating assignment to each job\((\mathrm{GR}i)\)\(\mathrm{Extension\ of\ }(\mathrm{sGR}i)\) to compute a Pareto frontier for \(\mathrm{(TAP)}\)\(\mathrm{Extension\ of\ }(\mathrm{sGR}e)\) to compute a Pareto frontier for \(\mathrm{(TAP)}\)\(\mathrm{Extension\ of\ }(\mathrm{sGJ})\) to compute a Pareto frontier for \(\mathrm{(TAP)}\)\(\mathrm{MIP}\)\(\mathrm{Mixed\ Integer\ Program}\\ (\mathrm{sMIP})&\mathrm{MIP\ formulation\ of\ (\mathrm{(STAP)}\)}\\ (\mathrm{sMIP}g)&\mathrm{MIP\ formulation\ of\ (\mathrm{(STAP)}\) aggregating transporters by model\((\rho\mathrm{MIP})\)\(\mathrm{MIP}\)\(\mathrm{Mixed\ job\ idle\ rates\ }l_{j}\)\((r\mathrm{MIP})\)\(\mathrm{MIP}\)\(\mathrm{Mixed\ job\ idle\ rates\ }\)\(\mathrm{and\ altered\ job\ return\ times}\\ (\mathrm{BS})&\mathrm{Algorithm\ framework\ to\ compute\ a\ solution\ (\mathrm{(TAP)}\) with minimum makespan}\\ (\mathrm{BS}.\mathrm{MIP}g)&\mathrm{Exact\ algorithm\ for\ (\mathrm{(TAP)}\), using framework\ (\mathrm{(BS)}\) and an \(\mathrm{MIP\ solver\ for\ (\rho\mathrm{MIP})\)\(\mathrm{Heuristic\ for\ }\mathrm{(TAP)}\), using framework\(\ \mathrm{(BS)}\) and \((\mathrm{sGR}i)\) to generate a solution\(\mathrm{for\ }(r\mathrm{MIP})\)\(\mathrm{Heuristic\ for\ }\mathrm{(TAP)}\)\(\mathrm{Mixed\ job\ idle\ rates\ }l_{j}\)\(\mathcal{J}\)\(\mathrm{Set\ of\ jobs}\)\(\mathcal{R}\)\(\mathrm{Set\ of\ transporters}\)\(\mathcal{M}\)\(\mathrm  
**Theorem A1**.: _Given a set \(R\subset\mathcal{R}\) of transporters assigned to some job \(j\in\mathcal{J}\), it holds that_  
\[\left|C^{\min}(j)-C^{\mathrm{sat}}(j)\frac{L(j)}{L(j)-I(j)}\right|\leq 2\delta(j)\]  
_where \(C^{\min}(j)\) is the minimum completion time reachable when processing job \(j\) with the set of transporters \(R\), and \(L(j)\) and \(I(j)\) are given by Equations (2) and (3), respectively._  
Since in our practical applications, usually \(C^{\mathrm{sat}}(j)\) and therefore also \(C(j)\) is much larger than the return time \(\delta(j)\), Theorem A1 implies that the error incurred by using Equation (1) to estimate the completion times of jobs is negligible. For the remainder of this appendix, we use notations \(R\), \(j\), \(C^{\min}(j)\), \(L_{j}\), and \(I(j)\) as defined in Theorem A1. Furthermore, we continue to denote by \(C(j)\) the estimated completion time of job \(j\) as given by Equation (1). Finally, let the resources in \(R\) be given as \(r_{1},r_{2},\ldots,r_{k}\), as numbered by the non-increasing order of filling times. We first proof the following Lemma. **Lemma A1**. : _If_  
\[L(j)=\sum_{r\in R}\kappa(r),\]  
_then, the transporters in \(R\) saturate job \(j\), i.e., \(C^{\min}(j)=C^{\mathrm{sat}}(j)\)._  
Proof. : Note that if \(L(j)=\sum_{r\in R}\kappa(r)\), then \(\sum_{r\in R}\kappa(r)\geq\delta(j)+\kappa(r_{1})\), by definition of \(L(j)\). In particular, for any subset \(R^{\prime}\subset R\) with exactly \(k-1\) elements, it holds that \(\sum_{r\in R^{\prime}}\kappa(r)\geq\delta(j)\). This means that using the transporters in \(R\) in a cyclic fashion, a transporter always returns before all other transporters finish their processing of job \(j\). Thus, job \(j\) can be processed without idle times and the transporters in \(R\) saturate job \(j\).