# Elimination Properties for a Probabilistic Scheduling Problem
## 8 Summary  
The paper presents a certain method representing uncertain data in discrete optimization problems, using independent random variables of normal distribution. This distribution is in practice widely used for solving many non-deterministic decision problems. Consideration of uncertain data leads to great difficulty in terms of the calculations of practical optimization problems which, however, significantly better describe reality than deterministic models. \begin{table}
\begin{tabular}{c c c c c c} \hline \hline \multirow{2}{*}{**Instance Group**} & \multicolumn{2}{c}{\(c=0.5\)} & \multicolumn{2}{c}{\(c=0.1\)} & \multicolumn{2}{c}{\(c=0.2\)} \\ \cline{2-7}  & \(TS_{\mathcal{P}}\) & \(TS_{\mathcal{P+B}}\) & \(TS_{\mathcal{P}}\) & \(TS_{\mathcal{P+B}}\) & \(TS_{\mathcal{P}}\) & \(TS_{\mathcal{P+B}}\) \\ \hline
000–025 & 0.0028 & \(\mathbf{-0.0040}\) & 0.0199 & \(\mathbf{0.0157}\) & 0.0855 & \(\mathbf{0.0761}\) \\
026–050 & 15.0490 & \(\mathbf{5.3410}\) & 0.0482 & \(\mathbf{0.0478}\) & 0.3703 & \(\mathbf{0.3258}\) \\
050–075 & 0.0131 & \(\mathbf{-0.0017}\) & 0.0282 & \(\mathbf{0.0122}\) & 19.6031 & \(\mathbf{17.7367}\) \\
076–100 & 0.0642 & \(\mathbf{-0.0294}\) & 0.8347 & \(\mathbf{0.7095}\) & \(\mathbf{0.3933}\) & 0.4549 \\
101–125 & 0.0596 & \(\mathbf{0.0345}\) & \(\mathbf{0.3063}\) & 0.3850 & 1.1980 & \(\mathbf{1.0438}\) \\ \hline Average & 3.0377 & \(\mathbf{1.0681}\) & 0.2475 & \(\mathbf{0.2341}\) & 4.3300 & \(\mathbf{3.9275}\) \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Computational results \(\mathcal{S}(A,\hat{\mathcal{P}})\) for the \(wt100\) instance group. \begin{table}
\begin{tabular}{c c c c c c c} \hline \hline \multirow{2}{*}{**Instance Group**} & \multicolumn{2}{c}{\(c=0.5\)} & \multicolumn{2}{c}{\(c=0.1\)} & \multicolumn{2}{c}{\(c=0.2\)} \\ \cline{2-7}  & \(TS_{\mathcal{P}}\) & \(TS_{\mathcal{P+B}}\) & \(TS_{\mathcal{P}}\) & \(TS_{\mathcal{P+B}}\) & \(TS_{\mathcal{P}}\) & \(TS_{\mathcal{P+B}}\) \\ \hline
000–025 & 0.0049 & \(\mathbf{-0.0070}\) & 0.0263 & \(\mathbf{0.0169}\) & \(\mathbf{0.0826}\) & 0.0862 \\
026–050 & \(\mathbf{0.0148}\) & 0.2466 & \(\mathbf{0.1426}\) & 0.1878 & 0.3270 & \(\mathbf{0.1983}\) \\
050–075 & 0.0146 & \(\mathbf{-0.0064}\) & 0.0595 & \(\mathbf{0.0078}\) & 0.2674 & \(\mathbf{0.1840}\) \\
076–100 & 0.0054 & \(\mathbf{-0.0256}\) & 0.0077 & \(\mathbf{-0.0037}\) & 0.1847 & \(\mathbf{0.1720}\) \\
101–125 & \(\mathbf{0.0138}\) & 0.0217 & 0.0277 & \(\mathbf{0.0265}\) & 0.6870 & \(\mathbf{0.6292}\) \\ \hline Average & \(\mathbf{0.0107}\) & 0.0459 & 0.0528 & \(\mathbf{0.0471}\) & 0.3097 & \(\mathbf{0.2540}\) \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Computational results \(\mathcal{S}(A,\hat{\mathcal{P}})\) for the \(wt50\) instance group. Also presented is the construction of the algorithm based on the tabu search method for the problem of scheduling tasks on a single machine with minimization of the sum of penalties for tasks not completed on time. Random execution times tasks are represented by independent random variables of normal distribution. Since the objective function is a random variable, thus, when choosing an element from the neighborhood as a comparative criterion the expected value was assumed. To accelerate the calculation, blocks are used, i.e., certain specific methods of an intermediate review of solutions for the problem under consideration. Computational experiments were conducted out in order to test the stability of the algorithms, i.e., the impact of altering task parameters on changes in the value of a criterion function. The obtained results clearly indicate that probabilistic algorithms are much more stable, i.e., algorithms in which the randomness of parameters is taken into account. The use of blocks significantly accelerated the calculations and greatly improved the stability of the algorithm. The described methods and algorithms can be directly applied to other probability distributions and also other task parameters (not only execution times).