# Elimination Properties for a Probabilistic Scheduling Problem
## 2 Single-Machine Total Weighted Tardiness Tasks Scheduling Problem  
Tasks scheduling problems on a single machine with cost goal functions have a very long (over 50 years) history (the first work of [PERSON] et al. [19] appeared in 1975). However, despite the simplicity of formulation, they mostly belong to the class of strongly NP-hard problems. They are important both from the point of view of theory and practice. Such problems often constitute a significant part of more extensive production systems. Different variants of scheduling tasks on a single machine are still intensively tested and the results obtained are the inspiration for much more complex research of multi-machine problems. While describing of the problem considered in this section we will use some definitions, designations and properties presented in the following works: [PERSON] et al. [18; 20], [PERSON] and [PERSON] [16].  
A single-machine Total Weighted Tardiness Problem, abbreviated as TWT, will be defined as follows.  
**TWT Problem:** Let  
\[\mathcal{J}=\{1,2,\ldots,n\},\]  
be a set of tasks to be performed, without interruption, on the executing machine performing at a given moment at most one task at a time. For task \(i\in\mathcal{J}\) (\(i=1,\ldots,n\)) we define:  
\(p_{i}\)--execution time;  
\(w_{i}\)--penalty for tardiness;  
\(d_{i}\)--demanded completion time..  
Let \(\pi=(\pi(1),\pi(2),\ldots,\pi(n))\) be any permutation of elements from \(\mathcal{J}\), and \(\Phi\) a set of all such permutations. Then,  
\[C_{\pi(i)}=\sum_{j=1}^{i}p_{\pi(j)} \tag{1}\]  
is a moment of completion of task \(\pi(i)\in\mathcal{J}\), executed as \(i\)-th in a sequence. If \(C_{\pi(i)}\leq d_{\pi(i)}\), then the task is called an early one, otherwise a tardy one.  
Tardiness of task  
\[T_{\pi(i)}=\max\{0,C_{\pi(i)}-d_{\pi(i)}\}, \tag{2}\]and cost of its execution \(f(\pi(i))=w_{\pi(i)}T_{\pi(i)}\). By  
\[\mathcal{F}(\pi)=\sum_{i=1}^{n}w_{\pi(i)}T_{\pi(i)} \tag{3}\]  
we designate cost of execution of all tasks (weight of permutation \(\pi\)).  
The problem under consideration (which will be also called a deterministic) problem involves determining permutation \(\pi^{*}\in\Phi\) with the smallest weight, such that  
\[\mathcal{F}(\pi^{*})=\min\{\mathcal{F}(\pi):\ \pi\in\Phi\}. \tag{4}\]  
In the literature, this problem is denoted by \(1||\sum w_{i}T_{i}\) and belongs to the strongly NP-hard class of problems. Optimal algorithms for solving it based on the dynamic programming method were presented by [PERSON], [PERSON] [21], [PERSON] [22], those based on the branch and bound method were presented by [PERSON], [PERSON] [23] [PERSON], [PERSON] [24], [PERSON] [25] and [PERSON] [26]. They enable the effective determination of optimal solutions for examples whose number of tasks does not exceed 80. Due to the time-consuming characteristic of exact algorithms, in practice, approximate algorithms (mainly metaheuristics) are usually applied.  
In the best metaheuristic algorithms, where the task is solving multi-machine task scheduling problems, so-called 'block elimination properties' are used (e.g., for flow shop problems such algorithms are presented in the works of [PERSON] and [PERSON] [27] and [PERSON] and [PERSON] [28]). Blocks enable both the reduction of calculation time, as well as improvement of the values determined by the algorithm solutions. For the single-machine Total Weighted Tardiness Problem TWT presented in this section, in the works of [PERSON] [29], [PERSON] [26; 30] there were two types of blocks presented: the so-called early and tardy blocks, which were successfully used in tabu search algorithms.