## 2 Formulation of the Problem  
In the formulation part and throughout the paper, we use the following notations: \begin{tabular}{l l l} \(n\) & - & number of tasks, \\ \(\mathcal{J}\) & - & set of tasks, \\ \(p_{i}\) & - & time of task execution, \\ \(w_{i}\) & - & task's tardiness cost factor, \\ \(d_{i}\) & - & requested task completion time, \\ \(\pi\) & - & permutation of tasks, \\ \(\Phi\) & - & set of all permutation of elements from \(\mathcal{J}\), \\ \end{tabular} \begin{tabular}{l l l} \(\mathcal{N}(\pi)\) & - & neighborhood of solution \(\pi\), \\ \(S_{i}\) & - & task starting time \(i\in\mathcal{J}\), \\ \(C_{i}\) & - & task completion time \(i\in\mathcal{J}\), \\ \(T_{i}\) & - & task tardiness \(i\), \\ \(\pi^{\mathcal{T}}\) & - & semi block of early tasks, \\ \(\pi^{\mathcal{D}}\) & - & semi block of tardy tasks, \\ \(\mathcal{B}\) & - & partition of permutation into blocks, \\ \(\mathcal{F}(\approx)\) & - & sum of tardiness costs (criterion), \\ \end{tabular}   
_Total Weighted Tardiness Problem_, (in short TWT) can be formulated as follows:  
**TWT problem**: Each task from the set \(\mathcal{J}=\{1,2,\ldots,n\}\) is to be executed on one machine. Wherein the following restrictions must be met:  
1. all jobs are available at time zero,
2. the machine can process at most one job at a time,
3. preemption of the jobs is not allowed,
4. associated with each job \(j\in\mathcal{J}\) there is 1. processing time \(p_{j}\),
5. due date \(d_{j}\),
6. positive weight \(w_{j}\). The order in which tasks will be performed must be determined, which minimizes the sum of the cost of delays. As in [22], we denote the problem as \(1||\sum w_{i}T_{i}\). Any solution to the considered problem (the order in which the tasks are performed on the machine) can be represented by the permutation of tasks (elements of the set \(\mathcal{J}\)). By \(\Phi\) we denote the set of all such permutations. Let \(\pi\in\Phi\) be some permutation of tasks. For task \(\pi(i)\) (\(i=1,2,\ldots,n\)), let: \begin{tabular}{l l l} \(C_{\pi(i)}\) & \(-\) & _be the completion time_ \\  & & of task execution, \\ \(T_{i}=\max\ \{0,C_{i}-d_{i}\}\) & \(-\) & _tardiness_, \\ \(f_{i}(C_{i})=w_{i}\cdot T_{i}\) & \(-\) & _tardiness cost_. \\ \end{tabular}   
In the considered problem there should be determined the order in which the tasks will be performed (permutation \(\pi\in\Phi\)) by machine, minimizing _sum of tardiness costs_, i.e., sum  
\[\mathcal{F}(\pi)=\sum_{i=1}^{n}f_{\pi(i)}(C_{\pi(i)})=\sum_{i=1}^{n}w_{\pi(i) }T_{\pi(i)}. \tag{1}\]  
The problem of minimizing the cost of tardiness is \(N\!P\)-hard ([PERSON] [23] and [PERSON] et al. [22]). There were many papers published devoted to researching this problem. [PERSON] [24] introduced a partial order relationship on a set of tasks, thus limiting the process of searching the optimal solutions to some subset of the set of solutions. These properties are used in the best metaheuristic algorithms. Optimal algorithms (based on the dynamic programming method or branch and bound) were published by: [PERSON] et al. [25], [PERSON] [26] oraz [PERSON] [1]. Some of them were presented in the review of [PERSON] et al. [27]. They are, however not very useful in solving most examples found in practice, because the calculation time increases exponentially relatively to the number of tasks. Hence, in a reasonable time one can solve only examples with the number of tasks not exceeding 50 tasks (80 with the use of parallel algorithm [1]). There is extensive literature devoted to algorithms determining approximate solutions within acceptable time. Methods, on which the constructions of these algorithms are based, can be divided into the class of construction and correction style method. Construction algorithms usually have low computational complexity. However, designated solutions may differ significantly (even by several hundred percent) from optimal ones.