# Allocating Small Transporters to Large Jobs
## Abbreviations
Consider next the schedule in which transporters in \(R\) are used in a cyclic fashion, in order of their numbering, that is, they use each transporter once, in order of the transporter numbering, then restart with transporter \(r_{1}\) and continue, again in order of the transporter numbering and so on, until job \(j\) is fully finished. Denote this schedule by \(S^{\mathrm{cyc}}\) and its completion time by \(C^{\mathrm{cyc}}\). **Lemma A2**. :
1. _In schedule_ \(S^{\mathrm{cyc}}\)_, the time between the starts of two uses of transporter_ \(r_{1}\) _is exactly_ \(L(j)\)_._
2. _In schedule_ \(S^{\mathrm{cyc}}\)_, between any two uses of transporter_ \(r_{1}\)_, job_ \(j\) _is idle for exactly_ \(I(j)\) _time. Furthermore, all idle time, if any, appears immediately before the second use of_ \(r_{1}\)_._
3. _It holds that_  
\[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.\]  
Proof. : **Proof of 1:** By Lemma A1, if \(L(j)=\sum_{r\in R}\kappa(r)\), then job \(j\) is saturated and clearly the time between the starts of two uses of a transporter \(r\) is given as the sum of filling times of all transporters, which is exactly \(L(j)\). On the other hand, \(\delta(j)+\kappa(r)\) is a lower bound for the time between the starts of two uses of any transporter, since between two starts, the transporter needs to finish its processing and then its whole return time. Since from \(L(j)=\delta(j)+\kappa(r_{1})\), it follows that \(\delta(j)\geq\sum_{i=2}^{k}\kappa(r_{i})\), this means by the time \(r_{1}\) returns, no other transporter is processing job \(j\) so it can start immediately, leading again to a time of \(L(j)\) between any two starts of uses of \(r_{1}\). **Proof of 2:** Since, by definition, \(I(j)=0\) if and only if \(L(j)=\sum_{r\in R}\kappa(r)\) and by Lemma A1 this means job \(j\) is saturated, in that case, the statement holds. Suppose \(I(j)>0\) and \(L(j)=\delta(j)+\kappa(r_{1})>\sum_{r\in R}\kappa(r)\). In that case, since during time \(L(j)\), each transporterprocesses job \(j\) exactly once, by construction of schedule \(S^{\text{cyc}}\), the total time spent idle is given as  
\[\delta(j)+\kappa(r_{1})-\sum_{r\in\mathcal{R}}\kappa(r)=I(j),\]  
by definition. Finally, note that due to the ordering of jobs in \(S^{\text{cyc}}\), the time between the start of a use of any transporter \(r\) and the next time \(r\) is needed is given by \(L(j)\geq\delta(j)+\kappa(r)\), so any transporter other than \(r_{1}\) always arrives back at site before it is needed again. Therefore, any idle time can only happen before a use of transporter \(r_{1}\). **Proof of 3:** During any time \(L(j)\), exactly \(L(j)-I(j)\) time is spent processing in schedule \(S^{\text{cyc}}\), by Statement 1 and 2 of this Lemma. Thus, after \(\left(\left\lceil\frac{C^{\text{sat}}(j)}{L(j)-I(j)}\right\rceil-1\right)L(j)\) time,  
\[\left(\left\lceil\frac{C^{\text{sat}}(j)}{L(j)-I(j)}\right\rceil-1\right)(L(j )-I(j))\]  
of job \(j\) has been processed. It remains an amount of either exactly \(L(j)-I(j)\) if \(L(j)-I(j)\) divides \(C^{\text{sat}}(j)\) or \(\left(C^{\text{sat}}(j)\bmod(L(j)-I(j))\right)<L(j)-I(j)=\sum_{r\in\mathcal{R }}\kappa(r)\), otherwise, which combined yields a remaining amount of  
\[\left(\left(C^{\text{sat}}(j)-1\right)\bmod(L(j)-I(j))\right)+1.\]  
Finally, note that the remaining amount can be processed immediately and without interruption, since after time \(\left(\left\lceil\frac{C^{\text{sat}}(j)}{L(j)-I(j)}\right\rceil-1\right)L(j)\), transporter \(r_{1}\) is ready to process, and by the second statement of this lemma, no further idle time happens before all the remaining amount is processed. Obviously, it holds that \(C^{\text{min}}(j)\leq C^{\text{cyc}}\).