# Allocating Small Transporters to Large Jobs
## 1 Introduction
### Formal Problem Definition  
For the purpose of this study, we assume that each operation site is assigned exactly one main resource. Otherwise, we split an operation site into multiple neighboring sites, one for each resource assigned. Furthermore, we assume that the processing speed of the main resources is fixed. This is reasonable for tactical planning if the tasks conducted at each site as well as the resources used to do so are similar. Formally, a set of jobs \(\mathcal{J}=\{j_{1},\ldots,j_{N_{j}}\}\) is given, each representing one operation site together with a main resource. Furthermore, let \(\mathcal{R}=\{r_{1},\ldots,r_{N_{R}}\}\) be the set of transporters. In normal scheduling terminology, the transporters would be called resources or machines; however, we stay with the term transporters throughout this paper in order to stay closer to the terminology in our field of application. Each job has a certain volume that needs to be processed before the job is complete, and each transporter has a certain capacity that can be used up before the transporter has to rest (travel to the central hub). Since we assume the processing speed of the main resources to be fixed, we can translate all volumes into time values for ease of notation. Thus, each job \(j\in\mathcal{J}\) has a _saturated processing time_\(C^{\mathrm{sat}}(j)>0\), which is the total time it needs to be processed by transporters before it is complete. Similarly, each transporter \(r\in\mathcal{R}\) has a _filling time_\(\kappa(r)>0\), which is the time it can process a job before it needs to rest. Finally, we denote by \(\delta(j)>0\) the return time of every transporter assigned to job \(j\). In this paper, we do not allow a transporter to be assigned to multiple jobs. Figure 2 shows how two transporters may process the same job. Figure 1: Example of three fields being harvested by forage harvesters and eight transporters of heterogeneous sizes. Field 1 is assigned an extra transporter due to its large size, making the avoidance of idle times even more important. Field 3 is assigned an extra transporter because it is far away from its silage pit, causing assigned transporters to waste a lot of time on the road. We assume all jobs start processing at the same time. The completion time \(C(j)\) of a job \(j\in\mathcal{J}\) is given as the sum of \(C^{\text{sat}}(j)\) and all idle times happening during the processing of job \(j\) due to no transporter being available. In particular, \(C^{\text{sat}}(j)\) is the completion time of job \(j\) if job \(j\) is never idle (always has a transporter available for processing). Our goal is to minimize the maximum completion time of any job, which is also called the makespan \(C^{*}=\max_{j\in\mathcal{J}}C(j)\). A short makespan is desirable, because it ties in directly with several crucial performance indicators, such as the necessary opening times of the hub, potential overtime pay for workers, as well as minimizing the time frame in which problems (e.g., due to weather) may happen. In addition, a large makespan may indicate unnecessary idle times for the main resources, which are to be avoided in order to operate cost efficiently. However, it may not be possible to hire enough transporters to avoid all idle times (due to transporter availability), or, if it is possible, it may still not be economically desirable (due to drivers' wages) in cases where an additional transporter would only decrease the idle time by a marginal value. Thus, the total number of assigned transporters is another important measure for the quality of a solution. Therefore, our goal in this paper is to jointly minimize the makespan of multiple simultaneously operated sites and minimize the number of used transporters. The problem of assigning transporters to jobs in order to minimize simultaneously the makespan and the number of assigned transporters is called the _transportor allocation problem_ or \((\operatorname{TAP})\) for short.