## 3 The Optimality Box
### The Largest Relative Perimeter of the Optimality Box
Using the complexities of the Procedures 1 and 3, we conclude that the total complexity of the described algorithm (we call it Procedure 4) can be estimated by \(O(n\log n)\). **Lemma 5**. : _Within constructing a permutation \(\pi_{k}\) with the largest relative perimeter of the optimality box \(\mathcal{OB}(\pi_{k},T)\), any job \(J_{i}\) may be moved only within the blocks \(B(J_{i})\)._  
Proof. : Let job \(J_{i}\) be located in the block \(B_{r}\) in the permutation \(\pi_{k}\) such that \(J_{i}\
ot\in B_{r}\). Then, either the inequality \(p_{v}^{L}>p_{i}^{UI}\) or the inequality \(p_{v}^{UI}<p_{i}^{L}\) holds for each job \(J_{v}\in B_{r}\). If \(p_{v}^{L}>p_{i}^{UI}\), job \(J_{u}\) dominates job \(J_{i}\) (due to Theorem 2). If \(p_{v}^{UI}<p_{i}^{L}\), job \(J_{i}\) dominates job \(J_{u}\). Hence, if job \(J_{i}\) is located in the permutation \(\pi_{k}\) between jobs \(J_{v}\in B_{r}\) and \(J_{w}\in B_{r}\), then \(\mathcal{OB}(\pi_{k},T)=\emptyset\) due to Definition 2. Due to Lemma 5, if job \(J_{i}\) is fixed in the block \(B_{k}\in B\) (or is non-fixed but distributed to the block \(B_{k}\in B\)), then job \(J_{i}\) is located within the jobs from the block \(B_{k}\) in any permutation \(\pi_{k}\) with the largest relative perimeter of the optimality box \(\mathcal{OB}(\pi_{k},T)\). An Algorithm for Constructing a Job Permutation with the Largest Relative Perimeter of the Optimality Box  
Based on the properties of the optimality box, we next develop Algorithm 2 for constructing the permutation \(\pi_{k}\) for the problem \(1|p_{i}^{L}\leq p_{i}\leq p_{i}^{UI}|\sum C_{i}\), whose optimality box \(\mathcal{OB}(\pi_{k},T)\) has the largest relative perimeter among all permutations in the set \(S\). ```
Input: Segments \([p_{i}^{L},p_{i}^{UI}]\) for the jobs \(J_{i}\in\mathcal{J}\). Output: The permutation \(\pi_{



Procedure 5 for the Problem \(1|p_{i}^{L}\leq p_{i}\leq p_{i}^{[l]}\sum C_{i}\) with Blocks Including More Than One Non-Fixed Jobs

For solving the problem \(P_{1}\) at step 9 of the Algorithm 2, we use Procedure 5 based on dynamic programming. Procedure 5 allows us to construct the permutation \(\pi_{k}\in S\) for the problem \(1|p_{i}^{L}\leq p_{i}\leq p_{i}^{[l]}\sum C_{i}\) with the largest value of \(\mathit{Per}\mathcal{OB}(\pi_{k},T)\), where the set \(B\) consists of more than one block, \(m\geq 2\), the condition of Lemma 4 does not hold for the jobs \(\mathcal{J}=\{J_{1},J_{2},\ldots,J_{n}\}=:\mathcal{J}(B_{m}^{0})\), where \(\mathcal{B}_{m}^{0}\) denotes the following set of blocks: \(\{B_{1},B_{2},\ldots,B_{m}\}=:\mathcal{B}_{m}^{0}\). Moreover, the condition of Theorem 6 does hold for the set \(B=\mathcal{B}_{m}^{0}\) of the blocks, i.e., there is a block \(B_{r}\in\mathcal{B}_{m}^{0}\) containing more than one non-fixed jobs. For the problem \(1|p_{i}^{L}\leq p_{i}\leq p_{i}^{[l]}\sum C_{i}\) with \(\mathcal{J}=\{J_{1},J_{2},\ldots,J_{n}\}=\mathcal{J}(B_{m}^{0})\), one can calculate the following tight upper bound \(\mathit{Per}_{max}\) on the length of the relative perimeter \(\mathit{Per}\mathcal{OB}(\pi_{k},T)\) of the optimality box \(\mathcal{OB}(\pi_{k},T)\):

\[\mathit{Per}_{max}=2\cdot|B\setminus\underline{B}|+|\underline{B}|\geq \mathit{Per}\mathcal{OB}(\pi_{k},T), \tag{5}\]

where \(\underline{B}\) denotes the set of all blocks \(B_{r}\in B\) which are singletons, \(|B_{r}|=1\). The upper bound (5) on the relative perimeter \(\mathit{Per}\mathcal{OB}(\pi_{k},T)\) holds, since the relative optimality segment \(\frac{u_{i}^{L}-l_{i}^{L}}{p_{i}^{L}-p_{i}^{L}}\) for any job \(J_{i}\in\mathcal{J}\) is not greater than one. Thus, the sum of the relative optimality segments for all jobs \(J_{i}\in\mathcal{J}\) cannot be greater than \(2m\). Instead of describing Procedure 5 in a formal way, we next describe the first two iterations of Procedure 5 along with the application of Procedure 5 to a small example with four blocks and three non-fixed jobs (see Section 4.2).