# Two-Machine Job-Shop Scheduling Problem to Minimize the Makespan with Uncertain Job Durations
## 2 Contributions and New Results  
We study the two-machine job-shop scheduling problem with uncertain job durations and address the issue of how to best execute a schedule if each duration may take any value from the given segment. The main aim is to determine a minimal dominant set of schedules (DS) that would contain at least one optimal schedule for each feasible scenario of the distribution of durations of the jobs.  
It is shown how an uncertain two-machine job-shop problem may be decomposed into two uncertain two-machine flow-shop problems. We prove several sufficient conditions for the existence of a small dominant set of schedules. In particular, the sufficient and necessary conditions are proven for the existence of a single pair of job permutations, which is optimal for the two-machine job-shop problem with any possible scenario. We investigated properties of the optimal pairs of job permutations for the uncertain two-machine job-shop problem.  
In the stability approach, scheduling decisions may consist of two phases: an off-line phase and an on-line phase. Using information on the lower and upper bounds on each job duration available at the off-line phase, a scheduler can determine a small (or minimal) dominant set of schedules based on sufficient conditions for schedule dominance. The DS optimally covers all scenarios in the sense that, for each possible scenario, there exists at least one schedule in the DS that is optimal. The DS enables a scheduler to quickly make an on-line scheduling decision whenever additional information on completing some jobs becomes available. The stability approach enables a scheduler to choose a schedule, which is optimal for the most possible scenarios.  
In this paper, we develop algorithms for testing a set of conditions for a schedule dominance. The developed algorithms are polynomial in the number of jobs. Their asymptotic complexities do not exceed \(O(n^{2})\), where \(n\) is a number of the jobs. Computational experiments have shown effectiveness of the developed algorithms: if there were no more than 600 jobs, then all 1000 instances in each tested series were solved in no more than one second. For the tested series of instances with 10,000 jobs, all 1000 instances of a series were solved in 344 seconds at most (on average, 0.4 s per one instance).  
The paper is organized as follows. In Section 3, we present settings of the uncertain scheduling problems. The related literature and closed results are discussed in Section 4. In Section 4.2, we describe in detail the results published for the uncertain two-machine flow-shop problem. These results are used in Section 5, where we investigate properties of the optimal job permutations used for processing a set of the given jobs. Some proofs of the claims are given in Appendix A. In Section 6, we develop algorithms for constructing optimal schedules if the proven dominance conditions hold. In Section 7, we report on the wide computational experiments for solving a lot of randomly generated instances. Tables with the obtained computational results are presented in Appendix B. The paper is concluded in Section 8, where several directions for further researches are outlined.