## 3 The Optimality Box
### Properties of a Job Permutation Based on Blocks
Using Definition 3, one can convince that the cores of any two blocks have no common point. Thus, the inequality \(b_{r}^{L}<b_{s}^{L}\) implies the inequality \(b_{r}^{U}<b_{s}^{L}\). The inequalities \(p_{v}^{L}\leq p_{v}\leq b_{r}^{U}<b_{s}^{L}\leq p_{w}^{L}\leq p_{w}^{L}\) hold for any feasible processing time \(p_{v}\) and any feasible processing time \(p_{w}\), where \(p\in T\). Hence, the inequality \(p_{v}<p_{w}\) holds as well, and due to Theorem 1, the permutation \(\pi_{k}\in S\) cannot be optimal for any fixed scenario \(p\in T\). Thus, the equality \(\mathcal{OB}(\pi_{k},T)=\emptyset\) holds due to Definition 2. This contradiction with our assumption completes the proof. Next, we assume that blocks in the set \(B=\{B_{1},B_{2},\ldots,B_{m}\}\) are numbered according to the increasing of the left bounds of their cores, i.e., the inequality \(b_{v}^{L}<b_{u}^{L}\) implies \(v<u\). Due to Definition 3, each block \(B_{r}=\{J_{r_{1}},J_{r_{2}},\ldots,J_{r_{|B_{r}|}}\}\) may include jobs of the following four types. If \(p_{r_{i}}^{L}=b_{r}^{L}\) and \(p_{r_{i}}^{U}=b_{r}^{U}\), we say that job \(J_{r_{i}}\) is a **core** job in the block \(B_{r}\). Let \(B_{r}^{*}\) be a set of all core jobs in the block \(B_{r}\). If \(p_{r_{i}}^{L}<b_{r}^{U}\), we say that job \(J_{r_{i}}\) is a **left** job in the block \(B_{r}\). If \(p_{r_{i}}^{U}>b_{r}^{U}\), we say that job \(J_{r_{i}}\) is a **right** job in the block \(B_{r}\). Let \(B_{r}^{*}\) (\(B_{r}^{+}\)) be a set of all left (right) jobs in the block \(B_{r}\). Note that some job \(J_{r_{i}}\in B_{r}\) may be **left-right** job in the block \(B_{r}\), since it is possible that \(B\setminus\{B_{r}^{*}\cup B_{r}^{-}\cup B_{r}^{+}\}\
eq\emptyset\). Two jobs \(J_{v}\) and \(J_{w}\) are **identical** if both equalities \(p_{v}^{L}=p_{w}^{L}\) and \(p_{v}^{U}=p_{w}^{U}\) hold. Obviously, if the set \(B_{r}\in B\) is a singleton, \(|B_{r}|=1\), then the equality \(B_{r}=B_{r}^{*}\) holds. Furthermore, the latter equality cannot hold for a virtual block \(B_{t}\in B\) since any trivial block must contain at least two non-fixed jobs. **Theorem 3**. : _For the problem \(1|p_{i}^{L}\leq p_{i}\leq p_{i}^{U}|\sum C_{i}\), any permutation \(\pi_{k}\in S\) has an empty optimality box \(\mathcal{OB}(\pi_{k},T)=\emptyset\), if and only if for each block \(B_{r}\in B\), either condition \(|B_{r}|=|B_{r}^{*}|\geq 2\) holds or \(B_{r}=B_{r}^{-}\cup B_{r}^{+}\), all jobs in the set \(B_{r}^{-}\) (in the set \(B_{r}^{+}\)) are identical and the following inequalities hold: \(|B_{r}^{-}|\geq 2\) and \(|B_{r}^{+}|\geq 2\)._  
Proof. : _Sufficiency._ It is easy to prove that there is no virtual block in the considered set \(B\). First, we assume that for each block \(B_{r}\in B\), the condition \(|B_{r}|=|B_{r}^{*}|\geq 2\) holds. Due to Lemma 3, in the permutation \(\pi_{k}\in S\) with the non-empty optimality box \(\mathcal{OB}(\pi_{k},T)\
eq\emptyset\), all jobs must be located in the increasing order of the left bounds of the cores of their blocks. However, in the permutation \(\pi_{k}\in S\), the following two equalities hold for each block \(B_{r}\in B\): \(\min_{j\in B_{r}}p_{i}^{U}=\max_{j\in B_{r}}p_{i}^{U}\) and \(\max_{j\in B_{r}}p_{i}^{L}=\min_{j\in B_{r}}p_{i}^{U}\). Since \(|B_{r}|\geq 2\), there is no job \(J_{v}\in B_{r}\)which has an optimality segment in any fixed permutation \(\pi_{k}\in S\) due to Lemma 2. Hence, the equality \(\mathcal{OB}(\pi_{k},T)=\emptyset\) must hold, if the condition \(|B_{r}|=|B_{r}^{*}|\geq 2\) holds for each block \(B_{r}\in B\). We assume that there exists a block \(B_{r}\in B\) such that all jobs are identical in the set \(B_{r}^{-}\) with \(|B_{r}^{-}|\geq 2\) and all jobs are identical in the set \(B_{r}^{+}\) with \(|B_{r}^{+}|\geq 2\). Thus, for the permutation \(\pi_{k}\in S\), the equalities \(\min_{j_{l}\in B_{r}^{-}}p_{l}^{U}=\max_{j_{l}\in B_{r}^{-}}p_{l}^{U}\) and \(\max_{j_{l}\in B_{r}^{-}}p_{l}^{U}=\min_{j_{l}\in B_{r}^{-}}p_{l}^{U}\) hold.