# Two-Machine Job-Shop Scheduling Problem to Minimize the Makespan with Uncertain Job Durations
## 4 A Literature Review and Closed Results
### Uncertain Shop-Scheduling Problems  
The stability approach was proposed in Reference [17] and developed in Reference [18; 29; 30; 31] for the \(C_{max}\) criterion, and in References [19; 32; 33; 34; 35] for the total completion time criterion \(\sum C_{i}:=\min_{s\in S}\sum_{l_{i}\in\mathcal{J}}C_{i}(s)\). The stability approach combines a stability analysis of the optimal schedules, a multi-stage decision framework, and the solution concept of a minimal dominant set \(S(T)\) of schedules, which optimally covers all possible scenarios. The main aim of the stability approach is to construct a schedule which remains optimal for most scenarios of the set \(T\). The minimality of the dominant set \(S(T)\) is useful for the two-phase scheduling described in Reference [36]. At the off-line phase, one can construct set \(S(T)\), which enables a scheduler to make a quick scheduling decision at the on-line phase whenever additional local information becomes available. The knowledge of the minimal dominant set \(S(T)\) enables a scheduler to execute best a schedule and may end up executing a schedule optimally in many cases of the problem \(F2|l_{ij}\leq p_{ij}\leq u_{ij}|C_{max}\)[36]. In Reference [17], a formula for calculating the _stability radius_ of an optimal schedule is proven, i.e., the largest value of independent variations of the job durations in a schedule such that this schedule remains optimal. In Reference [19], a stability analysis of a schedule minimizing the total completion time was exploited in the branch-and-bound method for solving the job-shop problem \(Jm|l_{ij}\leq p_{ij}\leq u_{ij}|\sum C_{i}\) with \(m\) machines. In Reference [29], for the two-machine flow-shop problem \(F2|l_{ij}\leq p_{ij}\leq u_{ij}|C_{max}\), sufficient conditions have been identified when the transposition of two jobs minimizes the makespan. Reference [37] addresses the total completion time objective in the flow-shop problem with uncertain durations of the jobs. A geometrical algorithm has been developed for solving the flow-shop problem \(Fm|l_{ij}\leq p_{ij}\leq u_{ij},n=2|\sum C_{i}\) with \(m\) machines and two jobs. For this problem with two or three machines, sufficient conditions are determined such that the transposition of two jobs minimizes \(\sum C_{i}\). Reference [38] is devoted to the case of separate setup times with the criterion of minimizing the makespan or total completion time. The job durations are fixed while each setup time is relaxed to be a distribution-free random variable within the given lower and upper bounds. Local and global dominance relations have been determined for the flow-shop problem with two machines. Since, for the problem \(F2|l_{ij}\leq p_{ij}\leq u_{ij}|C_{max}\) there often does not exist a single permutation of \(n\) jobs \(\mathcal{J}=\mathcal{J}_{1,2}\) which remains optimal for all possible scenarios, an additional criterion may be introduced for dealing with uncertain scheduling problems. In Reference [39], a robust solution minimizing the worst-case deviation from optimality was proposed to hedge against uncertainties. While the deterministic problem \(F2||C_{max}\) is polynomially solvable (the optimal Johnson's permutation may be constructed for the problem \(F2||C_{max}\) in \(O(n\log n)\) time), finding a job permutation minimizing the worst-case regret for the uncertain counterpart with a finite set of possible scenarios is NP hard. In Reference [40], a binary NP hardness has been proven for finding a pair \((\pi_{k},\pi_{k})\in S\) of identical job permutations that minimizes the worst-case absolute regret for the uncertain two-machine flow-shop problem with the criterion \(C_{max}\) even for two possible scenarios. Minimizing the worst-case regret implies a time-consuming search over the set of \(n!\) job permutations. In order to overcome this computational complexity in some cases, it is useful to consider a minimal dominant set of schedules \(S(T)\) instead of the whole set \(S\).