# Allocating Small Transporters to Large Jobs
## 1 Introduction
### Formal Problem Definition
As the two objectives of \((\operatorname{TAP})\) are conflicting, our goal is to find all _Pareto optimal_ solutions. A feasible solution to \((\operatorname{TAP})\) is Pareto optimal if every other feasible solution with smaller makespan uses a larger number of transporters, and every other feasible solution that uses a smaller number of transporters has a larger makespan. The set of all Pareto optimal solutions is called the _Pareto frontier_. We refer to [13] for a general introduction to multicriteria optimization. In the Appendix A, we prove that given a set \(R\subset\mathcal{R}\) of transporters assigned to some job \(j\in\mathcal{J}\), the completion time of \(j\) can be estimated by  
\[C(j)=C^{\text{sat}}(j)\frac{L(j)}{L(j)-I(j)}, \tag{1}\]  
where  
\[L(j):=\max\Big{\{}\sum_{r\in R}\kappa(r),\;\delta(j)+\max_{r\in R}\kappa(r) \Big{\}}, \tag{2}\]  
and  
\[I(j):=L(j)-\sum_{r\in R}\kappa(r). \tag{3}\]  
The estimate depends on the practical assumption, mentioned above, that jobs are very large compared to transporter capacities and return times. See Theorem A.1 for details. We also call \(L(j)\) the _period length_ and \(I(j)\) the _idle time per period_ of job \(j\), according to the statements of Lemma A.2 in the Appendix A. For the remainder of this paper, we do not deal  
Figure 2: Example of two transporters relaying each other to process a job. The job processing stops while both transporters are in their return time. with the exact scheduling and sequencing of transporters when processing jobs and instead only focus on the assignment of transporters to jobs using Equation (1) to estimate the completion times of the jobs. Therefore, a solution to \((\mathrm{TAP})\) is fully given by an assignment of transporters to jobs, which are encoded by variables \(\overline{X}=(\overline{X}_{r,j})\) in the following way:  
\[\overline{X}_{r,j}=\left\{ \begin{array}{ll}1&\text{if transporter $r$ is assigned to job $j$}\\ 0&\text{otherwise.}\end{array} \right.\]  
For a solution \(\overline{X}\), we denote by \(\overline{Y}_{j}(\overline{X})\) the number of transporters assigned to \(j\) under assignment \(\overline{X}\):  
\[\overline{Y}_{j}(\overline{X})=\sum_{r\in\overline{R}}\overline{X}_{r,j}.\]  
In addition, by \(\overline{Y}(\overline{X})\), we denote the total number of transporters assigned by assignment \(\overline{X}\), i.e.,  
\[\overline{Y}(\overline{X})=\sum_{j\in\mathcal{J}}\overline{Y}_{j}(\overline{ X}).\]  
Furthermore, we denote by \(C^{*}(\overline{X}),C(j,\overline{X}),L(j,\overline{X})\), and \(I(j,\overline{X})\) the makespan, completion time of job \(j\in\mathcal{J}\), its period length, and its idle time per period, under solution \(\overline{X}\), respectively. If there is no confusion about the solution referred, we may instead leave out \(\overline{X}\) as before. Note that all mathematical notation introduced in this section and throughout the remainder of the paper is also given again in a concise list in the Abbreviations section at the end of this paper. Finally, a solution \(\overline{X}\)_saturates_ a job \(j\in\mathcal{J}\) if job \(j\) has no idle time under solution \(\overline{X}\), that is if \(L(j,\overline{X})=\sum_{r\in\overline{R}}\overline{X}_{ij,k}(r_{i})\) and \(I(j,\overline{X})=0\). If solution \(\overline{X}\) saturates all jobs \(j\in\mathcal{J}\), then \(\overline{X}\) is called _saturating_. Recall that in this case, the completion time of every job \(j\) is at its minimum value \(C^{\text{sat}}(j)\). Note that a saturating solution minimizes both the maximum and total completion time of all jobs. An instance of problem \((\mathrm{TAP})\) is _saturated_ if there exists at least one saturating assignment. The remainder of this paper is structured as follows. To finish Section 1 below, we briefly summarize our results and contributions. Then, in Section 2, we present a review of the literature related to our problem. In Section 3, we state and prove some structural properties of \((\mathrm{TAP})\), in particular that \((\mathrm{TAP})\) is NP-hard.