## 3 The Optimality Box
### The Largest Relative Perimeter of the Optimality Box
The aim of Procedure 5 is to construct a complete job permutation \(\pi^{f}(B_{m};\mathcal{J}_{[f]})=\pi_{k}\in S\) such that the penalty \(\phi_{f}\) is minimal for all job permutations from the set \(S\). At the next iteration, a partial permutation \(\pi^{s}(B_{2};\mathcal{J}_{[s]})\) is chosen from the constructed solution tree such that the penalty \(\phi_{s}\) is minimal among the permutations corresponding to the leafs of the constructed solution tree. At the second iteration, the set \(\mathcal{P}(\mathcal{J}[B_{2}^{2}])=\{\mathcal{J}[B_{2}^{2}],\ldots,\emptyset\}\) of all subsets of the set \(\mathcal{J}[B_{2}^{2}]\) is generated and \(2^{|\mathcal{J}[B_{2}^{2}]|}\) permutations for all subsets \(\mathcal{P}(\mathcal{J}[B_{2}^{2}])\) of the jobs from the block \(B_{2}\) are constructed. For each generated permutation \(\pi^{p}(B_{2}^{2};\mathcal{J}_{[p]})\), where \(\mathcal{J}_{[p]}\in\mathcal{P}(\mathcal{J}[B_{2}^{2}])\), the penalty \(\phi_{v}\) is calculated using the equality \(\phi_{v}=\phi_{l}+\Delta\phi_{k}\), where the edge \([l,v]\) belongs to the solution tree \(\mathcal{T}_{2}=(V_{2},E_{2})\) and \(\Delta\phi_{k}\) denotes the penalty reached for the optimal permutation \(\pi^{0\to v}(B_{2};\mathcal{J}_{[v]})\) constructed from the permutation \(\pi^{v}(B_{1};\mathcal{J}_{[v]})\) using \(O(n)\)-Procedure 3. For the consideration at the next iteration, one chooses the partial permutation \(\pi^{d}(B_{c};\mathcal{J}_{[d]})\) with the minimal value of the penalty for the partial permutations in the leaves of the constructed solution tree. The whole solution tree is constructed similarly until there is a partial permutation with a smaller value of the penalty \(\phi_{t}\) in the constructed solution tree. ### The Application of Procedure 5 to the Small Example

Table 1 presents input data for the example of the problem \(1|p_{i}^{L}\leq p_{i}\leq p_{i}^{U}|\sum C_{i}\) described in Section 3.1. The jobs \(J_{4}\), \(J_{5}\) and \(J_{7}\) are non-fixed: \(\mathcal{J}[B_{1}]=\{J_{4},J_{5}\}\), \(\mathcal{J}[B_{2}]=\{J_{4},J_{5},J_{7}\}\), \(\mathcal{J}[B_{3}]=\{J_{4},J_{6},J_{7}\}\), \(\mathcal{J}[B_{4}]=\{J_{7}\}\). The job \(J_{4}\) must be distributed either to the block \(B_{1}\), \(B_{2}\), or to the block \(B_{3}\). The job \(J_{5}\) must be distributed either to the block \(B_{1}\), or to the block \(B_{2}\). The job \(J_{7}\) must be distributed either to the block \(B_{2}\), \(B_{3}\), or to the block \(B_{4}\). The relative perimeter of the optimality box \(\mathcal{OB}(\pi_{k},T)\) for any job permutation \(\pi_{k}\in S\) cannot be greater than \(Per_{max}=4\times 2=8\) due to the upper bound on the relative perimeter \(Per\mathcal{OB}(\pi_{k},T)\) given in (5). At the first iteration of Procedure 5, the set \(\mathcal{P}(\mathcal{J}[B_{1}^{1}])=\{\emptyset,\{J_{4}\},\{J_{5}\},\{J_{4},J_{5 }\}\}\) is constructed and permutations \(\pi^{1}(B_{1}^{1};\emptyset),\pi^{2}(B_{1}^{1};J_{4}),\pi^{3}(B_{1}^{1};J_{5})\) and \(\pi^{4}(B_{1}^{1};J_{4},J_{5})\) are generated. For each element of the set \(\mathcal{P}(\mathcal{J}[B_{1}^{1}])\), we construct a permutation with the maximal length of the relative perimeter of the optimality box and calculate the penalty. We obtain the following permutations with their penalties: \(\pi^{0\to 1}(B_{1}^{1};\emptyset)=(I_{1},J_{2},J_{3})\), \(\phi_{1}=1\frac{19}{30}\approx 1.633333\); \(\pi^{0\to 2}(B_{1}^{1};J_{4})=(J_{4},[PERSON]_{2},[PERSON]_{1},J_{3})\), \(\phi_{2}=1,5\); \(\pi^{0\to 3}(B_{1}^{1};J_{5})=([PERSON]_{1},J_{5},J_{2},J_{3})\), \(\phi_{3}=1\frac{13}{30}\approx 1.4333333\); \(\pi^{0\to 4}(B_{1}^{1};J_{4},J_{5})=(J_{4},J_{5},J_{1},J_{2},J_{3})\), \(\phi_{4}=1\frac{13}{30}\approx 1.433333\). where the permutation \(\pi_{t}\in S\) is optimal for the factual scenario \(p^{*}\in T\) of the job processing times. We call the scenario \(p^{*}=(p_{1}^{*},p_{2}^{*},\ldots,p_{n}^{*})\in T\)**factual**, if \(p_{i}\) is equal to the exact time needed for processing the job \(J_{i}\in\mathcal{J}\).