## 3 Definitions and Properties of the Problem
### Blocks of Tasks  
This section briefly introduces the definitions and properties of blocks and algorithms for their determination. They were described in detail in the work by [PERSON] [1]. Blocks of early tasks  
Subpermutation of tasks \(\pi^{\mathcal{T}}\) in permutation \(\pi\in\Phi\) is \(\mathcal{T}\)_-block_, if:  
1. each task \(j\in\pi^{\mathcal{T}}\) is early and \(d_{j}\geq C_{last}\), where \(C_{last}\) is the completion time of the last task in \(\pi^{\mathcal{T}}\),
2. \(\pi^{\mathcal{T}}\) is maximum subpermutation (in sense of number of elements) satisfying the restriction (a). It is easy to see that if \(\pi^{\mathcal{T}}\) is \(\mathcal{T}\)-block, then the inequality \(\min\{d_{j}:\ j\in\pi^{\mathcal{T}}\}\geq C_{last}\) is satisfied. Therefore, in any permutation of elements from \(\pi^{\mathcal{T}}\) every task in permutation \(\pi\) is early. Using this property, we present the algorithm determining the first \(\mathcal{T}\)-block in permutation \(\pi\). Input of Algorithm 1 is permutation \(\pi\), and output some \(\mathcal{T}\)-block of this permutation. In line 1 first due date job is determined. Next in lines 4-7, it is checked whether adding another due task to the block will keep the following property: in any permutation of these tasks, all tasks are on time. The computational complexity of the algorithm is \(O(n)\)Blocks of tardy tasks. Subpermutation of tasks \(\pi^{\mathcal{D}}\) in permutation \(\pi\in\Phi\) is called \(\mathcal{D}\)-_block_, if:  
each task \(j\in\pi^{\mathcal{D}}\) is tardy and \(d_{j}<S_{first}+p_{j}\), where \(S_{first}\) is the starting time of the first task in \(\pi^{\mathcal{D}}\),  
\(\pi^{\mathcal{D}}\) is the maximum subpermutation (in sense of number of elements) satisfying the constraint (a\({}^{\prime}\)). It is easy to see that in any permutation of elements from \(\pi^{\mathcal{D}}\) each task (belonging to \(\pi^{\mathcal{D}}\)) in permutation \(\pi\) is tardy. Similarly, as for \(\mathcal{T}\)-block, according to the above definition, we present the algorithm for determining the first \(\mathcal{D}\)-block in permutation \(\pi\). Input of Algorithm 2 is permutation \(\pi\), and output some \(\mathcal{D}\)-block of this permutation. In line 1 first tardy job is determined. Next, in lines 5-8, it is checked whether adding another tardy job to the block will keep the following property: in any permutation of these tasks, all tasks are tardy. The computational complexity of the algorithm is \(O(n)\). ```
Input : permutation \(\pi=(\pi(1),\pi(2),\ldots,\pi(n))\); Output :subpermutation (\(\mathcal{T}\)-block) \(\pi^{\mathcal{D}}=(\pi(v),\pi(v+1),\ldots,\pi(r-1),\pi(r))\);
1 Let \(\pi(v)\) be the first task in \(\pi\) such that \(C_{\pi(v)}>d_{\pi(v)}\); if no such a tasks then return\(\emptyset\);
2\(\pi^{\mathcal{D}}\leftarrow\pi(v)\);
3\(r\gets v\);
4\(S_{first}\gets C_{\pi(v)}-p_{\pi(v)}\);
5 while\(|\pi^{\mathcal{D}}|=r-v+1\wedge r<n\)do
6 if\(S_{first}+p_{\pi(r+1)}>d_{\pi(r+1)}\)then
7\(\pi^{\mathcal{D}}\leftarrow(\pi^{\mathcal{D}},\pi(r+1))\); {add an element to the subpermutation}
8\(r\gets r+1\);
```  
**Algorithm 2**\(\mathcal{AD}\)-**block**  
Theorem 1 ([1]). : _For any permutation \(\pi\in\Phi\) there is a partition of \(\pi\) into subpermutations such, in which each of them is:_  
\(\mathcal{T}\)_-block or_  
\(\mathcal{D}\)_-block._  
The algorithm for splitting permutation \(\pi\in\Phi\) into blocks has computational complexity \(O(n)\). Property 1.: _From block definition and from Theorem 1:_  
1. _Each task belongs to a certain_ \(\mathcal{T}\) _or_ \(\mathcal{D}\) _block,__. 2. _Different blocks contain various elements,_
3. _Two_ \(\mathcal{T}\) _or_ \(\mathcal{D}\) _blocks can appear directly next to each other,_
4. _A block can contain only one task._
5. _The partition of permutations into blocks is not explicit.