# Allocating Small Transporters to Large Jobs
## 7 Experiments
### Performance of the General Algorithms  
We now evaluate the Pareto frontier generated by the following algorithms:  
* The three greedy algorithms \((\mathrm{GJ})\), \((\mathrm{GR}i)\), and \((\mathrm{GR}c)\) generalizing their saturated counterparts \((\mathrm{SGJ})\), \((\mathrm{SG}Ri)\), and \((\mathrm{SG}Rc)\).
* The binary search algorithm \((\mathrm{BS.MIP}g)\) solving an aggregated version of \((\rho\mathrm{MIP})\) by grouping transporters with equal filling time.
* The binary search heuristics \((\mathrm{BS.GJ})\) and \((\mathrm{BS.GR}i)\), which are iteratively called respectively \((\mathrm{SGJ})\) and \((\mathrm{SG}Ri)\) to solve the saturated mixed integer program \((r\mathrm{MIP})\) with altered job return times.  
Figure 8 shows the computed Pareto frontiers for our first simulation scenario, using \(four\) jobs and 20 transporters. Contrary to the saturated case, Algorithm \((\mathrm{GJ})\) performs poorly for limited transporter fleets, as it over-invests transporters for the first jobs while letting future jobs have a single transporter. Since the last job typically gets assigned the smallest transporter in the fleet, adding an even smaller transporter to the fleet will further increase its completion time, hence potentially increasing the makespan of the assignment. In other words, Algorithm \((\mathrm{GJ})\) may generate a worse, dominated solution while using a bigger transporter fleet. In order to create a non-increasing Pareto frontier, we set the makespan with \(N\) available transporters as the minimum makespan over every instance using at most \(N\) transporters.  
Algorithm \((\mathrm{GR}i)\) is less efficient than Algorithm \((\mathrm{GR}c)\) for a similar reason: since we want to minimize the maximum job completion time, we should assign more transporters to jobs with the highest residual completion time instead of the job with the highest residual idle time.  
However, the binary search-based heuristics generally perform very well when compared to the nearly optimal algorithm \((\mathrm{BS.MIP}g)\), with the exception of \((\mathrm{BS.GJ})\) when using less than 10 transporters. This shows that virtually increasing the return times of the small jobs (with short saturated processing time) is a good way to balance the transporter fleet between the jobs and ensure a short makespan. Note that the Pareto frontiers generated by the binary search heuristics only start at eight transporters, because each job needs at least two transporters to be saturated.  
Figure 7: Distribution of assigned transporters (using the same boxplot settings as in Figure 5). Whenever an instance is infeasible, this number is set to the total number of transporters.  
Finally, Table 2 shows that the binary search-based heuristics are extremely fast, despite being 10 to 100 times slower than their greedy counterpart.  
We conclude that to solve an instance of the transporter assignment problem, an efficient method consists of iteratively increasing the return time of the jobs until the problem has a saturated solution. Then, the computed saturated solution is a good solution to the initial assignment problem. An advantage of this method is that the saturated problem instances do not have to be solved to optimality, and most decent algorithms should induce a good solution to the transporter assignment problem.