## 3 The Optimality Box
### The Largest Relative Perimeter of the Optimality Box  
If the permutation \(\pi_{k}\in S\) has the non-empty optimality box \(\mathcal{OB}(\pi_{k},T)\
eq\emptyset\), then one can calculate the length of the relative perimeter of this box as follows:  
\[\mathit{Per}\mathcal{OB}(\pi_{k},T)=\sum_{h_{k}\in\mathcal{J}(\pi_{k})}\frac{u_ {k_{i}}^{*}-l_{k_{i}}^{*}}{p_{k_{i}}^{U}-p_{k_{i}}^{L}}, \tag{2}\]  
where \(\mathcal{J}(\pi_{k})\) denotes the set of all jobs \(J_{i}\in\mathcal{J}\) having optimality segments \([l_{k_{i}}^{*},u_{k_{i}}^{*}]\) with the positive lengths, \(l_{k_{i}}^{*}<u_{k_{i}}^{*}\), in the permutation \(\pi_{k}\). It is clear that the inequality \(l_{k_{i}}^{*}<u_{k_{i}}^{*}\) may hold only if the inequality \(p_{k_{i}}^{L}<p_{k_{i}}^{U}\) holds. Theorem 3 gives the sufficient and necessary condition for the smallest value of \(\mathit{Per}\mathcal{OB}(\pi_{k},T)\), i.e., the equalities \(\mathcal{J}(\pi_{k})=\emptyset\) and \(\mathit{Per}\mathcal{OB}(\pi_{k},T)=0\) hold for each permutation \(\pi_{k}\in S\). A necessary and sufficient condition for the largest value of \(\mathit{Per}\mathcal{OB}(\pi_{k},T)=n\) is given in Theorem 4. The sufficiency proof of Theorem 4 is based on Procedure 2. **Theorem 4**: _For the problem \(1|p_{i}^{L}\leq p_{i}\leq p_{i}^{U}|\sum\mathrm{C}_{i}\), there exists a permutation \(\pi_{k}\in S\), for which the equality \(\mathit{Per}\mathcal{OB}(\pi_{k},T)=n\) holds, if and only if for each block \(B_{r}\in B\), either \(|B_{r}|=|B_{r}^{*}|=1\) or \(B_{r}=B_{r}^{-}\cup B_{r}^{+}\) with \(|B_{r}|=2\)._  
Proof. : _Sufficiency._ Let the equalities \(|B_{r}|=|B_{r}^{*}|=1\) hold for each block \(B_{r}\in B\). Therefore, both equalities \(B_{r}=B_{r}^{*}\) and \(|B|=n\) hold. Due to Theorem 2 and Lemma 3, all jobs must be ordered with the increasing of the left bounds of the cores of their blocks in each permutation \(\pi_{k}\in S\) such that \(\mathcal{OB}(\pi_{k},T)\
eq\emptyset\). Each job \(J_{k_{i}}\in\mathcal{J}\) in the permutation \(\pi_{k}=(J_{k_{1}},J_{k_{2}},\ldots,J_{k_{n}})\) has the optimality segments \([l_{k_{i}}^{*},u_{k_{i}}^{*}]\) with the maximal possible length  
\[u_{k_{i}}^{*}-l_{k_{i}}^{*}=p_{k_{i}}^{U}-p_{k_{i}}^{L}. \tag{3}\]  
Hence, the desired equalities  
\[\mathit{Per}\mathcal{OB}(\pi_{k},T)=\sum_{h_{k}\in\mathcal{J}(\pi_{k})}\frac{ p_{k_{i}}^{U}-p_{k_{i}}^{L}}{p_{k_{i}}^{U}-p_{k_{i}}^{L}}=n \tag{4}\]  
hold, if the equalities \(|B_{r}|=|B_{r}^{*}|=1\) hold for each block \(B_{r}\in B\). Let there exist a block \(B_{r}\in B\) such that the equalities \(B_{r}=B_{r}^{-}\cup B_{r}^{+}\) and \(|B_{r}|=2\) hold. It is clear that the equalities \(|B_{r}^{-}|=|B_{r}^{+}|=1\) hold as well, and job \(J_{k_{i}}\) from the set \(B_{r}^{-}\) (from the set \(B_{r}^{+}\)) in the permutation \(\pi_{k}\) has the optimality segments \([l_{k_{i}}^{*},u_{k_{i}}^{*}]\) with the maximal possible length determinedin (3). Hence, the equalities (4) hold, if there exist blocks \(B_{r}\in B\) with the equalities \(B_{r}=B_{r}^{-}\cup B_{r}^{+}\) and \(|B_{r}|=2\). This efficiency proof contains the description of Procedure 2 with the complexity \(O(n)\). _Necessary._ If there exists at least one block \(B_{r}\in B\) such that neither condition \(|B_{r}|=|B_{r}^{*}|=1\) nor condition \(B_{r}=B_{r}^{-}\cup B_{r}^{+}\), \(|B_{r}|=2\) hold, then the equality (3) is not possible for at least one job \(J_{k_{i}}\in B_{r}\). Therefore, the inequality \(Per\mathcal{OB}(\pi_{k_{i}}T)<n\) holds for any permutation \(\pi_{k}\in S\). The length of the relative perimeter \(Per\mathcal{OB}(\pi_{k},T)\) may be used as a stability measure for the optimal permutation \(\pi_{k}\). If the permutation \(\pi_{k}\in S\) has the non-empty optimality box \(\mathcal{OB}(\pi_{k},T)\) with a larger length of the relative perimeter than the optimality box \(\mathcal{OB}(\pi_{t},T)\) has, \(\pi_{k}\
eq\pi_{t}\in S\), then the permutation \(\pi_{k}\in S\) may provide a smaller value of the objective function \(\sum C_{i}\) than the permutation \(\pi_{t}\).