# Allocating Small Transporters to Large Jobs
## 8 Conclusions  
The objective of the transporter allocation problem is to assign transporters to jobs to jointly minimize the makespan of the jobs and the number of assigned transporters. Crucially, transporters have a limited capacity, and usually, multiple transporters are assigned to a single job. After processing a share of the job load, a transporter must wait for a given time before it can process the job again. In particular, the goal is to compute the frontier of Pareto optimal solutions. To the best of our knowledge, this is the first study on the assignment of an heterogeneous transporter fleet where transporters are regarded as a dynamic resource impacting the completion times and not as a fixed requirement. We show that in general, it is NP-hard in the strong sense to compute even a single point on the Pareto frontier. In particular, it is NP-complete to decide whether a solution exists where every job has the same minimum completion time. Furthermore, the problem remains NP-hard in the usual sense, even if there are only two jobs. On the other hand, when every transporter is identical, the whole Pareto frontier can be computed in a runtime polynomial in the number of jobs and transporters. We provide several exact algorithms and heuristics to compute the minimum number of transporters needed such that all jobs are contracted to their minimum completion time. Figure 8: Median Pareto frontier over 100 instances with 95% confidence intervals. Algorithm (BS.MIP\(\diameter\)) computes Pareto optimal solutions, whereas the other algorithms have no optimality guarantee. By design, Algorithms (BS.GJ) and (BS.GR\(i\)) cannot compute any solution using less than eight transporters. \begin{table}
\begin{tabular}{l c c c c c c} \hline \hline
**Algorithm** & (BS.MIP\(\diameter\)) & (GJ) & (GR\(i\)) & (GR\(c\)) & (BS.GJ) & (BS.GR\(i\)) \\ \hline
**Runtimes[s]** & 33 & 0.00075 & 0.00011 & 0.00015 & 0.013 & 0.010 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Average running times to compute the Pareto frontiers over 100 instances, in seconds. Then, we use these results to compute Pareto frontiers for general (\(\mathrm{TAP}\)) instances, both exactly and heuristically. Computational experiments show that our heuristics compute quickly decent approximations of the optimal solution, where the mixed integer program is already slow. The results presented in this paper are part of a wider, practical study, in which we used a multi-level approach to solve applied problems in farming logistics together with an industrial partner. Assigning transporters to jobs was one of several levels of decision making in this regard, and our algorithms (adjusted for some additional practical needs) have proven to be useful also in early applied experiments. In this paper, we assumed that every team of transporters only completes a single job. However, depending on the job sizes, there are also a variety of practical applications, where transporters are grouped into teams to fulfill several jobs per day in a sequence. Removing this limitation in a future study would significantly increase the number of use cases to which our results can be applied. Note that moving from one job to another may induce location-dependent traveling times, which we did not need to take into account in this paper. Even though we expect a single move from one job (or from the hub) to the next job to only have a minor impact on the solution, it will be important to find the best time to switch a transporter from one job to the next. Another challenge would be how to decide which jobs should be served by the same transporter team and which should receive a different team. Such a clustering, if not mandated by practical circumstances such as large travel times between the jobs, would be an additional degree of freedom, which can have a large impact on the optimality of a solution. As a further area of extension, note that in our model, it is implicitly assumed that all teams of transporters are disjointed (since each transporter can only be assigned to one job).