## 2 Problem Setting and the Related Results  
There are given \(n\) jobs \(\mathcal{J}=\{J_{1},J_{2},...,J_{n}\}\) to be processed on a single machine. The processing time \(p_{i}\) of the job \(J_{i}\in\mathcal{J}\) can take any real value from the given segment \([p_{i}^{L},p_{i}^{U}]\), where \(p_{i}^{U}\geq p_{i}^{L}>0\). The exact value \(p_{i}\in[p_{i}^{L},p_{i}^{U}]\) of the job processing time remains unknown until completing the job \(J_{i}\in\mathcal{J}\). Let \(R_{+}^{n}\) denote a set of all non-negative \(n\)-dimensional real vectors. The set of all possible vectors \((p_{1},p_{2},\ldots,p_{n})=p\in R_{+}^{n}\) of the job processing times is presented as the Cartesian product of the segments \([p_{i}^{L},p_{i}^{U}]\): \(T=\{p\in R_{+}^{n}\,:\,p_{i}^{L}\leq p_{i}\leq p_{i}^{U},\,i\in\{1,2,\ldots,n\}\}=[p_{1 }^{L},p_{1}^{U}]\times[p_{2}^{L},p_{2}^{U}]\times\ldots\times[p_{n}^{L},p_{n}^{U }]=:\times_{i=1}^{n}[p_{1}^{L},p_{1}^{U}]\). Each vector \(p\in T\) is called a **scenario**. Let \(S=\{\pi_{1},\pi_{2},\ldots,\pi_{n1}\}\) be a set of all permutations \(\pi_{k}=(J_{k_{1}},J_{k_{2}},\ldots,J_{k_{n}})\) of the jobs \(\mathcal{J}\). Given a scenario \(p\in T\) and a permutation \(\pi_{k}\in S\), let \(C_{i}=C_{i}(\pi_{k},p)\) denote the completion time of the job \(J_{i}\in\mathcal{J}\) in the schedule determined by the permutation \(\pi_{k}\). The criterion \(\sum C_{i}\) denotes the minimization of the sum of job completion times: \(\sum_{j\in\mathcal{J}}C_{i}(\pi_{t},p)=\min_{\pi_{k}\in S}\left\{\sum_{j\in \mathcal{J}}C_{i}(\pi_{k},p)\right\},\) where the permutation \(\pi_{t}=(J_{t_{1}},J_{t_{2}},\ldots,J_{t_{n}})\in S\) is optimal for the criterion \(\sum C_{i}\). This problem is denoted as \(1|p_{i}^{L}\leq p_{i}\leq p_{i}^{U}|\sum C_{i}\) using the three-field notation \(\alpha|\beta|\gamma\)[13], where \(\gamma\) denotes the objective function. If scenario \(p\in T\) is fixed before scheduling, i.e., \([p_{i}^{L},p_{i}^{U}]=[p_{i},p_{i}]\) for each job \(J_{i}\in\mathcal{J}\), then the uncertain problem \(1|p_{i}^{L}\leq p_{i}\leq p_{i}^{U}|\sum C_{i}\) is turned into the deterministic one \(1||\sum C_{i}\). We use the notation \(1|p|\sum C_{i}\) to indicate an instance of the problem \(1||\sum C_{i}\) with the fixed scenario \(p\in T\). Any instance \(1|p|\sum C_{i}\) is solvable in \(O(n\log n)\) time [14] since the following claim has been proven. **Theorem 1**. : _The job permutation \(\pi_{k}=(J_{k_{1}},J_{k_{2}},\ldots,J_{k_{n}})\in S\) is optimal for the instance \(1|p|\sum C_{i}\) if and only if the following inequalities hold: \(p_{k_{1}}\leq p_{k_{2}}\leq\ldots\leq p_{k_{n}}\). If \(p_{k_{n}}<p_{k_{n}}\), then job \(J_{k_{n}}\) precedes job \(J_{k_{n}}\) in any optimal permutation \(\pi_{k}\)._  
Since a scenario \(p\in T\) is not fixed for the uncertain problem \(1|p_{i}^{L}\leq p_{i}\leq p_{i}^{U}|\sum C_{i}\), the completion time \(C_{i}\) of the job \(J_{i}\in\mathcal{J}\) cannot be exactly determined for the permutation \(\pi_{k}\in S\) before the completion of the job \(J_{i}\). Therefore, the value of the objective function \(\sum C_{i}\) for the permutation \(\pi_{k}\) remains uncertain until jobs \(\mathcal{J}\) have been completed. **Definition 1**. : _Job \(J_{v}\) dominates job \(J_{w}\) (with respect to \(T\)) if there is no optimal permutation \(\pi_{k}\in S\) for the instance \(1|p|\sum C_{i}\), \(p\in T\), such that job \(J_{w}\) precedes job \(J_{v}\)._  
The following criterion for the domination was proven in [15]. **Theorem 2**. : _Job \(J_{v}\) dominates job \(J_{w}\) if and only if \(p_{v}^{U}<p_{w}^{L}\)._  
Since for the problem \(\alpha|p_{i}^{L}\leq p_{i}\leq p_{i}^{U}|\gamma\), there does not usually exist a permutation of the jobs \(\mathcal{J}\) being optimal for all scenarios \(T\), additional objectives or agreements are often used in the literature. In particular, a robust schedule minimizing the worst-case regret to hedge against data uncertainty has been developed in [3; 8; 16; 17; 18; 19; 20].