## 3 The Optimality Box
### The Largest Relative Perimeter of the Optimality Box
Step 3: ELSE determine the set \(B\) of all blocks using the \(O(n\log n)\)-Procedure 1 described in the proof of Lemma 1 Step 4: Index the blocks \(B=\{B_{1}.B_{2},\ldots,B_{m}\}\) according to increasing  left bounds of their cores (Lemma 3) Step 5: IF\(\mathcal{J}=B_{1}\) THEN problem \(1|p_{i}^{L}\leq p_{i}\leq p_{i}^{LI}|\sum C_{i}\) is called problem \(P_{1}\) (Theorem 5) set \(i=0\) GOTO step 8 ELSE set \(i=1\) Step 6: IF there exist two adjacent blocks \(B_{r^{*}}\in B\) and \(B_{r^{*}+1}\in B\) such that \(B_{r^{*}}\cap B_{r^{*}+1}=\emptyset\); let \(r\) denote the minimum of the above index \(r^{*}\) in the set \(\{1,2,\ldots,m\}\) THEN decompose the problem \(P\) into subproblem \(P_{1}\) with the set of jobs \(\mathcal{J}_{1}=\cup_{k=1}^{r}B_{k}\) and subproblem \(P_{2}\) with the set of jobs \(\mathcal{J}_{2}=\cup_{k=r+1}^{m}B_{k}\) using Lemma 4;  set \(P=P_{1}\), \(\mathcal{J}=\mathcal{J}_{1}\), \(B=\{B_{1},B_{2},\ldots,B_{r}\}\) GOTO step 7 ELSE 7: IF\(B\
eq\{B_{1}\}\) THEN GOTO step 9 ELSE Step 8: Construct the permutation \(\pi^{\delta(i)}\) with the minimal value of the error function \(F(\pi_{k},T)\) using Procedure 3+\(F(\pi_{k},t)\)  IF\(i=0\) or \(\mathcal{J}_{2}=B_{m}\) GOTO step 12 ELSE 9: IF there exists a block in the set \(B\) containing more than one non-fixed jobs THEN construct the permutation \(\pi^{\delta(i)}\) with the minimal value of the error function \(F(\pi_{k},T)\) for the problem \(P_{1}\) using Procedure 5+\(F(\pi_{k},t)\) GOTO step 11 Step 10: ELSE construct the permutation \(\pi^{\delta(i)}\) with the minimal value of the error function \(F(\pi_{k},T)\) for the problem \(P_{1}\) using Procedure 3+\(F(\pi_{k},t)\)  IF\(i=0\) or \(\mathcal{J}_{2}=B_{m}\) GOTO step 12 ELSE 9: IF there exists a block in the set \(B\) containing more than one non-fixed jobs THEN construct the permutation \(\pi^{\delta(i)}\) with the minimal value of the error function \(F(\pi_{k},T)\) for the problem \(P_{1}\) using Procedure 5+\(F(\pi_{k},t)\) GOTO step 11 Step 10: ELSE construct the permutation \(\pi^{\delta(i)}\) with the minimal value of the error function \(F(\pi_{k},T)\) for the problem \(P_{1}\) using Procedure 3+\(F(\pi_{k},t)\)  IF\(i=0\) or \(\mathcal{J}_{2}=B_{m}\) GOTO step 12 ELSE 9: IF there exists a block in the set \(B\) containing more than one non-fixed jobs THEN construct the permutation \(\pi^{\delta(i)}\) with the minimal value of the error function \(F(\pi_{k},T)\) for the problem \(P_{1}\) using Procedure 5+\(F(\pi_{k},t)\) GOTO step 11 Step 11: Construct the optimality box \(\mathcal{OB}(\pi^{\delta(i)},T)\) for the permutation \(\pi^{\delta(i)}\) using Algorithm 1 IF\(\mathcal{J}_{2}\
eq B_{m}\) and \(i\geq 1\) THEN set \(i:=i+1\), \(P=P_{2}\), \(\mathcal{J}=\mathcal{J}_{2}\), \(B=\{B_{r+1},B_{r+2},\ldots,B_{m}\}\) GOTO step 6 ELSE IF\(\mathcal{J}_{2}=B_{m}\) THEN GOTO step 8 Step 12: IF\(i>0\) THEN set \(v=i\), determine the permutation \(\pi_{k}=(\pi^{\delta(1)},\pi^{\delta(2)},\ldots,\pi^{\delta(v)})\) and the optimality box: \(\mathcal{OB}(\pi_{k},T)=\times_{i\in\{1,2,\ldots,p\}}\mathcal{OB}(\pi^{\delta(i )},T)\) GOTO step 13 ELSE\(\mathcal{OB}(\pi_{k},T)=\mathcal{OB}(\pi^{\delta(0)},T)\) Step 13: The optimality box \(\mathcal{OB}(\pi_{k},T)\) has the minimal value of the error function \(F(\pi_{k},T)\) STOP. ```

**Algorithm 3**

In Section 6, we describe the results of the computational experiments on applying Algorithm 3 to the randomly generated problems \(1|p_{i}^{L}\leq p_{i}\leq p_{i}^{U}|\sum C_{i}\). ## 6 Computational Results

For the benchmark instances \(1|p_{i}^{L}\leq p_{i}\leq p_{i}^{U}|\sum C_{i}\), where there are no properties of the randomly generated jobs \(\mathcal{J}\), which make the problem harder, the mid-point permutation \(\pi_{mid-p}=\pi_{e}\in S\), where all jobs \(J_{i}\in\mathcal{J}\) are ordered according to the increasing of the mid-points \(\frac{p_{i}^{U}+p_{i}^{L}}{2}\) of their segments \([p_{i}^{L},p_{i}^{U}]\), is often close to the optimal permutation.