# Allocating Small Transporters to Large Jobs
## 6 The General Transporter Allocation Problem
### Computing the Pareto Frontier Exactly
#### 6.1.1 A Mixed Integer Quadratic Program  
We denote by \(\mathbb{R}^{+}\) the set of real positive numbers, including 0. The following mixed integer non-linear program computes a solution to \((\mathrm{TAP})\) minimizing the makespan, using the return time \(\delta(j)\), the saturated job processing time \(\mathrm{C}^{\mathrm{sat}}(j)\), the period length \(\overline{L}_{j}\), and the idle time per period \(\overline{I}_{j}\). Note that \(\overline{L}\) and \(\overline{I}\) in this case are used as variables, instead of the predefined values \(L(j,\overline{X})\) and \(I(j,\overline{X})\), as introduced in Section 1.  
\[(\mathrm{Q}\mathrm{TAP}):\] \[\min_{\overline{X},\mathrm{C}^{*},\overline{I},I}C^{*} \tag{17}\] \[\mathrm{s.t.}\sum_{j\in\mathcal{J}}\overline{X}_{r,j}\leq 1, \forall r\in\mathcal{R}\] (18) \[\sum_{r\in\mathcal{R}}\overline{X}_{r,j}\geq 1, \forall j\in\mathcal{J}\] (19) \[C^{*}\geq\mathrm{C}^{\mathrm{sat}}(j)\cdot\frac{\overline{L}_{j }}{\overline{L}_{j}-\overline{I}_{j}} \forall j\in j\] (20) \[\overline{L}_{j}=\overline{I}_{j}+\sum_{r\in\mathcal{R}}\overline {X}_{r,j}\cdot\kappa(r) \forall j\in\mathcal{J}\] (21) \[\overline{L}_{j}\geq\overline{X}_{r,j}\cdot\kappa(r)+\delta(j) \forall j\in\mathcal{J},\forall r\in\mathcal{R}\] (22) \[\overline{X}_{r,j}\in\{0,1\}, \forall j\in\mathcal{J},\forall r\in\mathcal{R}\] (23) \[\overline{L}_{j},\overline{I}_{j}\in\mathbb{R}^{+}, \forall j\in\mathcal{J} \tag{24}\]  
Note that because of the terms \(\frac{\overline{T}_{j}}{\overline{L}_{j}-\overline{I}_{j}}\) in Equation (20), the above program is indeed not linear. Namely, we get a quadratic program by multiplying both sides of the equation by \(\overline{L}_{j}-\overline{I}_{j}\). In the next subsection, we will propose an alternative algorithm to solve \((\mathrm{TAP})\) with the means of a slightly modified linear formulation.  
Equation (19) ensures that \(\overline{L}_{j}-\overline{I}_{j}>0\) (i.e., the idle time is finite); hence, Equation (20) does not induce a division by zero. Equation (20) computes the job completion time.  
Equations (21) and (22) model the period length along with the idle time per period. For a given assignment \(\overline{X}\), the value of \(\overline{L}_{j}-\overline{I}_{j}\) is fixed by Equation (21). Since we minimize the makespan, the program will tend to minimize \(\overline{L}_{j}\) by Equation (20) while keeping it above \(\delta(j)+\max\left\{\kappa(r):\overline{X}_{r,j}=1\right\}\) by Equation (22). However, in this mathematical program, \(\overline{L}_{j}\) and \(\overline{I}_{j}\) do not exactly model the period length and idle time per period, as defined in Equations (2) and (3). Indeed, a solution to \((\mathrm{Q}\mathrm{TAP})\) may contain additional, unnecessary ide times for some jobs, and thus, the period length of those jobs may be artificially increased as long as the resulting completion time stays shorter than the completion time of the longest job. This problem could be fixed, though, by minimizing, for example, the average completion time as an additional objective.