# Two-Machine Job-Shop Scheduling Problem to Minimize the Makespan with Uncertain Job Durations
## 8 Concluding Remarks and Future Works  
The uncertain flow-shop scheduling problem \(F2|l_{ij}\leq p_{ij}\leq u_{ij}|C_{max}\) and its generalization the job-shop problem \(J2|l_{ij}\leq p_{ij}\leq u_{ij},n_{i}\leq 2|C_{max}\) attract the attention of researchers since these problems are applicable in many real-life scheduling systems. The optimal scheduling decisions for these problems allow the plant to reduce the costs of productions due to a better utilization of the available machines and other resources. In Section 5, we proved several properties of the optimal pairs \((\pi^{\prime},\pi^{\prime\prime})\) of job permutations (Theorems 7-12). Using these properties, we derived Algorithms 1-4 for constructing optimal pairs \((\pi^{\prime},\pi^{\prime\prime})\) of job permutations or a small dominant set of schedules for the problem \(J2|l_{ij}\leq p_{ij}\leq u_{ij},n_{i}\leq 2|C_{max}\). If it is impossible to construct a single pair \((\pi^{\prime},\pi^{\prime\prime})\) of job permutations, which dominates all other pairs of job permutations for all possible scenarios \(T\), then Algorithm 2 determines the partial strict order \(A_{\prec}^{1,2}\) on the job set \(\mathcal{J}_{1,2}\) (Algorithm 3) and the partial strict order \(A_{\prec}^{2,1}\) on the job set \(\mathcal{J}_{2,1}\) (Algorithm 4). The precedence digraphs \((\mathcal{J}_{1,2},A_{\prec}^{1,2})\) and \((\mathcal{J}_{2,1},A_{\prec}^{2,1})\) determine a minimal dominant set of schedules for the problem \(J2|l_{ij}\leq p_{ij}\leq u_{ij},n_{i}\leq 2|C_{max}\). From the conducted extensive computational experiments, it follows that pairs of job permutations constructed using Algorithm 2 are close to the optimal pairs of job permutations, which may be determined after completing all jobs \(\mathcal{J}\) when factual operation durations become known. We tested 15 classes of the randomly generated instances \(J2|l_{ij}\leq p_{ij}\leq u_{ij},n_{i}\leq 2|C_{max}\). Most instances from tested classes 1-9 were optimally solved at the off-line phase of scheduling. If the values of \(\delta\) were no greater than 20%, i.e., \(\delta\in\{5\%,10\%,15\%,20\%\}\), then more than 80% of the tested instances was optimally solved in spite of the uncertainty of the input data. If \(\delta=50\%\), then 45% of the tested instances was optimally solved. However, less than 5% of the instances with \(\delta\geq 20\%\) from hard classes 10-15 were optimally solved at the off-line phase of scheduling (Figure 2). There were no tested hard instances optimally solved for the value \(\delta=50\%\). In future research, the on-line phase of scheduling will be studied for the problem \(J2|l_{ij}\leq p_{ij}\leq u_{ij},n_{i}\leq 2|C_{max}\). To this end, it will be useful to find sufficient conditions for existing a dominant pair of job permutations at the on-line phase of scheduling. The additional information on the factual value of the job duration becomes available once the processing of the job on the corresponding machine is completed. Using this additional information, a scheduler can determine a smaller dominant set DS of schedules, which is based on sufficient conditions for schedule dominance. The smaller DS enables a scheduler to quickly make an on-line scheduling decision whenever additional information on processing the job becomes available. To solve the problem \(J2|l_{ij}\leq p_{ij}\leq u_{ij},n_{i}\leq 2|C_{max}\) at the  
Figure 4: Average percentages of the correct decisions made for constructing permutations of the conflict jobs for the hard instances presented in Tables 10-15.  
on-line phase, a scheduler needs to use fast (better polynomial) algorithms. The investigation of the on-line phase of scheduling for the uncertain job-shop problem is under development.