## 3 The Optimality Box
### The Largest Relative Perimeter of the Optimality Box
Let \(\mathcal{T}=(V,E)\) denote the solution tree constructed by Procedure 5 at the last iteration, where \(V\) is a set of the vertexes presenting states of the solution process and \(E\) is a set of the edges presenting transformations of the states to another ones. A subgraph of the solution tree \(\mathcal{T}=(V,E)\) constructed at the iteration \(h\) is denoted by \(\mathcal{T}_{h}=(V_{h},E_{h})\). All vertexes \(i\in V\) of the solution tree have their ranks from the set \(\{0,1,\ldots,m=|B|\}\). The vertex \(0\) in the solution tree \(\mathcal{T}_{h}=(V_{h},E_{h})\) has a zero rank. The vertex \(0\) is characterized by a partial job permutation \(\pi^{0}(\emptyset;\emptyset)\), where the non-fixed jobs are not distributed to their blocks. All vertexes of the solution tree \(\mathcal{T}_{h}\) having the first rank are generated at iteration 1 from vertex 0 via distributing the non-fixed jobs \(\mathcal{J}[B_{1}]\) of the block \(B_{1}\), where \(\mathcal{J}[B_{1}]\subseteq B_{1}\). Each job \(J_{v}\in\mathcal{J}[B_{1}]\) must be distributed either to the block \(B_{1}\) or to another block \(B_{j}\in B\) with the inclusion \(J_{v}\in\mathcal{J}[B_{j}]\). Let \(B_{k}^{t}\) denote a set of all non-fixed jobs \(J_{i}\in B_{k}\), which are not distributed to their blocks at the iterations with the numbers less than \(t\). A partial permutation of the jobs is characterized by the notation \(\pi^{u}(B_{k};\mathcal{J}_{[u]})\), where \(u\) denotes the vertex \(u\in V_{t}\) in the constructed solution tree \(\mathcal{T}_{t}=(V_{t},E_{t})\) and \(\mathcal{J}_{[u]}\) denotes the non-fixed jobs from the set \(\mathcal{J}[B_{k}]\), which are distributed to the block \(B_{k}\) in the vertex \(j\in V_{t}\) of the solution tree such that the arc \((j,u)\) belongs to the set \(E_{t}\). At the first iteration of Procedure 5, the set \(\mathcal{P}(\mathcal{J}[B_{1}^{1}])=\{\mathcal{J}[B_{1}^{1}],\ldots,\emptyset\}\) of all subsets of the set \(\mathcal{J}[B_{1}^{1}]\) is constructed and \(2^{|\mathcal{J}[B_{1}^{1}]|}\) partial permutations are generated for all subsets \(\mathcal{P}(\mathcal{J}[B_{1}^{1}])\) of the non-fixed jobs \(\mathcal{J}[B_{1}^{1}]\). The constructed solution tree \(\mathcal{T}_{1}=(V_{1},E_{1})\) consists of the vertexes \(0,1,\ldots,2^{|\mathcal{J}[B_{1}^{1}]|}\) and \(2^{|\mathcal{J}[B_{1}^{1}]|}\) arcs connecting vertex \(0\) with the other vertexes in the tree \(\mathcal{T}_{1}\). For each generated permutation \(\pi^{u}(B_{k};\mathcal{J}_{[u]})\), where \(\mathcal{J}_{[u]}\in\mathcal{P}(\mathcal{J}[B_{k}^{1}])\), the penalty \(\phi_{u}\) determined in (6) is calculated, which is equal to the difference between the lengths of the maximal possible relative perimeter \(Per_{max}\) of the optimality box \(\mathcal{OB}(\pi_{k},T)\) and the relative perimeter of the optimality box \(\mathcal{OB}(\pi^{u}(B_{k};\mathcal{J}_{[u]}),T)\), which may be constructed for the permutation \(\pi^{u}(B_{k};\mathcal{J}_{[u]})\):

\[Per\mathcal{OB}(\pi^{u}(B_{k};\mathcal{J}_{[u]}),T)=\sum_{i\leq k}Per_{max}^{u }-\phi_{u}, \tag{6}\]

where \(Per_{max}^{u}\) denotes the maximal length of the relative perimeter of the permutation \(\pi^{u}(B_{k};\mathcal{J}_{[u]}),T)\). The penalty \(\phi_{u}\) is calculated using \(O(n)\)-Procedure 3 described in the proof of Theorem 5. The complete permutation \(\pi^{0\to u}(B_{k};\mathcal{J}_{[u]})\) with the end \(\pi^{u}(B_{k};\mathcal{J}_{[u]})\) is determined based on the permutations \(\pi^{s}(B_{c};\mathcal{J}_{[s]})\), where each vertex \(s\) belongs to the chain \((0\to u)\) between vertexes \(0\) and \(u\) in the solution tree \(\mathcal{T}_{t}=(V_{t},E_{t})\) and each block \(B_{c}\) belongs to the set \(B^{u}=\{B_{1},B_{2},\ldots,B_{k}\}\). The permutation \(\pi^{0\to u}(B_{k};\mathcal{J}_{[u]})\) includes all jobs, which are fixed in the blocks \(B_{c}\in B^{u}\) or distributed to their blocks \(B_{c}\in B^{u}\) in the optimal order for the penalty \(\phi_{u}\).