# Elimination Properties for a Probabilistic Scheduling Problem
## 3 Random Task Execution Times  
In the literature we can find many ways in which uncertainty is modeled. First, we can distinguish proactive and reactive approaches where the former assumes that all preparations for handling uncertainty are completed before the algorithm starts its execution, while the latter assumes the opposite, i.e., uncertainty needs to be handled during the actual algorithm execution. Of course, we can also find many types of combination of those two. Moreover, we can also distinguish an online approach where the problem instance is not known in advance. Next, uncertainty can be modeled in different ways and even though there are several descriptions in the field, we can distinguish 3 main categories: probabilistic (or stochastic), where random variables are involved, and a fuzzy description and bound form where fixed ranges are involved. Sometimes by stochastic the authors refer to certain types of online algorithms and solutions in the bound form are sometimes referred to as robust, by fixed ranges we can introduce the guarantee on the upper or bottom bound of the provided solutions (however, in general the robustness description is not limited to the bound form). Having the above, in this paper we investigate the proactive version of the problem with uncertainty modeled by a probability approach with random variables; that is, in this section, we consider the probabilistic version of the aforementioned single-machine Total Weighted Tardiness Problem and we assume that the times of completing the tasks are independent random variables. They are most often described in the literature as scheduling problems with uncertain parameters. In practice, there are great difficulties in establishing the probability distribution of random parameters. Especially when we are dealing with unique processes, therefore, there is no representative statistical data. An extensive review of methods and algorithms for solving the problems of combinatorial optimization with random parameters was presented by [PERSON] in monograph [7] and in the more recent work by [PERSON] et al. [31]. Some practical problems are also considered in the works of [PERSON] et al. [20; 32; 33; 34]. The last of these works concerns the implementation of construction projects under uncertainty. We will now introduce the necessary definitions and designations. If \(X\) is a continuous random variable, we will use the following designations later in this work:  
\(F_{X}\)--cumulative distribution function of random variable \(X\);  
\(f_{X}\)--density function of random variable \(X\);  
\(E(X)\)--expected value of random variable \(X\). We are considering, as described in Section 2, a probabilistic version of the TWT problem, in which the task execution times \(\hat{p}_{i}\) are independent random variables, and the remaining task parameters \(w_{i}\) and \(d_{i}\) (\(i=1,2,\ldots,n\)) are deterministic. This problem will be denoted in short by PTWT. If task execution times \(\hat{p}_{i}\) are random variables, then for any order of execution of tasks \(\pi\in\Phi\), the completion of the task \(\pi(k)\)  
\[\tilde{C}_{\pi(k)}=\hat{p}_{\pi(1)}+\hat{p}_{\pi(2)}+,\ldots,+\hat{p}_{\pi(k)},\]  
tardiness \(\tilde{T}_{\pi(k)}=\max\{0,\tilde{C}_{\pi(k)}-d_{\pi(k)}\}\) (Equivalent (2)) and criterion function (Equivalent (3))  
\[\tilde{\mathcal{F}}(\pi)=\sum_{i=1}^{n}w_{\pi(i)}\tilde{T}_{\pi(i)}. \tag{5}\]  
are also random variables. In algorithms for solving optimization problems, it is necessary to compare the values of the criterion function for various acceptable solutions (e.g., permutations). In a case when this function is a random variable (5) we will be using its expected value. Therefore, as comparative criteria of solutions the following function will be used:  
\[\mathcal{L}(\pi)=E(\tilde{\mathcal{F}}(\pi))=\sum_{i=1}^{n}w_{\pi(i)}E(\tilde{ T}_{\pi(i)}). \tag{6}\]  
By  
\[f(\pi(k))=w_{\pi(k)}E(\tilde{T}_{\pi(k)}) \tag{7}\]  
we designate the cost of execution of task \(\pi(k)\).