# Allocating Small Transporters to Large Jobs
## Abbreviations
Furthermore, note that  
\[C^{\text{cyc}}-C(j)\] \[= \left(\left\lceil\frac{C^{\text{sat}}(j)}{L(j)-I(j)}\right\rceil -1\right)L(j)+\left(\left(C^{\text{sat}}(j)-1\right)\bmod(L(j)-I(j))\right)+1\] \[-C^{\text{sat}}(j)\frac{L(j)}{L(j)-I(j)}\] \[= \left(\left(C^{\text{sat}}(j)-1\right)\bmod(L(j)-I(j))\right)+1\] \[L(j)=\sum_{r\in R}\kappa(r),\]0 \[L(j)=\sum_{r\in R}\kappa(r),\]1  
where the last inequality is due to \(L(j)>I(j)\geq 0\). Therefore, it is proven that \(C^{\min}(j)-C(j)\leq 0\leq 2\delta(j)\). We are left to prove that \(C(j)-C^{\min}(j)\leq 2\delta(j)\). First, we show the following lemma, extending the statement of Lemma A2 (2). Lemma A3: _In any schedule using transporters in \(R\) to process job \(j\), between two uses of transporter \(r_{1}\), idle time of at least \(I(j)\) happens._  
Proof: If \(I(j)=0\), there is nothing to prove. So assume \(I(j)>0\) and \(L(j)=\delta(j)+\kappa(r_{1})>\sum_{r\in R}\kappa(r)\). In the proof of Lemma A2, it was shown that if every other transporter is used exactly once between two uses of \(r_{1}\), then between the two uses of \(r_{1}\), the idle time of exactly \(I(j)\) is reached. Using fewer transporters in between does obviously not reduce idle time. On the other hand, using any other transporter \(r^{*}\) twice without using \(r_{1}\) in between leads to an idle time between the two uses of \(r^{*}\) of at least  
\[L(j)=\sum_{r\in R}\kappa(r),\]2 (A1)which means the idle time between the two uses of \(r_{1}\) would also be larger, which finishes the proof. Using Lemma A3 and Equation (A1), we can prove the following lemma. For any schedule using transporters in \(R\) to process job \(j\), let transporter \(r^{*}\) be a transporter with the most uses and let \(r^{*}\) be used exactly \(\ell\) times. Then, job \(j\) is idle for at least  
\[L(j)=\sum_{r\in R}\kappa(r),\]3  
time. Proof. : If \(r_{1}\) is used \(\ell\) times, by Lemma A3, job \(j\) is idle for at least \((\ell-1)I(j)\), and the statement is proven. So, assume transporter \(r_{1}\) is used \(\ell_{1}<\ell\) times. By Lemma A3, between any two uses of transporter \(r_{1}\), idle time of at least \(I(j)\) appears. However, by Equation (A1), between any two uses of job \(r^{*}\) where \(r_{1}\) is not used in between, idle time of at least  
\[L(j)=\sum_{r\in R}\kappa(r),\]4  
appears. Thus, the total idle time of job \(j\) is at least  
\[L(j)=\sum_{r\in R}\kappa(r),\]5  
time units long. Note that using schedule \(S^{\text{cyc}}\), each transporter can be used \(\ell\) times, causing idle time of at most \((\ell-1)I(j)\). Thus, by Lemma A4, we have  
\[L(j)=\sum_{r\in R}\kappa(r),\]6 (A2)  
Furthermore,  
\[L(j)=\sum_{r\in R}\kappa(r),\]7 \[L(j)=\sum_{r\in R}\kappa(r),\]8 \[L(j)=\sum_{r\in R}\kappa(r),\]9 \[C^{\mathrm{cyc}}=\left(\left\lceil\frac{C^{\mathrm{sat}}(j)}{L(j)-I(j)} \right\rceil-1\right)L(j)+\left(\left(C^{\mathrm{sat}}(j)-1\right)\mathrm{mod }\left(L(j)-I(j)\right)\right)+1.\]0 \[C^{\mathrm{cyc}}=\left(\left\lceil\frac{C^{\mathrm{sat}}(j)}{L(j)-I(j)} \right\rceil-1\right)L(j)+\left(\left(C^{\mathrm{sat}}(j)-1\right)\mathrm{mod }\left(L(j)-I(j)\right)\right)+1.\]1  
Therefore, and due to Equation A2, we have \(C(j)-C^{\text{min}}(j)\leq 2\delta(j)\), which finishes the proof of Theorem A1. Note that in the case where the transporters in \(R\) saturate job \(j\) and \(I(j)=0\), then the above and Equation A2 even imply that \(C(j)=C^{\text{min}}(j)\). In addition, note that we actually showed that \(C(j)-C^{\text{min}}(j)\leq 2I(j)\leq 2\delta(j)\), and thus the worst case estimate as given in Theorem A1 can only happen when only a single transporter is assigned to a job (which is the only time when \(I(j)=\delta(j)\)).