# Allocating Small Transporters to Large Jobs
## 2 Literature Review
### Divisible Load Scheduling  
In divisible load scheduling [15], a processing load needs to be divided onto several processors, just like the total volume of a job in \((\mathrm{TAP})\) needs to be divided onto several transporters. The main difference between the two is that in divisible load scheduling, the processors are assumed to be parallel, such that they are allowed to process different parts of the main load at the same time. In addition, usually, in divisible load scheduling problems, only a single load needs to be split across processors, while for \((\mathrm{TAP})\), multiple loads need to be assigned to transporters. Note that without any further assumptions, splitting a load over parallel processors is usually easy. Therefore, the literature considers many additional parameters, such as setup times, communication delays between processors, and more complex processor networks (e.g., where sub-processors on the first level have again several second-level sub-processors to which they can divide their sub-task). We refer to [16] for a review. In comparison, as we show in this paper, \((\mathrm{TAP})\) is much harder, even without any additional assumptions.  
Interestingly, many papers consider bi-criteria versions of divisible load scheduling, where the goal is to minimize the makespan and cost of a schedule simultaneously; see [17; 18; 19]. Here, cost is usually defined as a function of the load assigned to each processor, together with a fixed cost to activate each used processor in the first place [19].  
\begin{table}
\begin{tabular}{c c c c} \hline \hline
**Version** & **Whole Pareto Front** & **Single Pareto Point** & **Reference** \\ \hline General & str. NP-hard & str. NP-hard & Section 3 \\ \hline \(\delta(j)=\delta^{*}\) & str. NP-hard & str. NP-hard & Section 3 \\ \hline \(\kappa(r)=\kappa^{*}\) & \(\mathcal{O}\big{(}(N_{R}+N_{J})\log[N_{J}]\big{)}\) & \(\mathcal{O}\big{(}N_{J}\cdot\log[\max_{j}\{C(j,1)\}]\big{)}\) & Section 4 \\ \hline \hline \end{tabular}
\end{table}
Table 1: Overview of complexity results for problem \((\mathrm{TAP})\). Note that \(\delta(j)=\delta^{*}\) denotes the case where all return times are identical and \(\kappa(r)=\kappa^{*}\) denotes the case where all transporter capacities are identical. Finally, \(C(j,1)\) denotes the completion time of job \(j\) when exactly one transporter is assigned to it, in the case where all transporters have identical capacity.  
Special versions have been studied without any additional restrictions and where only the fixed cost for each processor is used [17; 19]. Note that this version is very close to (TAP) with only three differences: first, of course, for the divisible load scheduling problem, the processors work in parallel, whereas for \((\mathrm{TAP})\), they in sequence; second, in the divisible load scheduling problem, processors may have different speeds but have no maximum load, whereas in \((\mathrm{TAP})\), all transporters have the same speed but a maximum capacity after which they must rest; third, for \((\mathrm{TAP})\), we assume additionally that the fixed cost for each transporter is the same. This special version of divisible load scheduling is shown to be NP-hard in the usual sense [17]. We prove later that \((\mathrm{TAP})\) is NP-hard in the strong sense. Furthermore, note that if in the divisible load scheduling problem the fixed cost of all processors is the same, then the NP-hardness proof from [17] is no longer valid, while this assumption holds by definition for \((\mathrm{TAP})\).  
Most other results for divisible load scheduling are not comparable to \((\mathrm{TAP})\) either due to additional restrictions for the divisible load scheduling problem or because of the difference in sharing load in parallel or sequential. Thus, techniques used to solve divisible load scheduling problems cannot be easily transferred to \((\mathrm{TAP})\).