# Elimination Properties for a Probabilistic Scheduling Problem
## 5 Tasks Execution Times with Normal Distribution  
We now consider the probabilistic Total Weighted Tardiness Problem PTWT. In order to simplify the notation, it was assumed that the order of execution of tasks is a natural permutation, i.e., \(\pi=(1,2,\ldots,n)\). Let \((\hat{p}_{i},w_{i},d_{i})\) (\(i\in\mathcal{J}\)) be an example of the problem data, where \(\hat{p}_{i}\sim N(m_{i},s_{i})\) are random variables with normal distribution, and \(w_{i}\) and \(d_{i}\) are certain numbers. Using [PERSON]'s notation, this problem can be symbolically presented as \(1|\tilde{p}_{i}\sim N(m_{i},s_{i})|\sum w_{i}T_{i}\). When determining the value of the criterion function (6) of the PTWT problem, one must compute the expected tardiness value \(\tilde{T}_{i}\), i.e., \(E(\tilde{T}_{i})\). First, we present some facts concerning distributions of random variables. If task execution times are independent random variables with normal distribution \(\hat{p}_{i}\sim N(m_{i},s_{i})\)\(i\in\mathcal{J}\), the dates of completing tasks are also random variables with normal distribution \(\tilde{C}_{i}\sim N(\mu_{i},\sigma_{i})\), where  
\[\mu_{i}=\sum_{j=1}^{i}m_{j}\ \ \text{and}\ \ \sigma_{i}=\sqrt{\sum_{j=1}^{i}s_{j}^{2}}. \tag{14}\]  
In this case, tardiness is a random variable defined as follows:  
\[\tilde{T}_{i}=\left\{ \begin{array}{ll}\tilde{C}_{i}-d_{i},&\text{if}\ \ \tilde{C}_{i}>d_{i},\\ 0,&\text{if}\ \ \tilde{C}_{i}\leq d_{i}.\end{array} \right.\]  
**Lemma 4**: _Cumulative distribution \(\tilde{F}_{\tilde{T}_{i}}\) of distribution of random variable \(\tilde{T}_{i}\) is expressed by the formula:_  
\[F_{\tilde{T}_{i}}(x)=\left\{ \begin{array}{ll}0,&x\leq 0,\\ F_{\tilde{C}_{i}}(d_{i}+x)-F_{\tilde{C}_{i}}(d_{i}+x)F_{\tilde{C}_{i}}(d_{i})+F_ {\tilde{C}_{i}}(d_{i}),&x>0,\end{array} \right.\]  
**Proof. ** Using the definition of the random variable \(\tilde{T}_{i}\) we consider two cases. 1. \(x>0\). Then  
\[F_{\tilde{T}_{i}}(x)=P(\tilde{T}_{i}<x)=\]  
\[P(\tilde{T}_{i}<x|\tilde{C}_{i}-d_{i}>0)P(\tilde{C}_{i}-d_{i}>0)+\]  
\[P(\tilde{T}_{i}<x|\tilde{C}_{i}-d_{i}\leq 0)P(\tilde{C}_{i}-d_{i}\leq 0).\]  
We can see two facts:  
\[P(\tilde{T}_{i}<x|\tilde{C}_{i}-d_{i}\leq 0)=1\]  
and  
\[P(\tilde{T}_{i}<x|\tilde{C}_{i}-d_{i}>0)=P(\tilde{C}_{i}-d_{i}<x).\]  
Next we have:  
\[F_{\tilde{T}_{i}}(x)=P(\tilde{C}_{i}-d_{i}<x)P(\tilde{C}_{i}-d_{i}>0)+P(\tilde {C}_{i}-d_{i}\leq 0)=\]  
\[P(\tilde{C}_{i}<d_{i}+x)P(\tilde{C}_{i}>d_{i})+P(\tilde{C}_{i}\leq d_{i})=\]  
\[F_{\tilde{C}_{i}}(d_{i}+x)(1-F_{\tilde{C}_{i}}(d_{i}))+F_{\tilde{C}_{i}}(d_{i})=\]  
\[F_{\tilde{C}_{i}}(d_{i}+x)-F_{\tilde{C}_{i}}(d_{i}+x)F_{\tilde{C}_{i}}(d_{i})+ F_{\tilde{C}_{i}}(d_{i}).\]  
2. \(x<0\). It is obvious that \(F_{\tilde{T}_{i}}(x)=0\). In order to calculate the density function \(f_{\tilde{T}_{i}}(x)\) of random variable \(\tilde{T}\), it is enough to calculate the derivative of the cumulative distribution function \(F_{\tilde{T}_{i}}(x)\). Thus  
\[f_{\tilde{T}_{i}}(x)=\left\{ \begin{array}{ll}0,&\mbox{for $x\leq 0$,}\\ f_{\tilde{C}_{i}}(d_{i}+x)-F_{\tilde{C}_{i}}(d_{i})f_{\tilde{C}_{i}}(d_{i}+x),& \mbox{for $x>0$.}\end{array} \right.\]  
Using the above lemma we will prove the theorem enabling the calculation of the expected value of the random variable \(\tilde{T}_{i}\). **Theorem 3. **_Expected value of the random variable \(\tilde{T}_{i}\)_  
\[E(\tilde{T}_{i})=(1-F_{\tilde{C}_{i}}(d_{i}))\left(\frac{\sigma}{\sqrt{2\pi}}e ^{\frac{-(d_{i}-\mu_{i})^{2}}{2\mu_{i}^{2}}}+\right.\]  
\[(\mu_{i}-d_{i})\left(1-F_{N(0,1)}(\frac{d_{i}-\mu_{i}}{\sigma_{i}})\right) \right).\]  
**Proof.