# Allocating Small Transporters to Large Jobs
## 6 The General Transporter Allocation Problem
### Computing the Pareto Frontier Exactly
#### 6.1.2 Solving the Mixed Integer Quadratic Program  
Instead of directly computing the optimal completion time of \(C^{*}\), we iteratively look for a solution with a given completion time. We denote the maximum saturated job processing time by:  
\[C^{\text{sat}}_{\max}:=\max_{j}\{C^{\text{sat}}(j)\}. \tag{25}\]  
The makespan \(C^{*}\) of any solution to \((\text{TAP})\) takes at least this duration:  
\[C^{*}\geq C^{\text{sat}}_{\max}. \tag{26}\]  
We define the _rate of idle time per period_\(\rho(j,C)\) as the rate of idle time to have at every period for job \(j\) so that its completion time is \(C\):  
\[\rho(j,C):=1-\frac{C^{\text{sat}}(j)}{C}<1. \tag{27}\]  
Hence, we fix the idle time per period as:  
\[\bar{I}_{j}=\rho(j,C)\cdot\overline{L}_{j}. \tag{28}\]  
The following mixed integer program \((\rho\text{MIP})\) minimizes the number of assigned transporters under the same constraints as in the above mathematical program after replacing the idle time variables and the job completion time variables:  
\[(\rho\text{MIP}):\] \[\min_{\overline{X}}\sum_{r\in\mathcal{R}}\sum_{j\in\mathcal{J}} \overline{X}_{r,j}\] (29) s.t. \[\sum_{j\in\mathcal{J}}\overline{X}_{r,j}\leq 1, \forall r\in\mathcal{R} \tag{30}\] \[\frac{\sum_{r^{\prime}}\left[\overline{X}_{j,r^{\prime}}\cdot \kappa(r^{\prime})\right]}{1-\rho(j,C)}-\overline{X}_{r,j}\cdot\kappa(r)\geq \delta(j) \forall j\in\mathcal{J},\forall r\in\mathcal{R}\] (31) \[\overline{X}_{r,j}\in\{0,1\}, \forall j\in\mathcal{J},\forall r\in\mathcal{R}. \tag{32}\]  
Since \(\rho(j,C)<1\), it follows that \(\bar{I}_{j}<\overline{L}_{j}\) and hence Equation (19) is not needed anymore. Equation (31) is the combination of Equations (21) and (22) from the previous mathematical program along with the idle time per period formula of Equation (28). Note that it differs from the saturation condition of Equation (8) only by the factor \(1/\left(1-\rho(j,C)\right)\). Lemma 2: _For any solution of \((\rho\text{MIP})\), the completion time of every job is \(C^{*}\)._  
Proof: Consider a solution \(\overline{X}\) of \((\rho\text{MIP})\). For every job \(j\), the idle time per period is:  
\[\bar{I}_{j} =\rho(j,C)\cdot\overline{L}_{j}\] \[C^{*}\geq C^{\text{sat}}_{\max}. \tag{26}\]0 \[C^{*}\geq C^{\text{sat}}_{\max}. \tag{26}\]1Using Equation (1), the job completion time \(C(j)\) is then:  
\[C^{*}\geq C^{\text{sat}}_{\max}. \tag{26}\]2 \[C^{*}\geq C^{\text{sat}}_{\max}. \tag{26}\]3 \[C^{*}\geq C^{\text{sat}}_{\max}. \tag{26}\]4  
Now, we show that for a given target makespan \(C^{*}\), a solution to \((\rho\text{MIP})\) is a solution to \((\text{TAP})\), i.e., an element of the Pareto frontier. Furthermore, ignoring artificial idle times, a solution to \((\text{TAP})\) can be found by solving \((\rho\text{MIP})\) with an appropriate target makespan \(C^{*}\). Theorem 5.: _For a given target makespan \(C^{*}\), any solution of \((\rho\text{MIP})\) is a solution of \((\text{TAP})\) with makespan at most \(C^{*}\). Conversely, any solution of \((\text{TAP})\) with makespan \(C^{*}\) can be transformed into a solution of \((\rho\text{MIP})\) with target makespan \(C^{*}\)._  
Proof. : Algorithm \((\rho\text{MIP})\) has been constructed from \((\text{QTAP})\) by fixing the variables \(\overline{I}\) and \(\overline{L}\) for a given target makespan \(C^{*}\). Therefore, any solution to \((\rho\text{MIP})\) is a solution to \((\text{QTAP})\) and therefore to \((\text{TAP})\). Moreover, by definition of \((\rho\text{MIP})\), the makespan of the any solution is at most \(C^{*}\). On the other hand, given a solution \(\overline{X}\) of \((\text{TAP})\), we can increase the completion time of every job up to the makespan \(C^{*}\). After adding such artificial idle times, note that the new solution \(\overline{X}^{*}\) fulfills Equation (28) for all jobs. Therefore, it is also a solution of \((\rho\text{MIP})\) with target makespan \(C^{*}\).