## 3 The Optimality Box
### The Largest Relative Perimeter of the Optimality Box
: _If \(J_{i}\
ot\in B_{r}\in B\), then the job \(J_{i}\) must be located either on the left side from the core of the block \(B_{r}\) or on the right side from this core in any permutation \(\pi_{k}\) having the largest relative perimeter of the optimality box \(\mathcal{OB}(\pi_{k},T)\). Hence, job \(J_{i}\) must precede (or succeed, respectively) each job \(J_{v}\in B_{k}\). The permutation \(\pi_{t}\) of the jobs from the block \(B_{r}\) obtained using Procedure 3 described in the proof of Theorem 5, where jobs \(B_{r}\) are sequenced, remains the same if job \(J_{i}\
ot\in B_{r}\in B\) is added to the permutation \(\pi_{t}\)._  
**Lemma 4**. : _Let there exist two adjacent blocks \(B_{r}\in B\) and \(B_{r+1}\in B\), such that the equality \(B_{r}\bigcap B_{r+1}=\emptyset\) holds. Then the problem \(1|p_{i}^{L}\leq p_{i}\leq p_{i}^{L1}\bigcap C_{i}\) can be decomposed into the subproblem \(P_{1}\) with the set of jobs \(\mathcal{J}_{1}:=\bigcup_{k=1}^{r}B_{k}\) and the subproblem \(P_{2}\) with the set of jobs \(\mathcal{J}_{2}:=\bigcup_{k=r+1}^{m}B_{k}=\mathcal{J}\setminus\mathcal{J}_{1}\). The optimality box \(\mathcal{OB}(\pi_{k},T)\) with the largest length of the relative perimeter may be obtained as the Cartesian product of the optimality boxes constructed for the subproblems \(P_{1}\) and \(P_{2}\)._  
Proof. : Since the blocks \(B_{r}\) and \(B_{r+1}\) have no common jobs, the inequality \(p_{u}^{U}<p_{v}^{L}\) holds for each pair of jobs \(J_{u}\in\bigcup_{k=1}^{r}B_{k}\) and \(J_{v}\in\bigcup_{k=r+1}^{m}B_{k}\). Due to Theorem 2, any job \(J_{u}\in\bigcup_{k=1}^{r}B_{k}\) dominates any job \(J_{v}\in\bigcup_{k=r+1}^{m}B_{k}\). Thus, due to Definition 1, there is no optimal permutation \(\pi_{k}\in S\) for the instance \(1|p|\sum C_{i}\) with a scenario \(p\in T\) such that job \(J_{v}\) precedes job \(J_{u}\) in the permutation \(\pi_{k}\). Due to Definition 2, a non-empty optimality box \(\mathcal{OB}(\pi_{k},T)\) is possible only if job \(J_{u}\) is located before job \(J_{v}\) in the permutation \(\pi_{r}\). The optimality box \(\mathcal{OB}(\pi_{k},T)\) with the largest relative perimeter for the problem \(1|p_{i}^{L}\leq p_{i}\leq p_{i}^{U}|\sum C_{i}\) may be obtained as the Cartesian product of the optimality boxes with the largest length of the relative perimeters constructed for the subproblems \(P_{1}\) and \(P_{2}\), where the set of jobs \(\bigcup_{k=1}^{r}B_{k}\) and the set of jobs \(\bigcup_{k=r+1}^{m}B_{k}\) are considered separately one from another. Let \(B^{*}\) denote a subset of all blocks of the set \(B\), which contain only fixed jobs. Let \(\mathcal{J}^{*}\) denote a set of all non-fixed jobs in the set \(\mathcal{J}\). Let the set \(B(J_{u})\subseteq B^{*}\) denote a set of all blocks containing the non-fixed job \(J_{u}\in\mathcal{J}^{*}\). Theorem 5, Lemma 6 and the constructive proof of the following claim allows us to develop an \(O(n\log n)\)-algorithm for constructing the permutation \(\pi_{k}\) with the largest value of \(Per\mathcal{OB}(\pi_{k},T)\) for the special case of the problem \(1|p_{i}^{L}\leq p_{i}\leq p_{i}^{U}|\sum C_{i}\). The proof of Theorem 6 is based on Procedure 4. Theorem 6: _Let each block \(B_{r}\in B\) contain at most one non-fixed job. The permutation \(\pi_{k}\in S\) with the largest value of the relative perimeter \(Per\mathcal{OB}(\pi_{k},T)\) is constructed in \(O(n\log n)\) time._  
Proof. : There is no virtual block in the set \(B\), since any virtual block contains at least two non-fixed jobs while each block \(B_{r}\in B\) contains at most one non-fixed job for the considered problem \(1|p_{i}^{L}\leq p_{i}\leq p_{i}^{U}|\sum C_{i}\). Using \(O(n\log n)\)-Procedure 1 described in the proof of Lemma 1, we construct the set \(B=\{B_{1},B_{2},\ldots,B_{m}\}\) of all blocks. Using Lemma 3, we order the jobs in the set \(\mathcal{J}\setminus\mathcal{J}^{*}\) according to the increasing of the left bounds of the cores of their blocks.