## 3 Definitions and Properties of the Problem
### Properties of Insert Moves  
The move \(m^{*}\in\mathcal{M}(\pi)\) is _a representative_ of a set of moves from a certain set of moves \(\mathcal{W}\subset\mathcal{M}(\pi)\), if  
\[\forall r\in\mathcal{W},\ \ \mathcal{F}(r(\pi))\geq\mathcal{F}(m^{*}(\pi)).\]  
Let us assume that permutation \(\pi\in\mathit{Phi}\) is \(\mathcal{D}\)-OPT, and the neighborhood is generated by insert type of (_i-moves_). If \(i_{l}^{k}\) is a representative of the moves of the set \(\mathcal{M}^{k}\subset\mathcal{M}(\pi)\) (\(i_{l}^{k}\
ot\in\mathcal{M}^{k}\)), then moves belonging to \(\mathcal{M}^{k}\) are removed from the set \(\mathcal{M}_{bf}^{k}\) i \(\mathcal{M}_{af}^{k}\) i.e., they are modified as follows:  
\[\mathcal{M}_{bf}^{k}\leftarrow\mathcal{M}_{bf}^{k}\setminus\mathcal{M}^{k} \ \ \text{and}\ \ \mathcal{M}_{af}^{k}\leftarrow\mathcal{M}_{af}^{k}\setminus\mathcal{M}^{k}.\]  
This procedure makes it possible, in the process of generating the neighborhood, to omit the elements that do not directly improve the value of the criterion. Theorem 3: _If task \(\pi(k)\) after swapping to the position \(l\) ( after the move \(i_{l}^{k}\)), \(1\leq k<l\leq n\), in permutation \(\pi\) is early (i.e., \(C_{\pi(l)}\leq d_{\pi(k)}\)), then for a pair of moves \(i_{l-1}^{k}\), \(i_{l}^{k}\) there is_  
\[\mathcal{F}(\pi_{l-1}^{k})\geq\mathcal{F}(\pi_{l}^{k}).\]  
Proof: Let us assume that the task \(\pi(k)\) after swapping to position \(l\) (i.e., executing the move \(i_{l}^{k}\)) in permutation \(\pi\) is early. We consider two moves: \(i_{l}^{k}\) and \(i_{l-1}^{k}\). In permutations \(\pi_{l}^{k}\) and \(\pi_{l-1}^{k}\) generated by these moves there occurs:  
\[\pi_{l}^{k}(j)=\pi_{l-1}^{k}(j)\ \ \ \text{for}\  
Thus, this is the last position in the permutation \(\pi\), on which the task \(\pi(k)\) is swapped, after execution of \(i\)_-move_, is early. Therefore, the task \(\pi(k)\) is early in each permutation \(\pi_{l}^{k}\), \(l=1,2,\ \ldots,\tau(k)\).  
For a sequence of moves \(i_{1}^{k},i_{2}^{k},\ldots,i_{\tau(k)}^{k}\) of task \(\pi(k)\) there:  
\[\mathcal{F}(\pi_{1}^{k})\geq\mathcal{F}(\pi_{2}^{k})\geq\ldots\geq\mathcal{F} (\pi_{\tau(k)}^{k}),\]  
where parameter \(\tau(k)\) is designated by (6). Proof. : The move \(i_{l}^{k},l=1,2,\ldots,\tau(k)\) generates permutation \(\pi_{l}^{k}\), in which the task \(\pi(k)\) is early. Using the Theorem 3, it is easy to show that \(\mathcal{F}(\pi_{1}^{k})\geq\mathcal{F}(\pi_{2}^{k})\geq\ldots\geq\mathcal{F} (\pi_{\tau(k)}^{k})\). Therefore, the move \(i_{\tau(k)}^{k}\) is a representative of a set \(\{i_{1}^{k},\ i_{2}^{k},\ldots,i_{\tau(k)-1}^{k}\}\), hence these moves can be omitted by modifying accordingly the sets:  
\[\mathcal{M}_{bf}^{k}\leftarrow\mathcal{M}_{bf}^{k}\backslash\{i_{1}^{k},\ i_{2}^{k},\ldots,i_{\tau(k)-1}^{k}\},\]  
\[\mathcal{M}_{af}^{k}\leftarrow\mathcal{M}_{af}^{k}\backslash\{i_{1}^{k},\ i_{2}^{k},\ldots,i_{\tau(k)-1}^{k}\}. \tag{7}\]  
Let \(\pi(a)\ i\ \pi(b)\) be the first and the last task \(\mathcal{T}\)-bloku in permutation \(\pi\). If \(1\leq k<a\) and \(a\leq\tau(k)\leq b\), where parameter \(\tau(k)\) is defined in (6), then for the sequence of moves \(i_{\tau(k)+1^{\prime}}^{k}\), \(i_{\tau(k)+2^{\prime}}^{k}\ldots i_{b-1^{\prime}}^{k}\), \(i_{b}^{k}\) there is:  
\[\mathcal{F}(\pi_{\tau(k)+1}^{k})\leq\mathcal{F}(\pi_{\tau(k)+2}^{k})\leq \ldots\leq\mathcal{F}(\pi_{b-1}^{k})\leq\mathcal{F}(\pi_{b}^{k}).\]  
Proof. : The move \(i_{l}^{k},l=\tau(k)+1,\tau(k)+2,\ldots,b\) generates permutation \(\pi_{l}^{k}\), in which the task \(\pi(k)\) is tardy. Using the Theorem 4, it is easy to show that  
\[\mathcal{F}(\pi_{\tau(k)+1}^{k})\leq\mathcal{F}(\pi_{\tau(k)+2}^{k})\leq \ldots\leq\mathcal{F}(\pi_{b-1}^{k})\leq\mathcal{F}(\pi_{b}^{k}).\]  
The move \(i_{\tau(k)+1}^{k}\) is a representative of a set \(\{i_{\tau(k)+2}^{k},\ i_{\tau(k)+3}^{k},\ldots,i_{b-1^{\prime}}^{k},\ r_{b}^{k}\}\).