## 3 The Optimality Box
### Properties of a Job Permutation Based on Blocks  
The proof of Lemma 1 is based on Procedure 1. **Lemma 1**: _For the problem \(1|p_{i}^{L}\leq p_{i}\leq p_{i}^{U}|\sum C_{i}\), the set \(B=\{B_{1},B_{2},\ldots,B_{m}\}\) of all blocks can be determined in \(O(n\log n)\) time._  
The right bound \(b_{1}^{U}\) of the core of the first block \(B_{1}\in B\) is determined as follows: \(b_{1}^{U}=\min_{j_{1}\in\mathcal{J}}p_{i}^{U}\). Then, all jobs included in the block \(B_{1}\) may be determined as follows: \(B_{1}=\{J_{i}\in\mathcal{J}:p_{i}^{L}\leq b_{1}^{U}\leq p_{i}^{U}\}\). The left bound \(b_{1}^{L}\) of the core of the block \(B_{1}\) is determined as follows: \(b_{1}^{L}=\max_{j_{1}\in B_{1}}p_{i}^{L}\). Then, one can determine the second block \(B_{2}\in B\) via applying the above procedure to the subset of set \(\mathcal{J}\) without jobs \(J_{i}\), for which the equality \(b_{1}^{U}=p_{i}^{U}\) holds. This process is continued until determining the last block \(B_{m}\in B\). Thus, one can use the above procedure (we call it Procedure 1) for constructing the set \(B=\{B_{1},B_{2},\ldots,B_{m}\}\) of all blocks for the problem \(1|p_{i}^{L}\leq p_{i}\leq p_{i}^{U}|\sum C_{i}\). Obviously, Procedure 1 has the complexity \(O(n\log n)\). Any block from the set \(B\) has the following useful property. \begin{table}
\begin{tabular}{c c c c c c c c c c} \hline \hline \(i\) & **1** & **2** & **3** & **4** & **5** & **6** & **7** & **8** & **9** & **10** \\ \hline \(p_{i}^{L}\) & 6 & 7 & 6 & 1 & 8 & 17 & 15 & 24 & 25 & 26 \\ \hline \(p_{i}^{U}\) & 11 & 11 & 12 & 19 & 16 & 21 & 35 & 28 & 27 & 27 \\ \hline \end{tabular}
\end{table} 
Table 1: Input data for the problem \(1|p_{i}^{L}\leq p_{i}\leq p_{i}^{U}|\sum C_{i}\). **Lemma 2**. : _At most two jobs in the block \(B_{r}\in B\) may have the non-empty optimality segments in any fixed permutation \(\pi_{k}\in S\)._  
Proof. : Due to Definition 3, the inclusion \([b_{r}^{L},b_{r}^{U}]\subseteq[p_{i}^{L},p_{i}^{U}]\) holds for each job \(J_{i}\in B_{r}\). Thus, due to Definition 2, only job \(J_{k_{i}}\), which is the first one in the permutation \(\pi_{k}\) among the jobs from the block \(B_{r}\), and only job \(J_{k_{v}}\in B_{r}\), which is the last one in the permutation \(\pi_{k}\) among the jobs from the block \(B_{r}\), may have the non-empty optimality segments. It is clear that these non-empty segments look as follows: \([p_{k_{i}}^{L},u_{k_{i}}^{*}]\) and \([l_{k_{v}}^{*},p_{k_{v}}^{U}]\), where \(u_{k_{i}}^{*}\leq b_{r}^{L}\) and \(b_{r}^{U}\leq l_{k_{v}}^{*}\). **Lemma 3**. : _If \(\mathcal{OB}(\pi_{k},T)\
eq\emptyset\), then any two jobs \(J_{v}\in B_{r}\) and \(J_{w}\in B_{s}\), which are fixed in different blocks, \(r<s\), must be ordered in the permutation \(\pi_{k}\in S\) with the increasing of the left bounds (and the right bounds as well) of the cores of their blocks, i.e., the permutation \(\pi_{k}\) looks as follows: \(\pi_{k}=(\ldots,J_{v},\ldots,J_{w},\ldots)\), where \(b_{r}^{L}<b_{s}^{L}\)._  
Proof. : For any two jobs \(J_{v}\in B_{r}\) and \(J_{w}\in B_{s}\), \(r<s\), the condition \([p_{v}^{L},p_{v}^{U}]\cap[p_{w}^{L},p_{w}^{U}]=\emptyset\) holds. Therefore, the same permutation \(\pi_{k}=(\ldots,J_{v},\ldots,J_{w},\ldots)\) is obtained if jobs \(J_{v}\in B_{r}\) and \(J_{w}\in B_{s}\) are ordered either in the increasing of the left bounds of the cores of their blocks or in the increasing of the right bounds of the cores of their blocks. We prove Lemma 3 by a contradiction. Let the condition \(\mathcal{OB}(\pi_{k},T)\
eq\emptyset\) hold. However, we assume that there are fixed jobs \(J_{v}\in B_{r}\) and \(J_{w}\in B_{s}\), \(r<s\), which are located in the permutation \(\pi_{k}\in S\) in the decreasing order of the left bounds of the cores of their blocks \(B_{r}\) and \(B_{s}\). Note that blocks \(B_{r}\) and \(B_{s}\) cannot be virtual. Due to our assumption, the permutation \(\pi_{k}\) looks as follows: \(\pi_{k}=(\ldots,J_{w},\ldots,J_{v},\ldots)\), where \(b_{r}^{L}<b_{s}^{L}\).