## 3 The Optimality Box
### The Largest Relative Perimeter of the Optimality Box
As a result, all \(n-|\mathcal{J}^{*}|\) jobs are linearly ordered since all jobs \(\mathcal{J}\setminus\mathcal{J}^{*}\) are fixed in their blocks. Such an ordering of the jobs takes \(O(n\log n)\) time due to Lemma 1. Since each block \(B_{r}\in B\) contain at most one non-fixed job, the equality \(B(J_{u})\cap B(J_{v})=\emptyset\) holds for each pair of jobs \(J_{u}\in B(J_{u})\subseteq B\setminus B^{*}\) and \(J_{v}\in B(J_{v})\subseteq B\setminus B^{*}\), \(u\
eq v\). Furthermore, the problem \(1|p_{i}^{L}\leq p_{i}\leq p_{i}^{U}|\sum C_{i}\) may be decomposed into \(h=|\mathcal{J}^{*}|+|B^{*}|\) subproblems \(P_{1},P_{2},\ldots,P_{\lceil J^{*}\rceil},P_{\lceil J^{*}\rceil+1},\ldots,P_{h}\) such that the condition of Lemma 4 holds for each pair \(P_{r}\) and \(P_{r+1}\) of the adjacent subproblems, where \(1\leq r\leq h-1\). Using Lemma 4, we decompose the problem \(1|p_{i}^{L}\leq p_{i}\leq p_{i}^{U}|\sum C_{i}\) into \(h\) subproblems \(\{P_{1},P_{2},\ldots,P_{\lceil J^{*}\rceil},P_{\lceil J^{*}\rceil+1},\ldots,P_{ h}\}=\mathcal{P}\). The set \(\mathcal{P}\) is partitioned into two subsets, \(\mathcal{P}=\mathcal{P}^{1}\cup\mathcal{P}^{2}\), where the subset \(\mathcal{P}^{1}=\{P_{1},P_{2},\ldots,P_{\lceil J^{*}\rceil}\}\) contains all subproblems \(P_{f}\) containing all blocks from the set \(B(I_{j_{f}})\), where \(I_{j_{f}}\in\mathcal{J}^{*}\) and \(|\mathcal{P}^{1}|=|\mathcal{J}^{*}|\). The subset \(\mathcal{P}^{2}=\{P_{\lfloor J^{*}\rceil+1},\ldots,P_{h}\}\) contains all subproblems \(P_{d}\) containing one block \(B_{r_{d}}\) from the set \(\mathcal{B}^{*}\), \(|\mathcal{P}^{2}|=|B^{*}|\). If subproblem \(P_{d}\) belongs to the set \(\mathcal{P}^{2}\), then using \(O(n)\)-Procedure 3 described in the proof of Theorem 5, we construct the optimality box \(\mathcal{OB}(\pi(^{d}),T^{(d)})\) with the largest length of the relative perimeter for the subproblem \(P_{d}\), where \(\pi^{(d})\) denotes the permutation of the jobs \(B_{r_{d}}\subset B^{*}\) and \(T^{(d)}\subset T\). It takes \(O(|B_{r_{d}}|)\) time to construct a such optimality box \(\mathcal{OB}(\pi(^{d}),T^{(d)})\). If subproblem \(P_{f}\) belongs to the set \(\mathcal{P}^{1}\), it is necessary to consider all \(|B(I_{j_{f}})|\) fixings of the job \(I_{j_{f}}\) in the block \(B_{f_{f}}\) from the set \(B(J_{j_{f}})=\{B_{f_{1}},B_{f_{2}},\ldots,B_{\lceil B(J_{j_{f}})\rceil}\}\). Thus, we have to solve \(|B(J_{j_{f}})|\) subproblems \(P_{f}^{g}\), where job \(I_{i_{f}}\) is fixed in the block \(B_{f_{g}}\in B(J_{j_{f}})\) and job \(I_{i_{f}}\) is deleted from all other blocks \(B(J_{j_{f}})\setminus\{B_{f_{g}}\}\). We apply Procedure 3 for constructing the optimality box \(\mathcal{OB}(\pi^{(g)},T^{(f)})\) with the largest length of the relative perimeter \(Per\mathcal{OB}(\pi^{(g)},T^{(f)})\) for each subproblem \(P_{f}^{g}\), where \(g\in\{1,2,\ldots,|B(J_{j_{f}})|\}\). Then, we have to choose the largest length of the relative perimeter among \(|B(I_{j_{f}})|\) constructed ones: \(Per\mathcal{OB}(\pi^{(f^{\prime})},T^{(f)})=\max_{g\in\{1,2,\ldots,|B(I_{j_{f}})| \}}Per\mathcal{OB}(\pi^{(g)},T^{(f)})\). Due to Lemma 4, the optimality box \(\mathcal{OB}(\pi_{k},T)\) with the largest relative perimeter for the original problem \(1|p_{i}^{L}\leq p_{i}\leq p_{i}^{UI}|\sum C_{i}\) is determined as the Cartesian product of the optimality boxes \(\mathcal{OB}(\pi^{(d)},T^{(d)})\) and \(\mathcal{OB}(\pi^{(f^{\prime})},T^{(f)})\) constructed for the subproblems \(P_{d}\in\mathcal{P}^{2}\) and \(P_{f}\in\mathcal{P}^{1}\), respectively. The following equality holds: \(\mathcal{OB}(\pi_{k},T)=\times_{p_{f}\in\mathcal{P}^{1}}\mathcal{OB}(\pi^{(f^ {\prime})},T^{(f)})\times(\times_{P_{d}\in\mathcal{P}^{2}}\mathcal{OB}(\pi^{(d )},T^{(d)}))\). The permutation \(\pi_{k}\) with the largest length of the relative perimeter of the optimality box \(\mathcal{OB}(\pi_{k},T)\) for the problem \(1|p_{i}^{L}\leq p_{i}\leq p_{i}^{UI}|\sum C_{i}\) is determined as the concatenation of the corresponding permutations \(\pi^{(f^{\prime})}\) and \(\pi^{(d)}\).