## 3 The Optimality Box
### Properties of a Job Permutation Based on Blocks
Since \(|B_{r}^{-}|\geq 2\) and all jobs are identical in the set \(B_{r}^{-}\), there is no job \(J_{v}\in B_{r}^{-}\), which has the optimality segment in any fixed permutation \(\pi_{k}\in S\). Similarly, one can prove that there is no job \(J_{v}\in B_{r}^{+}\), which has the optimality segment in any fixed permutation \(\pi_{k}\in S\). Thus, we conclude that if the condition of Theorem 3 holds for each block \(B_{r}\in B\), then each job \(J_{i}\in\mathcal{J}\) has no optimality segment in any fixed permutation \(\pi_{k}\in S\). Thus, if the condition of Theorem 3 holds, the equality \(\mathcal{OB}(\pi_{k},T)=\emptyset\) holds for any permutation \(\pi_{k}\in S\). _Necessity._ We prove the necessity by a contradiction. We assume that any permutation \(\pi_{k}\in S\) has an empty optimality box \(\mathcal{OB}(\pi_{k},T)=\emptyset\). Let the condition \(|B_{r}|=|B_{r}^{*}|\geq 2\) do not hold. If \(|B_{r}|=|B_{r}^{*}|=1\), the set \(B_{r}\) is a singleton and so job \(J_{r_{1}}\in B_{r}\) has the optimality segment \([p_{r_{1}}^{L},p_{r_{1}}^{U}]\) with the length \(p_{r_{1}}^{U}-p_{r_{1}}^{L}\geq 0\) in the permutation \(\pi_{k^{*}}\in S\), where all jobs are ordered according to the increasing of the left bounds of the cores of their blocks. Let the following condition hold:  
\[|B_{r}|>|B_{r}^{*}|\geq 2. \tag{1}\]  
The condition (1) implies that there exists at least one left job or right job or left-right job \(J_{r_{i}}\in B_{r}\). If job \(J_{r_{i}}\) is a left job or a left-right job (a right job) in the block \(B_{r}\), then job \(J_{r_{i}}\) must be located on the first place (on the last place, respectively) in the above permutation \(\pi_{k^{*}}\in S\) among all jobs from the block \(B_{r}\). All jobs from the set \(B_{r}\setminus\{B_{r}^{*}\cup\{J_{r_{i}}\}\}\) must be located between job \(J_{r_{v}}\in B_{r}^{*}\) and job \(J_{r_{w}}\in B_{r}^{*}\). Therefore, the left job \(J_{r_{i}}\) or the left-right job \(J_{r_{i}}\) (the right job \(J_{r_{i}}\)) has the following optimality segment \([p_{r_{i}}^{L},p_{r_{i}}^{L}]\) (segment \([b_{r}^{U},p_{r_{i}}^{U}]\), respectively) with the length \(b_{r}^{L}-p_{r_{i}}^{L}>0\) (the length \(p_{r_{i}}^{U}-b_{r}^{U}>0\), respectively) in the permutation \(\pi_{k^{*}}\). Let the equality \(B_{r}=B_{r}^{-}\cup B_{r}^{+}\) do not hold. If there exist a job \(J_{r_{i}}\in B_{r}^{*}\), this job must be located between the jobs \(J_{r_{v}}\in B_{r}^{-}\) and \(J_{r_{w}}\in B_{r}^{-}\). It is clear that the job \(J_{r_{i}}\) has the optimality segment \([b_{r}^{L},b_{r}^{U}]\) with the length \(b_{r}^{U}-b_{r}^{L}>0\) in the permutation \(\pi_{k^{*}}\). Let the following conditions hold: \(B_{r}=B_{r}^{-}\cup B_{r}^{+}\), \(|B_{r}^{-}|\geq 2\), \(|B_{r}^{+}|\geq 2\). However, we assume that jobs from the set \(B_{r}^{-}\) are not identical. Then the job \(J_{r_{u}}\in B_{r}^{-}\) with the largest segment \([p_{r_{u}}^{L},p_{r_{u}}^{U}]\) among the jobs from the set \(B_{r}^{-}\) must be located in the permutation \(\pi_{k^{*}}\) before other jobs from the set \(B_{r}^{-}\). It is clear that the job \(J_{r_{u}}\) has the optimality segment in the permutation \(\pi_{k^{*}}\). Similarly, we can construct the permutation \(\pi_{k^{*}}\) with the non-empty optimality box, if the jobs from the set \(B_{r}^{+}\) are not identical. Let the equality \(B_{r}=B_{r}^{-}\cup B_{r}^{+}\) hold. Let all jobs in the set \(B_{r}^{-}\) (and all jobs in the set \(B_{r}^{+}\)) be identical. However, we assume that the equality \(|B_{r}^{-}|=1\) holds. The job \(J_{r_{i}}\in B_{r}^{-}\) has the optimality segment in the permutation \(\pi_{k^{*}}\), if the job \(J_{r_{i}}\) is located before other jobs in the set \(B_{r}\). Similarly, one can construct the permutation \(\pi_{k^{*}}\) such that job \(J_{r_{i}}\in B_{r}^{+}\) has the optimality segment in the permutation \(\pi_{k^{*}}\), if the inequality \(|B_{r}^{+}|\geq 2\) is violated.