# Allocating Small Transporters to Large Jobs
## 5 The Saturated Transporter Allocation Problem
### Greedy Algorithms
#### 5.3.1 Greedy Algorithm by Job  
Our first greedy algorithm \((\mathrm{SGJ})\) iterates through the jobs in order of non-increasing return times. It assigns exactly as many transporters as needed to one job at a time so that the job is saturated. If at any time during the algorithm the current job cannot be saturated, the algorithm fails.  
We assume that transporters are indexed in order of non-increasing filling times. We start with transporter set \(\mathcal{R}^{\prime}:=\mathcal{R}\). We iteratively assign to a job a saturating transporter set with respect to the current set \(\mathcal{R}^{\prime}\) and update \(\mathcal{R}^{\prime}\) thereafter by deleting the assigned transporters. Since the ideal transporter sets of different jobs may overlap, it cannot be guaranteed that every job \(j\) will be assigned to \(N_{\mathcal{R}}^{*}(j)\) transporters.  
At any iteration, for a current job \(j\), we first compute the minimum number of transporters \(N_{\mathcal{R}^{\prime}}^{*}(j)\) needed to saturate \(j\) using the current remaining set of transporters \(\mathcal{R}^{\prime}\). Recall that by Theorem 3.2, this can be done efficiently. Then, we enumerate all subsets of \(\mathcal{R}^{\prime}\) of size \(N_{\mathcal{R}^{\prime}}^{*}(j)\) and assign one to \(j\) such that \(j\) is saturated. If there are multiple subsets of \(\mathcal{R}^{\prime}\) of size \(N_{\mathcal{R}^{\prime}}^{*}(j)\) which saturate \(j\), then as a tie breaker, we choose the set that uses the smallest maximum indexed transporter, which is not used by all other sets. If there is still a tie, we repeat the above rule with only the still tied sets until only one candidate set is left.  
For example, suppose that the current transporter set is \(\mathcal{R}^{\prime}=\{r_{1},r_{2},r_{3},r_{4},r_{5}\}\), and that our current job is \(j\) with \(N_{\mathcal{R}^{\prime}}^{*}(j)=3\). Suppose there are four subsets of \(\mathcal{R}^{\prime}\) of size 3 that saturate job \(j\), namely \(\{r_{1},r_{2},r_{3}\}\), \(\{r_{1},r_{2},r_{4}\}\), \(\{r_{1},r_{2},r_{5}\}\), and \(\{r_{1},r_{3},r_{4}\}\). Recall that transporters are numbered in order of non-increasing filling times. All sets use transporter \(r_{1}\). After removing \(r1\), the transporter with maximum filling time in the first three candidatesis \(r_{2}\), while the transporter with maximum filling time in the fourth candidate is \(r_{3}\). We pick the fourth candidate, since \(r_{3}\) has a smaller or equal filling time compared to \(r_{2}\).  
If in the above example, \(\{r_{1},r_{3},r_{5}\}\) would have been a candidate as well, then in a second round of tie breaking, our algorithm would only consider sets \(\{r_{1},r_{3},r_{4}\}\) and \(\{r_{1},r_{3},r_{5}\}\). After removing common transporters, only \(r_{4}\) remains in the first set, while only \(r_{5}\) remains in the second, leading to us choosing the later set \(\{r_{1},r_{3},r_{5}\}\).  
Note that the runtime of algorithm \((\mathrm{SGJ})\) is exponential in the number of transporters, since we enumerate over a set of subsets of the transporter set. However, since all subsets have the same cardinality and this cardinality is usually relatively small, in practice, \((\mathrm{SGJ})\) still has a reasonable runtime, as is shown in the computational experiments in Section 7.