Two-Machine Job-Shop Scheduling Problem to Minimize the Makespan with Uncertain Job Durations

Abstract

We study two-machine shop-scheduling problems provided that lower and upper bounds on durations of n jobs are given before scheduling. An exact value of the job duration remains unknown until completing the job. The objective is to minimize the makespan (schedule length). We address the issue of how to best execute a schedule if the job duration may take any real value from the given segment. Scheduling decisions may consist of two phases: an off-line phase and an on-line phase. Using information on the lower and upper bounds for each job duration available at the off-line phase, a scheduler can determine a minimal dominant set of schedules (DS) based on sufficient conditions for schedule domination. The DS optimally covers all possible realizations (scenarios) of the uncertain job durations in the sense that, for each possible scenario, there exists at least one schedule in the DS which is optimal. The DS enables a scheduler to quickly make an on-line scheduling decision whenever additional information on completing jobs is available. A scheduler can choose a schedule which is optimal for the most possible scenarios. We developed algorithms for testing a set of conditions for a schedule dominance. These algorithms are polynomial in the number of jobs. Their time complexity does not exceed $O\left(n^2\right)$. Computational experiments have shown the effectiveness of the developed algorithms. If there were no more than 600 jobs, then all 1000 instances in each tested series were solved in one second at most. An instance with 10,000 jobs was solved in 0.4 s on average. The most instances from nine tested classes were optimally solved. If the maximum relative error of the job duration was not greater than $20\%$, then more than $80\%$ of the tested instances were optimally solved. If the maximum relative error was equal to $50\%$, then $45\%$ of the tested instances from the nine classes were optimally solved.

1. Introduction

A lot of real-life scheduling problems involve different forms of uncertainties. For dealing with uncertain scheduling problems, several approaches have been developed in the literature. A stochastic approach assumes that durations of the jobs are random variables with specific probability distributions known before scheduling. There are two types of stochastic scheduling problems [1], where one is on stochastic jobs and another is on stochastic machines. In the stochastic job problem, each job duration is assumed to be a random variable following a certain probability distribution. With an objective of minimizing the expected makespan, the flow-shop problem was considered in References [2,3,4]. In the stochastic machine problem, each job duration is a constant, while each completion time of the job is a random variable due to the machine breakdown or nonavailability. In References [5,6,7], flow-shop problems to stochastically minimize the makespan or total completion time have been considered.

If there is no information to determine a probability distribution for each random duration of the job, other approaches have to be used [8,9,10]. In the approach of seeking a robust schedule [8,11,12,13], a decision maker prefers a schedule that hedges against the worst-case scenario. A fuzzy approach [14,15,16] allows a scheduler to find best schedules with respect to fuzzy durations of the jobs. A stability approach [17,18,19,20] is based on the stability analysis of optimal schedules to possible variations of the durations. In this paper, we apply the stability approach to the two-machine job-shop scheduling problem with given segments of job durations. We have to emphasize that uncertainties of the job durations considered in this paper are due to external forces in contrast to scheduling problems with controllable durations [21,22,23], where the objective is to determine optimal durations (which are under the control of a decision maker) and to find an optimal schedule for the jobs with optimal 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\left(n^2\right)$, 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.

3. Problem Settings and Notations

Using the notation $\alpha \left|\beta \right|\gamma$ [24], the two-machine job-shop scheduling problem with minimizing the makespan is denoted as $J2|n_i\le 2|C_{max}$, where $\alpha =J2$ denotes a job-shop system with two available machines, $n_i$ is the number of stages for processing a job, and $\gamma =C_{max}$ denotes the criterion of minimizing the makespan. In the problem $J2|n_i\le 2|C_{max}$, the set $\mathcal{J}=\{J_1,J_2,\dots ,J_n\}$ of the given jobs have to be processed on machines from the set $\mathcal{M}=\{M_1,M_2\}$. All jobs are available for processing from the initial time $t=0$. Let $O_{ij}$ denote an operation of the job $J_i\in \mathcal{J}$ processed on machine $M_j\in \mathcal{M}$. Each machine can process a job $J_i\in \mathcal{J}$ no more than once provided that preemption of each operation $O_{ij}$ is not allowed. Each job $J_i\in \mathcal{J}$ has its own processing order (machine route) on the machines in $\mathcal{M}$.

Let ${\mathcal{J}}_{1,2}$ denote a subset of the set $\mathcal{J}$ of the jobs with the same machine route ($M_1,M_2$), i.e., each job $J_i\in {\mathcal{J}}_{1,2}$ has to be processed first on machine $M_1$ and then on machine $M_2$. Let ${\mathcal{J}}_{2,1}\subseteq \mathcal{J}$ denote a subset of the jobs with the opposite machine route ($M_2,M_1$). Let ${\mathcal{J}}_k\subseteq \mathcal{J}$ denote a set of the jobs, which has to be processed only on machine $M_k\in \mathcal{M}$. The partition $\mathcal{J}={\mathcal{J}}_1\bigcup {\mathcal{J}}_2\bigcup {\mathcal{J}}_{1,2}\bigcup {\mathcal{J}}_{2,1}$ holds. We denote $m_h=\left|{\mathcal{J}}_h\right|$, where $h\in \{1;2;1,2;2,1\}$.

We first assume that the duration $p_{ij}$ of each operation $O_{ij}$ is fixed before scheduling. The considered criterion $C_{max}$ is the minimization of the makespan (schedule length) as follows:

$$C_{max}:=\underset{s\in S}{min}{C}_{max}\left(s\right)=\underset{s\in S}{min}\{max\{C_i\left(s\right):J_i\in \mathcal{J}\}\},$$

where $C_i\left(s\right)$ denotes a completion time of the job $J_i\in \mathcal{J}$ in the schedule s and S denotes a set of semi-active schedules existing for the problem $J2|n_i\le 2|C_{max}$. A schedule is called semi-active if no job (operation) can be processed earlier without changing the processing order or violating some given constraints [1,25,26].

Jackson [27] proved that the problem $J2|n_i\le 2|C_{max}$ is polynomially solvable and that the optimal schedule for this problem may be determined as a pair $({\pi }^{\prime },{\pi }^{″})$ of the job permutations (calling it a Jackson’s pair of permutations) such that ${\pi }^{\prime }=({\pi }_{1,2},{\pi }_1,{\pi }_{2,1})$ is a sequence of all jobs from the set ${\mathcal{J}}_1\bigcup {\mathcal{J}}_{1,2}\bigcup {\mathcal{J}}_{2,1}$ processed on machine $M_1$ and ${\pi }^{″}=({\pi }_{2,1},{\pi }_2,{\pi }_{1,2})$ is a sequence of all jobs from the set ${\mathcal{J}}_2\bigcup {\mathcal{J}}_{1,2}\bigcup {\mathcal{J}}_{2,1}$ processed on machine $M_2$. Job $J_j$ belongs to the permutation ${\pi }_h$ if $J_j\in {\mathcal{J}}_h$.

In a Jackson’s pair $({\pi }^{\prime },{\pi }^{″})$ of the job permutations, the order for processing jobs from set ${\mathcal{J}}_1$ (from set ${\mathcal{J}}_2$, respectively) may be arbitrary, while for the permutation ${\pi }_{1,2}$, the following inequality holds for all indexes k and m, $1\le k<m\le m_{1,2}$:

$$min\{p_{i_{k}1},p_{i_{m}2}\}\le min\{p_{i_{m}1},p_{i_{k}2}\}$$

(1)

(for the permutation ${\pi }_{2,1}$, the following inequality holds for all indexes k and m, $1\le k<m\le m_{2,1}$) [28]:

$$min\{p_{j_{k}2},p_{j_{m}1}\}\le min\left\{p_{j_{m}2}{p}_{j_{k}1}\right\}$$

(2)

The aim of this paper is to investigate the uncertain two-machine job-shop scheduling problem. Therefore, we next assume that duration $p_{ij}$ of each operation $O_{ij}$ is unknown before scheduling; namely, in the realization of a schedule, a value of $p_{ij}$ may be equal to any real number no less than the given lower bound $l_{ij}$ and no greater than the given upper bound $u_{ij}$. Furthermore, it is assumed that probability distributions of random durations of the jobs are unknown before scheduling. Such a job-shop scheduling problem is denoted as $J2|l_{ij}\le p_{ij}\le u_{ij},n_i\le 2|C_{max}$. The problem $J2|l_{ij}\le p_{ij}\le u_{ij},n_i\le 2|C_{max}$ is called an uncertain scheduling problem in contrast to the deterministic scheduling problem $J2|n_i\le 2|C_{max}$. Let a set of all possible vectors $p=(p_{1,1},p_{1,2},\dots ,$$p_{n1},p_{n2})$ of the job durations be determined as follows: $T=\{p:l_{ij}\le p_{ij}\le u_{ij},J_i\in \mathcal{J},M_j\in \mathcal{M}\}.$ Such a vector $p=(p_{1,1},p_{1,2},\dots ,$$p_{n1},p_{n2})\in T$ of the possible durations of the jobs is called a scenario.

It should be noted that the problem $J2|l_{ij}\le p_{ij}\le u_{ij},n_i\le 2|C_{max}$ is mathematically incorrect. Indeed, in most cases, a single pair of job permutations which is optimal for all possible scenarios $p\in T$ for the uncertain problem $J2|l_{ij}\le p_{ij}\le u_{ij},n_i\le 2|C_{max}$ does not exist. Therefore, in the general case, one cannot find an optimal solution for this uncertain scheduling problem.

For a fixed scenario $p\in T$, the uncertain problem $J2|l_{ij}\le p_{ij}\le u_{ij},n_i\le 2|C_{max}$ turns into the deterministic problem $J2|n_i\le 2|C_{max}$ associated with scenario p. The latter deterministic problem is an individual one and we denote it as $J2|p,n_i\le 2|C_{max}$. For any fixed scenario $p\in T$, there exists a Jackson’s pair of the job permutations that is optimal for the individual deterministic problem $J2|p,n_i\le 2|C_{max}$ associated with scenario p.

Let $S_{1,2}$ denote a set of all permutations of $m_{1,2}$ jobs from the set ${\mathcal{J}}_{1,2}$, where $|S_{1,2}|=m_{1,2}!$. Let $S_{2,1}$ denote a set of all permutations of $m_{2,1}$ jobs from the set ${\mathcal{J}}_{2,1}$, where $|S_{2,1}|=m_{2,1}!.$ Let $S=<S_{1,2},S_{2,1}>$ be a subset of the Cartesian product $(S_{1,2},{\pi }_1,S_{2,1})\times (S_{2,1},{\pi }_2,S_{1,2})$ such that each element of the set S is a pair of job permutations $({\pi }^{\prime },{\pi }^{″})\in S$, where ${\pi }^{\prime }=({\pi }_{1,2}^i,{\pi }_1,{\pi }_{2,1}^j)$ and ${\pi }^{″}=({\pi }_{2,1}^j,{\pi }_2,{\pi }_{1,2}^i)$, $1\le i\le m_{1,2}!$, $1\le j\le m_{2,1}!$. The set S determines all semi-active schedules and vice versa.

Remark 1.

As an order for processing jobs from set ${\mathcal{J}}_1$ (from set ${\mathcal{J}}_2$) may be arbitrary in the Jackson’s pair of job permutations $({\pi }^{\prime },{\pi }^{″})$, in what follows, we fix both permutations ${\pi }_1$ and ${\pi }_2$ in the increasing order of the indexes of their jobs. Thus, both permutations ${\pi }_1$ and ${\pi }_2$ are now fixed, and so their upper indexes are omitted in each permutation from the pair $({\pi }^{\prime },{\pi }^{″})=(({\pi }_{1,2}^i,{\pi }_1,{\pi }_{2,1}^j),({\pi }_{2,1}^j,{\pi }_2,{\pi }_{1,2}^i))$.

Due to Remark 1, the equality $\left|S\right|=m_{1,2}!·m_{2,1}!$ holds. The following definition is used for a J-solution for the uncertain problem $J2|l_{ij}\le p_{ij}\le u_{ij},n_i\le 2|C_{max}$.

Definition 1.

A minimal (with respect to the inclusion) set of pairs of job permutations $S\left(T\right)\subseteq S$ is called a J-solution for the problem $J2|l_{ij}\le p_{ij}\le u_{ij},n_i\le 2|C_{max}$ with set $\mathcal{J}$ of the given jobs if, for each scenario $p\in T$, the set $S\left(T\right)$ contains at least one pair $({\pi }^{\prime },{\pi }^{″})\in S$ of the job permutations, which is optimal for the individual deterministic problem $J2|p,n_i\le 2|C_{max}$ associated with scenario p.

From Definition 1, it follows that, for any proper subset $S^{\prime }$ of the set $S\left(T\right)$$S^{\prime }\subset S\left(T\right)$, there exists at least one scenario $p^{\prime }\in T$ such that set $S^{\prime }$ does not contain an optimal pair of job permutations for the individual deterministic problem $J2|p^{\prime },n_i\le 2|C_{max}$ associated with scenario $p^{\prime }$, i.e., set $S\left(T\right)$ is a minimal (with respect to the inclusion) set possessing the property indicated in Definition 1.

The uncertain job-shop problem $J2|l_{ij}\le p_{ij}\le u_{ij},n_i\le 2|C_{max}$ is a generalization of the uncertain flow-shop problem $F2|l_{ij}\le p_{ij}\le u_{ij}|C_{max}$, where all jobs from the set $\mathcal{J}$ have the same machine route. Two flow-shop problems are associated with the individual job-shop problem $J2|l_{ij}\le p_{ij}\le u_{ij},n_i\le 2|C_{max}$. In one of these flow-shop problems, an optimal schedule for processing jobs ${\mathcal{J}}_{1,2}$ has to be determined, i.e., ${\mathcal{J}}_{2,1}={\mathcal{J}}_1={\mathcal{J}}_2=\varnothing$. In another flow-shop problem, an optimal schedule for processing jobs ${\mathcal{J}}_{2,1}$ has to be determined, i.e., ${\mathcal{J}}_{1,2}={\mathcal{J}}_1={\mathcal{J}}_2=\varnothing$. Thus, a solution of the problem $J2|l_{ij}\le p_{ij}\le u_{ij},n_i\le 2|C_{max}$ may be based on solutions of the two associated problems $F2|l_{ij}\le p_{ij}\le u_{ij}|C_{max}$ with job set ${\mathcal{J}}_{1,2}$ and with job set ${\mathcal{J}}_{2,1}$.

The permutation ${\pi }_{1,2}$ of all jobs from set ${\mathcal{J}}_{1,2}$ (the permutation ${\pi }_{2,1}$ of all jobs from set ${\mathcal{J}}_{2,1}$, respectively) is called a Johnson’s permutation, if the inequality in Equation (1) holds for the permutation ${\pi }_{1,2}$ (the inequality in Equation (2) holds for the permutation ${\pi }_{2,1}$, respectively). As it is proven in Reference [28], a Johnson’s permutation is optimal for the deterministic problem $F2\left|\right|C_{max}$.

4. A Literature Review and Closed Results

In this section, we address uncertain shop-scheduling problems if it is impossible to obtain probability distributions for random durations of the given jobs. In particular, we consider the uncertain two-machine flow-shop problem with the objective of minimizing the makespan. This problem is well studied and there are a lot of results published in the literature, unlike the uncertain job-shop problem.

4.1. 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 }_{J_i\in \mathcal{J}}{C}_i\left(s\right)$. 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\left(T\right)$ 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\left(T\right)$ is useful for the two-phase scheduling described in Reference [36].

At the off-line phase, one can construct set $S\left(T\right)$, 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\left(T\right)$ 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}\le p_{ij}\le 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}\le p_{ij}\le u_{ij}|\sum C_i$ with m machines. In Reference [29], for the two-machine flow-shop problem $F2|l_{ij}\le p_{ij}\le 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}\le p_{ij}\le 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}\le p_{ij}\le 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\left|\right|C_{max}$ is polynomially solvable (the optimal Johnson’s permutation may be constructed for the problem $F2\left|\right|C_{max}$ in $O(nlogn)$ 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\left(T\right)$ instead of the whole set S. To solve the flow-shop problem $F2|l_{ij}\le p_{ij}\le u_{ij}|C_{max}$ with job set $\mathcal{J}$, one can restrict a search within the set $S\left(T\right)$.

We next describe in detail the results published for the flow-shop problem $F2|l_{ij}\le p_{ij}\le u_{ij}|C_{max}$ since we use them for solving the job-shop problem $J2|l_{ij}\le p_{ij}\le u_{ij},n_i\le 2|C_{max}$ in Section 5, Section 6 and Section 7.

4.2. Closed Results

Since each permutation ${\pi }^{\prime }$ uniquely determines a set of the earliest completion times $C_i\left({\pi }^{\prime }\right)$ of the jobs $J_i\in \mathcal{J}$ for the problem $F2\left|\right|C_{max}$, one can identify the permutation ${\pi }^{\prime }$, ($({\pi }^{\prime },{\pi }^{\prime })\in S$), with the semi-active schedule [1,25,26] determined by the permutation ${\pi }^{\prime }$. Thus, the set S becomes a set of $n!$ pairs $({\pi }^{\prime },{\pi }^{\prime })$ of identical permutations of $n=m_{1,2}$ jobs from the set $\mathcal{J}={\mathcal{J}}_{1,2}$ since the order for processing jobs ${\mathcal{J}}_{1,2}$ on both machines may be the same in the optimal schedule [28]. Therefore, the above Definition 1 is supplemented by the following remark.

Remark 2.

For the problem $F2|l_{ij}\le p_{ij}\le u_{ij}|C_{max}$ considered in this section, it is assumed that a J-solution $S\left(T\right)$ is a minimal dominant set of Johnson’s permutations of all jobs from the set ${\mathcal{J}}_{1,2}$, i.e., for each scenario $p\in T$, the set $S\left(T\right)$ contains at least one optimal pair $({\pi }_k,{\pi }_k)$ of identical Johnson’s permutations ${\pi }_k$ such that the inequality in Equation (1) holds.

In Reference [36], it is shown how to delete redundant pairs of (identical) permutations from the set S for constructing a J-solution for the problem $F2|l_{ij}\le p_{ij}\le u_{ij}|C_{max}$ with job set $\mathcal{J}={\mathcal{J}}_{1,2}$. The order of jobs $J_v\in {\mathcal{J}}_{1,2}$ and $J_w\in {\mathcal{J}}_{1,2}$ is fixed in the J-solution if there exists at least one Johnson’s permutation of the form ${\pi }_k=(s_1,J_v,s_2,J_w,s_3)$ for any scenario $p\in T$. In Reference [29], the sufficient conditions are proven for fixing the order of two jobs from set $\mathcal{J}={\mathcal{J}}_{1,2}$. If one of the following conditions holds, then for each scenario $p\in T$, there exists a permutation ${\pi }_k=(s_1,J_v,s_2,J_w,s_3)$ that is a Johnson’s one for the problem $F2\left|p\right|C_{max}$ associated with scenario p:

$$u_{v1}\le l_{v2}\mathrm{and}{u}_{w2}\le l_{w1},$$

(3)

$$u_{v1}\le l_{v2}\mathrm{and}{u}_{v1}\le l_{w1},$$

(4)

$$u_{w2}\le l_{w1}\mathrm{and}{u}_{w2}\le l_{v2}.$$

(5)

If at least one condition in Inequalities (3)–(5) holds, then there exists a J-solution $S\left(T\right)$ for the problem $F2|l_{ij}\le p_{ij}\le u_{ij}|C_{max}$ with fixed order $J_v\to J_w$ of jobs, i.e., job $J_v$ has to be located before job $J_w$ in any permutation ${\pi }_i$, $({\pi }_i,{\pi }_i)\in S\left(T\right)$. If both conditions in Inequalities (4) and (5) do not hold, then there is no J-solution $S\left(T\right)$ with fixed order $J_v\to J_w$ in all permutations ${\pi }_i$, $({\pi }_i,{\pi }_i)\in S\left(T\right)$. If no analogous condition holds for the opposite order $J_w\to J_v$, then at least one permutation with job $J_v$ located before job $J_w$ or that with job $J_w$ located before job $J_v$ have to be included in any J-solution $S\left(T\right)$ for the problem $F2|l_{ij}\le p_{ij}\le u_{ij}|C_{max}$. Theorem 1 is proven in Reference [41].

Theorem 1.

There exists a J-solution $S\left(T\right)$ for the problem $F2|l_{ij}\le p_{ij}\le u_{ij}|C_{max}$ with fixed order $J_v\to J_w$ of the jobs $J_v$ and $J_w$ in all permutations ${\pi }_k$, $({\pi }_k,{\pi }_k)\in S\left(T\right)$ if and only if at least one condition of Inequalities (4) or (5) holds.

In Reference [41], the necessary and sufficient conditions have been proven for the case when a single-element J-solution $S\left(T\right)=\left\{({\pi }_k,{\pi }_k)\right\}$ exists for the problem $F2|l_{jm}\le p_{jm}\le u_{jm}|C_{max}$. The partition $\mathcal{J}={\mathcal{J}}^0\cup {\mathcal{J}}^1\cup {\mathcal{J}}^2\cup {\mathcal{J}}^{*}$ of the set $\mathcal{J}={\mathcal{J}}_{1,2}$ is considered, where

${\mathcal{J}}^0=\{J_i\in \mathcal{J}:u_{i1}\le l_{i2},u_{i2}\le l_{i1}\},$

${\mathcal{J}}^1=\{J_i\in \mathcal{J}:u_{i1}\le l_{i2},u_{i2}>l_{i1}\}=\{J_i\in \mathcal{J}\backslash {\mathcal{J}}^0:u_{i1}\le l_{i2}\},$

${\mathcal{J}}^2=\{J_i\in \mathcal{J}:u_{i1}>l_{i2},u_{i2}\le l_{i1}\}=\{J_i\in \mathcal{J}\backslash {\mathcal{J}}^0:u_{i2}\le l_{i1}\},$

${\mathcal{J}}^{*}=\{J_i\in \mathcal{J}:u_{i1}>l_{i2},u_{i2}>l_{i1}\}.$

For each job $J_k\in {\mathcal{J}}^0$, inequalities $u_{k1}\le l_{k2}$ and $u_{k2}\le l_{k1}$ imply inequalities $l_{k1}=u_{k1}=l_{k2}=u_{k2}$. Since both segments of the possible durations of the job $J_k$ on machines $M_1$ and $M_2$ become a point, the durations $p_{k1}$ and $p_{k2}$ are fixed and equal for both machines $M_1$ and $M_2$: $p_{k1}=p_{k2}=:p_k$. In Reference [41], Theorems 2 and 3 have been proven.

Theorem 2.

There exists a single-element J-solution $S\left(T\right)\subset S$, $\left|S\right(T\left)\right|$$=1,$ for the problem $F2|l_{ij}\le p_{ij}\le u_{ij}|C_{max}$ if and only if

(a) for any pair of jobs $J_i$ and $J_j$ from the set ${\mathcal{J}}^1$ (from the set ${\mathcal{J}}^2$, respectively), either $u_{i1}\le l_{j1}$ or $u_{j1}\le l_{i1}$ (either $u_{i2}\le l_{j2}$ or $u_{j2}\le l_{i2}$),

(b) $|{\mathcal{J}}^{*}|\le 1$; for job $J_{i^{*}}\in {\mathcal{J}}^{*}$, the inequalities $l_{i^{*}1}\ge max\{u_{i1}:J_i\in {\mathcal{J}}^1\},$$l_{i^{*}2}\ge max\{u_{j2}:J_j\in {\mathcal{J}}^2\}$ hold; and $max\{l_{i^{*}1},l_{i^{*}2}\}\ge p_k$ for each job $J_k\in {\mathcal{J}}^0$.

Theorem 2 characterizes the simplest case of the problem $F2|l_{ij}\le p_{ij}\le u_{ij}|C_{max}$ when one permutation ${\pi }_k$ of the jobs $\mathcal{J}={\mathcal{J}}_{1,2}$ dominates all other job permutations. The hardest case of this problem is characterized by the following theorem.

Theorem 3.

If $max\{l_{ik}:J_i\in \mathcal{J},M_k\in \mathcal{M}\}<min\{u_{ik}:J_i\in \mathcal{J},M_k\in \mathcal{M}\}$, then $S\left(T\right)=S$.

The J-solution $S\left(T\right)$ may be represented in a compact form using the dominance digraph which may be constructed in $O\left(n^2\right)$ time. Let $\mathcal{J}\times \mathcal{J}$ denote the Cartesian product of two sets $\mathcal{J}$. One can construct the following binary relation ${\mathcal{A}}_{⪯}\subseteq \mathcal{J}\times \mathcal{J}$ over set $\mathcal{J}={\mathcal{J}}_{1,2}$.

Definition 2.

For the two jobs $J_v\in \mathcal{J}$ and $J_w\in \mathcal{J}$, the inclusion $(J_v,J_w)\in {\mathcal{A}}_{⪯}$ holds if and only if there exists a J-solution $S\left(T\right)$ for the problem $F2|l_{ij}\le p_{ij}\le u_{ij}|C_{max}$ such that job $J_v\in \mathcal{J}$ is located before job $J_w\in \mathcal{J}$, $v\ne w$, in all permutations ${\pi }_k$, where $({\pi }_k,{\pi }_k)\in S\left(T\right)$.

The binary relation $(J_v,J_w)\in {\mathcal{A}}_{⪯}$ is represented as follows: $J_v⪯J_w$. Due to Theorem 1, if for the jobs $J_v\in \mathcal{J}$ and $J_w\in \mathcal{J}$ the relation $J_v⪯J_w$, $v\ne w$, holds, then for the jobs $J_v$ and $J_w$, at least one of conditions in Inequalities (4) and (5) holds. To construct the binary relation ${\mathcal{A}}_{⪯}$ of the jobs on the set $\mathcal{J}$, it is sufficient to check Inequalities (4) and (5) for each pair of jobs $J_v$ and $J_w$. The binary relation ${\mathcal{A}}_{⪯}$ determines the digraph $(\mathcal{J},{\mathcal{A}}_{⪯})$ with vertex set $\mathcal{J}$ and arc set ${\mathcal{A}}_{⪯}$. It takes $O\left(n^2\right)$ time to construct the digraph $(\mathcal{J},{\mathcal{A}}_{⪯})$. In the general case, the binary relation ${\mathcal{A}}_{⪯}$ may be not transitive. In Reference [42], it is proven that, if the binary relation ${\mathcal{A}}_{⪯}$ is not transitive, then ${\mathcal{J}}^0\ne \varnothing$. We next consider the case with the equality ${\mathcal{J}}^0=\varnothing$, i.e., $\mathcal{J}={\mathcal{J}}^{*}\cup {\mathcal{J}}^1\cup {\mathcal{J}}^2$ (the case with ${\mathcal{J}}^0\ne \varnothing$ has been considered in Reference [41]). For a pair of jobs $J_v\in {\mathcal{J}}^1$ and $J_w\in {\mathcal{J}}^1$ (for a pair of jobs $J_v\in {\mathcal{J}}^2$ and $J_w\in {\mathcal{J}}^2$, respectively), it may happen that there exist both J-solution $S\left(T\right)$ with job $J_v$ located before job $J_w$ in all permutations ${\pi }_k$, $({\pi }_k,{\pi }_k)\in S\left(T\right)$ and J-solution $S^{\prime }\left(T\right)$ with job $J_w$ located before job $J_v$ in all permutations ${\pi }_l$, $({\pi }_l,{\pi }_l)\in S^{\prime }\left(T\right)$.

In Reference [42], the following claim has been proven.

Theorem 4.

The digraph $(\mathcal{J},{\mathcal{A}}_{⪯})$ has no circuits if and only if the set $\mathcal{J}={\mathcal{J}}^{*}\cup {\mathcal{J}}^1\cup {\mathcal{J}}^2$ includes no pair of jobs $J_i\in {\mathcal{J}}^k$ and $J_j\in {\mathcal{J}}^k$ with $k\in \{1,2\}$ such that $l_{ik}=u_{ik}=l_{jk}=u_{jk}.$

The binary relation ${\mathcal{A}}_{\prec }\subset {\mathcal{A}}_{⪯}\subseteq \mathcal{J}\times \mathcal{J}$ is defined as follows.

Definition 3.

For the jobs $J_v\in \mathcal{J}$ and $J_w\in \mathcal{J}$, the inclusion $(J_v,J_w)\in {\mathcal{A}}_{\prec }$ holds if and only if $J_v⪯J_w$ and $J_w\cancel{⪯}{J}_v$, or $J_v⪯J_w$ and $J_w⪯J_v$ with $v<w$.

The relation $(J_v,J_w)\in {\mathcal{A}}_{\prec }$ is represented as follows: $J_v\prec J_w$. As it is shown in Reference [42], the relation $J_v\prec J_w$ implies that $J_v⪯J_w$ and that at least one condition in Inequalities (4) or (5) must hold. The relation $J_v⪯J_w$ implies exactly one of the relations $J_v\prec J_w$ or $J_w\prec J_v$.

Since it is assumed that set ${\mathcal{J}}^0$ is empty, the binary relation ${\mathcal{A}}_{\prec }$ is an antireflective, antisymmetric, and transitive relation, i.e., the binary relation ${\mathcal{A}}_{\prec }$ is a strict order. The strict order ${\mathcal{A}}_{\prec }$ determines the digraph $\mathcal{G}=(\mathcal{J},{\mathcal{A}}_{\prec })$ with arc set ${\mathcal{A}}_{\prec }$. The digraph $\mathcal{G}=(\mathcal{J},{\mathcal{A}}_{\prec })$ has neither a circuit nor a loop. Properties of the dominance digraph $\mathcal{G}$ were studied in Reference [42]. The permutation ${\pi }_k=(J_{k_1},J_{k_2},\dots ,J_{k_n})$, $({\pi }_k,{\pi }_k)\in S,$ may be considered as a total strict order of all jobs of the set $\mathcal{J}$. The total strict order determined by permutation ${\pi }_k$ is a linear extension of the partial strict order ${\mathcal{A}}_{\prec }$ if each inclusion $(J_{k_v},J_{k_w})\in {\mathcal{A}}_{\prec }$ implies inequality $v<w$. Let $\mathsf{\Pi }\left(\mathcal{G}\right)$ denote a set of permutations ${\pi }_k\in S_{1,2}$ defining all linear extensions of the partial strict order ${\mathcal{A}}_{\prec }$. The cases when $\mathsf{\Pi }\left(\mathcal{G}\right)=S_{1,2}$ and $\mathsf{\Pi }\left(\mathcal{G}\right)=\left\{{\pi }_k\right\}$ are characterized in Theorems 2 and 3. In the latter case, the strict order ${\mathcal{A}}_{\prec }$ over set $\mathcal{J}$ can be represented as follows: $J_{k_1}\prec \dots \prec J_{k_i}\prec J_{k_{i+1}}\prec \dots \prec J_{k_{n_{1,2}}}.$ In Reference [42], the following claims have been proven.

Theorem 5.

Let $\mathcal{J}={\mathcal{J}}^{*}\cup {\mathcal{J}}^1\cup {\mathcal{J}}^2$. For any scenario $p\in T$, the set $\mathsf{\Pi }\left(\mathcal{G}\right)$ contains a Johnson’s permutation for the problem $F2\left|p\right|C_{max}$.

Corollary 1.

If $\mathcal{J}={\mathcal{J}}^{*}\cup {\mathcal{J}}^1\cup {\mathcal{J}}^2$, then there exists a J-solution $S\left(T\right)$ for the problem $F2|l_{ij}\le p_{ij}\le u_{ij}|C_{max}$ such that ${\pi }^{\prime }\in \mathsf{\Pi }\left(\mathcal{G}\right)$ for all pairs of job permutations, $\left\{({\pi }^{\prime },{\pi }^{\prime })\right\}\in S\left(T\right)$.

In Reference [42], it was studied how to construct a minimal dominant set $S\left(T\right)=\left\{({\pi }^{\prime },{\pi }^{\prime })\right\}$, ${\pi }^{\prime }\in \mathsf{\Pi }\left(\mathcal{G}\right)$. Two types of redundant permutations were examined, and the following claim was proven.

Lemma 1.

Let $\mathcal{J}={\mathcal{J}}^{*}\cup {\mathcal{J}}_1\cup {\mathcal{J}}_2$. If permutation ${\pi }_t\in \mathsf{\Pi }\left(\mathcal{G}\right)$ is redundant in the set $\mathsf{\Pi }\left(\mathcal{G}\right)$, then ${\pi }_t$ is a redundant permutation either of type 1 or type 2.

Testing whether set $\mathsf{\Pi }\left(\mathcal{G}\right)$ contains a redundant permutation of type 1 takes $O\left(n^2\right)$ time, and testing whether permutation ${\pi }_g\in \mathsf{\Pi }\left(\mathcal{G}\right)$ is a redundant permutation of type 2 takes $O\left(n\right)$ time. In Reference [42], it is shown how to delete all redundant permutations from the set $\mathsf{\Pi }\left(\mathcal{G}\right)$. Let ${\mathsf{\Pi }}^{*}\left(\mathcal{G}\right)$ denote a set of permutations remaining in the set $\mathsf{\Pi }\left(\mathcal{G}\right)$ after deleting all redundant permutations of type 1 and type 2.

Theorem 6.

Assume the following condition:

$$max\{l_{i,3-k},l_{j,3-k}\}<l_{ik}=u_{ik}=l_{jk}=u_{jk}<min\{u_{i,3-k},u_{j,3-k}\}.$$

(6)

If set $\mathcal{J}={\mathcal{J}}^{*}\cup {\mathcal{J}}^1\cup {\mathcal{J}}^2$ does not contain a pair of jobs $J_i\in {\mathcal{J}}^k$ and $J_j\in {\mathcal{J}}^k$, $k\in \{1,2\}$, such that the above condition holds, then $S\left(T\right)=<{\mathsf{\Pi }}^{*}\left(\mathcal{G}\right),{\mathsf{\Pi }}^{*}\left(\mathcal{G}\right)>$.

To test conditions of Theorem 6 takes $O\left(n\right)$ time. Due to Theorem 6 and Lemma 1, if there are no jobs such that condition (6) holds, then a J-solution can be constructed via deleting redundant permutations from set $\mathsf{\Pi }\left(\mathcal{G}\right)$. Since the set ${\mathsf{\Pi }}^{*}\left(\mathcal{G}\right)$ is uniquely determined [42], we obtain Corollary 2.

Corollary 2

([42]). If set $\mathcal{J}={\mathcal{J}}^{*}\cup {\mathcal{J}}^1\cup {\mathcal{J}}^2$ does not contain a pair of jobs $J_i$ and $J_j$ such that condition (6) holds, then the binary relation ${\mathcal{A}}_{\prec }$ determines a unique J-solution $S\left(T\right)=<{\mathsf{\Pi }}^{*}\left(\mathcal{G}\right),{\mathsf{\Pi }}^{*}\left(\mathcal{G}\right)>$ for the problem $F2|l_{ij}\le p_{ij}\le u_{ij}|C_{max}$.

The condition of Theorem 6 is sufficient for the uniqueness of a J-solution ${\mathsf{\Pi }}^{*}\left(\mathcal{G}\right)=S\left(T\right)$ for the problem $F2|l_{ij}\le p_{ij}\le u_{ij}|C_{max}$. Due to Theorem 1, one can construct a digraph $\mathcal{G}=(\mathcal{J},{\mathcal{A}}_{\prec })$ in $O\left(n^2\right)$ time. The digraph $\mathcal{G}=(\mathcal{J},{\mathcal{A}}_{\prec })$ determines a set $S\left(T\right)$ and may be considered a condensed form of a J-solution for the problem $F2|l_{ij}\le p_{ij}\le u_{ij}|C_{max}$. The results presented in this section are used in Section 5 for constructing precedence digraphs for the problem $J2|l_{ij}\le p_{ij}\le u_{ij},n_i\le 2|C_{max}$.

5. Properties of the Optimal Pairs of Job Permutations

We consider the uncertain job-shop problem $J2|l_{ij}\le p_{ij}\le u_{ij},n_i\le 2|C_{max}$ and prove sufficient conditions for determining a small dominant set of schedules for this problem. In what follows, we use Definition 4 of the dominant set $DS\left(T\right)\subseteq S$ along with Definition 1 of the J-solution $S\left(T\right)\subseteq S$.

Definition 4.

A set of the pairs of job permutations $DS\left(T\right)\subseteq S$ is called a dominant set (of schedules) for the uncertain problem $J2|l_{ij}\le p_{ij}\le u_{ij},n_i\le 2|C_{max}$ if, for each scenario $p\in T$, the set $DS\left(T\right)$ contains at least one optimal pair of job permutations for the individual deterministic problem $J2|p,n_i\le 2|C_{max}$ with scenario p.

Every J-solution (Definition 1) is a dominant set for the problem $J2|l_{ij}\le p_{ij}\le u_{ij},n_i\le 2|C_{max}$. Before processing jobs of the set $\mathcal{J}$ (before the realization of a schedule $s\in S$), a scheduler does not know exact values of the job durations. Nevertheless, it is needed to choose a pair of permutations of the jobs $\mathcal{J}$, i.e., it is needed to determine orders of jobs for processing them on machine $M_1$ and machine $M_2$. When all jobs will be processed on machines $\mathcal{M}$ (a schedule will be realized) and the job durations will take on exact values $p_{ij}^{*}$, $l_{ij}\le p_{ij}^{*}\le u_{ij}$, and so a factual scenario $p^{*}\in T$ will be determined. A schedule s chosen for the realization should be optimal for the obtained factual scenario $p^{*}$. In the stability approach, one can use two phases of scheduling for solving an uncertain scheduling problem: the off-line phase and the on-line phase. The off-line phase of scheduling is finished before starting the realization of a schedule. At this phase, a scheduler knows only given segments of the job durations and the aim is to find a pair of job permutations $({\pi }^{\prime },{\pi }^{″})$ which is optimal for the most scenarios $p\in T$. After constructing a small dominant set of schedules $DS\left(T\right)$, a scheduler can choose a pair of job permutations in the set $DS\left(T\right)$, which dominates the most pairs of job permutations $({\pi }^{\prime },{\pi }^{″})\in S$ for the given scenarios T. Note that making a decision at the off-line phase may be time-consuming since the realization of a schedule is not started.

The on-line phase of scheduling can begin once the earliest job in the schedule $({\pi }^{\prime },{\pi }^{″})$ starts. At this phase, a scheduler can use additional on-line information on the job duration since, for each operation $O_{ij}$, the exact value $p_{ij}^{*}$ becomes known at the time of the completion of this operation. At the on-line phase, the selection of a next job for processing should be quick.

In Section 5.1, we investigate sufficient conditions for a pair of job permutations $({\pi }^{\prime },{\pi }^{″})$ such that equality $DS\left(T\right)=\left\{({\pi }^{\prime },{\pi }^{″})\right\}$ holds. In Section 5.2, the sufficient conditions allowing to construct a single optimal schedule dominating all other schedules in the set S are proven. If a single-element dominant set $DS\left(T\right)$ does not exist, then one should construct two partial strict orders $A_{\prec }^{1,2}$ and $A_{\prec }^{2,1}$ on the set ${\mathcal{J}}_{1,2}$ and on the set ${\mathcal{J}}_{2,1}$ of jobs as it is described in Section 4.2. These orders may be constructed in the form of the two precedence digraphs allowing a scheduler to reduce a size of the dominant set $DS\left(T\right)$. Section 5.4 presents Algorithm 1 for constructing a semi-active schedule, which is optimal for the problem $F2|l_{ij}\le p_{ij}\le u_{ij}|C_{max}$ for all possible scenarios T provided that such a schedule exists. Otherwise, Algorithm 1 constructs the precedence digraphs determining a minimal dominant set of schedules for the problem $F2|l_{ij}\le p_{ij}\le u_{ij}|C_{max}$.

5.1. Sufficient Conditions for an Optimal Pair of Job Permutations

In the proofs of several claims, we use a notion of the main machine, which is introduced within the proof of the following theorem.

Theorem 7.

Consider the following conditions in Inequalities (7) or (8):

$$\sum _{J_i\in {\mathcal{J}}_{1,2}}{u}_{i1}\le \sum _{J_i\in {\mathcal{J}}_{2,1}\cup {\mathcal{J}}_2}{l}_{i2} and \sum _{J_i\in {\mathcal{J}}_{1,2}}{l}_{i2}\ge \sum _{J_i\in {\mathcal{J}}_{2,1}\cup {\mathcal{J}}_1}{u}_{i1}$$

(7)

$$\sum _{J_i\in {\mathcal{J}}_{2,1}}{u}_{i2}\le \sum _{J_i\in {\mathcal{J}}_{1,2}\cup {\mathcal{J}}_1}{l}_{i1} and \sum _{J_i\in {\mathcal{J}}_{2,1}}{l}_{i1}\ge \sum _{J_i\in {\mathcal{J}}_{1,2}\cup {\mathcal{J}}_2}{u}_{i2}$$

(8)

If one of the above conditions holds, then any pair of job permutations $({\pi }^{\prime },{\pi }^{″})\in S$ is a single-element dominant set $DS\left(T\right)=\left\{({\pi }^{\prime },{\pi }^{″})\right\}$ for the problem $J2|l_{ij}\le p_{ij}\le u_{ij},n_i\le 2|C_{max}$ with set $\mathcal{J}={\mathcal{J}}_1\cup {\mathcal{J}}_2\cup {\mathcal{J}}_{1,2}\cup {\mathcal{J}}_{2,1}$ of the given jobs.

Proof. 

Let the condition in Inequalities (7) hold. Then, we consider an arbitrary pair of job permutations $({\pi }^{\prime },{\pi }^{″})\in S$ with any fixed scenario $p\in T$ and show that this pair of job permutations $({\pi }^{\prime },{\pi }^{″})$ is optimal for the individual deterministic problem $J2|p,n_i\le 2|C_{max}$ with scenario p, i.e., $C_{max}({\pi }^{\prime },{\pi }^{″})=C_{max}$.

Let $c_1\left({\pi }^{\prime }\right)$ ($c_2\left({\pi }^{″}\right)$) denote a completion time of all jobs ${\mathcal{J}}_1\cup {\mathcal{J}}_{1,2}\cup {\mathcal{J}}_{2,1}$ (jobs ${\mathcal{J}}_2\cup {\mathcal{J}}_{1,2}\cup {\mathcal{J}}_{2,1}$) on machine $M_1$ (machine $M_2$) in the schedule $({\pi }^{\prime },{\pi }^{″})$, where ${\pi }^{\prime }=({\pi }_{1,2},{\pi }_1,{\pi }_{2,1})$ and ${\pi }^{″}=({\pi }_{2,1},{\pi }_2,{\pi }_{1,2})$. For the problem $J2|p,n_i\le 2|C_{max}$, the maximal completion time of the jobs in schedule $({\pi }^{\prime },{\pi }^{″})$ may be calculated as follows: $C_{max}({\pi }^{\prime },{\pi }^{″})=max\{c_1\left({\pi }^{\prime }\right),c_2\left({\pi }^{″}\right)\}$.

Machine $M_1$ (machine $M_2$) is called a main machine for the schedule $({\pi }^{\prime },{\pi }^{″})$ if equality $C_{max}({\pi }^{\prime },{\pi }^{″})=c_1\left({\pi }^{\prime }\right)$ holds (equality $C_{max}({\pi }^{\prime },{\pi }^{″})=c_2\left({\pi }^{″}\right)$ holds, respectively).

For schedule $({\pi }^{\prime },{\pi }^{″})\in S$, the following equality holds:

$$c_1\left({\pi }^{\prime }\right)=\sum _{J_i\in {\mathcal{J}}_{1,2}\cup {\mathcal{J}}_{2,1}\cup {\mathcal{J}}_1}{p}_{i1}+I_1;c_2\left({\pi }^{″}\right)=\sum _{J_i\in {\mathcal{J}}_{1,2}\cup {\mathcal{J}}_{2,1}\cup {\mathcal{J}}_2}{p}_{i2}+I_2,$$

where $I_1$ and $I_2$ denote total idle times of machine $M_1$ and machine $M_2$ in the schedule $({\pi }^{\prime },{\pi }^{″})$, respectively. We next show that, if the condition in Inequalities (7) holds, then machine $M_2$ is a main machine for schedule $({\pi }^{\prime },{\pi }^{″})$ and machine $M_2$ has no idle time, i.e., machine $M_2$ is completely filled in the segment $[0,c_2\left({\pi }^{″}\right)]$ for processing jobs from the set ${\mathcal{J}}_{1,2}\cup {\mathcal{J}}_{2,1}\cup {\mathcal{J}}_2$. At the initial time $t=0$, machine $M_2$ begins to process jobs from the set ${\mathcal{J}}_{2,1}\cup {\mathcal{J}}_2$ without idle times until the time moment $t_1={\sum }_{J_i\in {\mathcal{J}}_{2,1}\cup {\mathcal{J}}_2}{p}_{i2}.$

From the first inequality in (7), we obtain the following relations:

$$\sum _{J_i\in {\mathcal{J}}_{1,2}}{p}_{i1}\le \sum _{J_i\in {\mathcal{J}}_{1,2}}{u}_{i1}\le \sum _{J_i\in {\mathcal{J}}_{2,1}\cup {\mathcal{J}}_2}{l}_{i2}\le \sum _{J_i\in {\mathcal{J}}_{2,1}\cup {\mathcal{J}}_2}{p}_{i2}=t_1.$$

Therefore, at the time moment $t_1$, machine $M_2$ begins to process jobs from the set ${\mathcal{J}}_{1,2}$ without idle times and we obtain the following equality: $c_2\left({\pi }^{″}\right)={\sum }_{J_i\in {\mathcal{J}}_{1,2}\cup {\mathcal{J}}_{2,1}\cup {\mathcal{J}}_2}{p}_{i2},$ where $I_2=0$ and machine $M_2$ has no idle time. We next show that machine $M_2$ is a main machine for the schedule $({\pi }^{\prime },{\pi }^{″})$. To this end, we consider the following two possible cases.

(a) Let machine $M_1$ have no idle time.

By summing Inequalities (7), we obtain the following inequality:

$$\sum _{J_i\in {\mathcal{J}}_{1,2}\cup {\mathcal{J}}_{2,1}\cup {\mathcal{J}}_1}{u}_{i1}\le \sum _{J_i\in {\mathcal{J}}_{1,2}\cup {\mathcal{J}}_{2,1}\cup {\mathcal{J}}_2}{l}_{i2}.$$

Thus, the following relations hold:

$$c_1\left({\pi }^{\prime }\right)=\sum _{J_i\in {\mathcal{J}}_{1,2}\cup {\mathcal{J}}_{2,1}\cup {\mathcal{J}}_1}{p}_{i1}\le \sum _{J_i\in {\mathcal{J}}_{1,2}\cup {\mathcal{J}}_{2,1}\cup {\mathcal{J}}_1}{u}_{i1}\le \sum _{J_i\in {\mathcal{J}}_{1,2}\cup {\mathcal{J}}_{2,1}\cup {\mathcal{J}}_2}{l}_{i2}\le \sum _{J_i\in {\mathcal{J}}_{1,2}\cup {\mathcal{J}}_{2,1}\cup {\mathcal{J}}_2}{p}_{i2}=c_2\left({\pi }^{″}\right).$$

Hence, machine $M_2$ is a main machine for the schedule $({\pi }^{\prime },{\pi }^{″})$.

(b) Let machine $M_1$ have an idle time.

An idle time of machine $M_1$ is only possible if some job $J_j$ from set ${\mathcal{J}}_{2,1}$ is processed on machine $M_2$ at the time moment $t_2$ when this job $J_j$ could be processed on machine $M_1$.

Obviously, after the time moment ${\sum }_{J_i\in {\mathcal{J}}_{2,1}}{p}_{i2}$ when machine $M_2$ completes all jobs from set ${\mathcal{J}}_{2,1}$, machine $M_1$ can process some jobs from set ${\mathcal{J}}_{2,1}$ without an idle time. Therefore, the inequality $t_2+I_1\le {\sum }_{J_i\in {\mathcal{J}}_{2,1}}{p}_{i2}$ holds and we obtain the following relations:

$$c_1\left({\pi }^{\prime }\right)\le t_2+I_1+\sum _{J_i\in {\mathcal{J}}_{2,1}}{p}_{i1}\le \sum _{J_i\in {\mathcal{J}}_{2,1}}{p}_{i2}+\sum _{J_i\in {\mathcal{J}}_{2,1}\cup {\mathcal{J}}_1}{p}_{i1}\le \sum _{J_i\in {\mathcal{J}}_{2,1}}{p}_{i2}+\sum _{J_i\in {\mathcal{J}}_{2,1}\cup {\mathcal{J}}_1}{u}_{i1}$$

$$\le \sum _{J_i\in {\mathcal{J}}_{2,1}}{p}_{i2}+\sum _{J_i\in {\mathcal{J}}_{1,2}}{l}_{i2}\le \sum _{J_i\in {\mathcal{J}}_{2,1}}{p}_{i2}+\sum _{J_i\in {\mathcal{J}}_{1,2}}{p}_{i2}\le \sum _{J_i\in {\mathcal{J}}_{2,1}\cup {\mathcal{J}}_2\cup {\mathcal{J}}_{1,2}}{p}_{i2}=c_2\left({\pi }^{″}\right).$$

We conclude that, in case (b), machine $M_2$ is a main machine for the schedule $({\pi }^{\prime },{\pi }^{″})$. Thus, if the condition in Inequalities (7) holds, then machine $M_2$ is a main machine for the schedule $({\pi }^{\prime },{\pi }^{″})$ and machine $M_2$ has no idle time, i.e., equality $C_{max}({\pi }^{\prime },{\pi }^{″})=c_2\left({\pi }^{″}\right)$ holds and machine $M_2$ is completely filled in the segment $[0,c_2\left({\pi }^{″}\right)]$ with processing jobs from the set ${\mathcal{J}}_{1,2}\cup {\mathcal{J}}_{2,1}\cup {\mathcal{J}}_2$.

Thus, the pair of permutations $({\pi }^{\prime },{\pi }^{″})$ is optimal for scenario $p\in T$. Since scenario p was chosen arbitrarily in the set T, we conclude that the pair of job permutations $({\pi }^{\prime },{\pi }^{″})$ is a singleton $DS\left(T\right)=\left\{({\pi }^{\prime },{\pi }^{″})\right\}$ for the problem $J2|l_{ij}\le p_{ij}\le u_{ij},n_i\le 2|C_{max}$ with set $\mathcal{J}={\mathcal{J}}_1\cup {\mathcal{J}}_2\cup {\mathcal{J}}_{1,2}\cup {\mathcal{J}}_{2,1}$ of the given jobs. As a pair of permutations $({\pi }^{\prime },{\pi }^{″})$ is an arbitrary pair of job permutations in the set S, any pair of job permutations $({\pi }^{\prime },{\pi }^{″})\in S$ is a singleton $DS\left(T\right)=\left\{({\pi }^{\prime },{\pi }^{″})\right\}$ for the problem $J2|l_{ij}\le p_{ij}\le u_{ij},n_i\le 2|C_{max}$ with job set $\mathcal{J}={\mathcal{J}}_1\cup {\mathcal{J}}_2\cup {\mathcal{J}}_{1,2}\cup {\mathcal{J}}_{2,1}$.

The case when the condition in Inequalities (8) holds may be analyzed similarly via replacing machine $M_1$ by machine $M_2$ and vice versa. □

If conditions of Theorem 7 hold, then in the optimal pair of job permutations $({\pi }^{\prime },{\pi }^{″})$ existing for the problem $J2|l_{ij}\le p_{ij}\le u_{ij},n_i\le 2|C_{max}$, the orders of jobs from sets ${\mathcal{J}}_{1,2}\subseteq \mathcal{J}$ and ${\mathcal{J}}_{2,1}\subseteq \mathcal{J}$ may be chosen arbitrarily. Theorem 7 implies the following two corollaries.

Corollary 3.

If the following inequality holds:

$$\sum _{J_j\in {\mathcal{J}}_{1,2}}{u}_{i1}\le \sum _{J_j\in {\mathcal{J}}_{2,1}\cup {\mathcal{J}}_2}{l}_{i2},$$

(9)

then set $<\left\{{\pi }_{1,2}\right\},S_{2,1}>\subseteq S$, where ${\pi }_{1,2}$ is an arbitrary permutation in set $S_{1,2}$, is a dominant set of schedules for the problem $J2|l_{ij}\le p_{ij}\le u_{ij},n_i\le 2|C_{max}$ with set $\mathcal{J}={\mathcal{J}}_1\cup {\mathcal{J}}_2\cup {\mathcal{J}}_{1,2}\cup {\mathcal{J}}_{2,1}$ of the given jobs.

Proof. 

We consider an arbitrary vector $p\in T$ of the job durations and an arbitrary permutation ${\pi }_{1,2}$ in the set $S_{1,2}$. The set $S_{2,1}$ contains at least one Johnson’s permutation ${\pi }_{2,1}^{*}$ for the deterministic problem $F2|p_{2,1}|C_{max}$ with job set ${\mathcal{J}}_{2,1}$ and scenario $p_{2,1}$ (the components of vector $p_{2,1}$ are equal to the corresponding components of vector p). We consider a pair of job permutations $({\pi }^{\prime },{\pi }^{″})$$=(({\pi }_{1,2},{\pi }_1,{\pi }_{2,1}^{*}),({\pi }_{2,1}^{*},{\pi }_2,{\pi }_{1,2}))\in <\left\{{\pi }_{1,2}\right\},S_{2,1}>\subseteq S$ and show that it is an optimal pair of job permutations for the problem $J2|p,n_i\le 2|C_{max}$ with job set $\mathcal{J}$ and scenario p. Without loss of generality, both permutations ${\pi }_1$ and ${\pi }_2$ are ordered in increasing order of the indexes of their jobs.

Similar to the proof of Theorem 7, one can show that, if the condition in Inequalities (9) holds, then machine $M_2$ processes jobs without idle times and equality $c_2\left({\pi }^{″}\right)={\sum }_{J_i\in {\mathcal{J}}_{1,2}\cup {\mathcal{J}}_{2,1}\cup {\mathcal{J}}_2}{p}_{i2}$ holds, where the value of $c_2\left({\pi }^{″}\right)$ cannot be reduced. If machine $M_1$ has no idle time, we obtain equalities

$$C_{max}({\pi }^{\prime },{\pi }^{″})=max\{c_1\left({\pi }^{\prime }\right),c_2\left({\pi }^{″}\right)\}=max\{\sum _{J_i\in {\mathcal{J}}_{1,2}\cup {\mathcal{J}}_{2,1}\cup {\mathcal{J}}_1}{p}_{i1},\sum _{J_i\in {\mathcal{J}}_{1,2}\cup {\mathcal{J}}_{2,1}\cup {\mathcal{J}}_2}{p}_{i2}\}=C_{max}.$$

On the other hand, an idle time of machine $M_1$ is only possible if some job $J_j$ from set ${\mathcal{J}}_{2,1}$ is processed on machine $M_2$ at the time moment $t_2$ when job $J_j$ could be processed on machine $M_1$. In such a case, the value of $c_1\left({\pi }^{\prime }\right)$ is equal to the makespan $C_{max}\left({\pi }_{2,1}^{*}\right)$ for the problem $F2|p_{2,1}|C_{max}$ with job set ${\mathcal{J}}_{2,1}$ and scenario $p_{2,1}$. As the permutation ${\pi }_{2,1}^{*}$ is a Johnson’s permutation, the value of $C_{max}\left({\pi }_{2,1}^{*}\right)$ cannot be reduced and we obtain the following equalities:

$$C_{max}({\pi }^{\prime },{\pi }^{″})=max\{c_1\left({\pi }^{\prime }\right),c_2\left({\pi }^{″}\right)\}=max\{C_{max}\left({\pi }_{2,1}^{*}\right),\sum _{J_i\in {\mathcal{J}}_{1,2}\cup {\mathcal{J}}_{2,1}\cup {\mathcal{J}}_2}{p}_{i2}\}=C_{max}.$$

Thus, the pair of job permutation $({\pi }^{\prime },{\pi }^{″})=(({\pi }_{1,2},{\pi }_1,{\pi }_{2,1}^{*}),({\pi }_{2,1}^{*},{\pi }_2,{\pi }_{1,2}))\in$$<\left\{{\pi }_{1,2}\right\},S_{2,1}>\subseteq S$ is optimal for the problem $J2|p,n_i\le 2|C_{max}$ with scenario $p\in T$. The optimal pair of job permutations for the problem $J2|p,n_i\le 2|C_{max}$ with scenario $p\in T$ belongs to the set $<\left\{{\pi }_{1,2}\right\},S_{2,1}>$. As vector p is an arbitrary vector in the set T, the set $<\left\{{\pi }_{1,2}\right\},S_{2,1}>$ contains an optimal pair of job permutations for all scenarios from set T. Due to Definition 4, the set $<\left\{{\pi }_{1,2}\right\},S_{2,1}>\subseteq S$ is a dominant set of schedules for the problem $J2|l_{ij}\le p_{ij}\le u_{ij},n_i\le 2|C_{max}$ with job set $\mathcal{J}$. □

Corollary 4.

Consider the following inequality:

$$\sum _{J_j\in {\mathcal{J}}_{2,1}}{u}_{i2}\le \sum _{J_j\in {\mathcal{J}}_{1,2}\cup {\mathcal{J}}_1}{l}_{i1}.$$

If the above inequality holds, then set $<S_{1,2},\left\{{\pi }_{2,1}\right\}>$, where ${\pi }_{2,1}$ is an arbitrary permutation in set $S_{2,1}$, is a dominant set of schedules for the problem $J2|l_{ij}\le p_{ij}\le u_{ij},n_i\le 2|C_{max}$ with set $\mathcal{J}={\mathcal{J}}_1\cup {\mathcal{J}}_2\cup {\mathcal{J}}_{1,2}\cup {\mathcal{J}}_{2,1}$ of the given jobs.

This claim may be proven similar to Corollary 3. If the conditions of Corollary 3 (Corollary 4) hold, then the order for processing jobs from set ${\mathcal{J}}_{1,2}\subseteq \mathcal{J}$ (set ${\mathcal{J}}_{2,1}\subseteq \mathcal{J}$, respectively) in the optimal schedule $({\pi }^{\prime },{\pi }^{″})=\left(\right({\pi }_{1,2},{\pi }_1,$${\pi }_{2,1}),({\pi }_{2,1},{\pi }_2,{\pi }_{1,2}))$ for the problem $J2|l_{ij}\le p_{ij}\le u_{ij},n_i\le 2|C_{max}$ may be arbitrary. Since the orders of jobs from the sets ${\mathcal{J}}_1$ and ${\mathcal{J}}_2$ are fixed in the optimal schedule (Remark 1), we need to determine only orders for processing jobs from set ${\mathcal{J}}_{2,1}$ (set ${\mathcal{J}}_{1,2}$, respectively). To do this, we will consider two uncertain problems $F2|l_{ij}\le p_{ij}\le u_{ij}|C_{max}$ with job set ${\mathcal{J}}_{1,2}\subseteq \mathcal{J}$ and with the machine route $(M_1,M_2)$ and that with job set ${\mathcal{J}}_{2,1}\subseteq \mathcal{J}$ and with the opposite machine route $(M_2,M_1)$.

Lemma 2.

If $S_{1,2}^{\prime }\subseteq S_{1,2}$ is a set of permutations from the dominant set for the problem $F2|l_{ij}\le p_{ij}\le u_{ij}|C_{max}$ with job set ${\mathcal{J}}_{1,2}$, then $<S_{1,2}^{\prime },S_{2,1}>\subseteq S$ is a dominant set for the problem $J2|l_{ij}\le p_{ij}\le u_{ij},n_i\le 2|C_{max}$ with job set $\mathcal{J}={\mathcal{J}}_1\cup {\mathcal{J}}_2\cup {\mathcal{J}}_{1,2}\cup {\mathcal{J}}_{2,1}$.

The proof of Lemma 2 and those for other statements in this section are given in Appendix A.

Lemma 3.

Let $S_{2,1}^{\prime }\subseteq S_{2,1}$ be a set of permutations from the dominant set for the problem $F2|l_{ij}\le p_{ij}\le u_{ij}|C_{max}$ with job set ${\mathcal{J}}_{2,1}$, $S_{2,1}^{\prime }\subseteq S_{2,1}$. Then, $<S_{1,2},S_{2,1}^{\prime }>$ is a dominant set for the problem $J2|l_{ij}\le p_{ij}\le u_{ij},n_i\le 2|C_{max}$ with job set $\mathcal{J}$.

The proof of this claim is similar to that for Lemma 2 (see Appendix A).

Theorem 8.

Let $S_{1,2}^{\prime }\subseteq S_{1,2}$ be a set of permutations from the dominant set for the problem $F2|l_{ij}\le p_{ij}\le u_{ij}|C_{max}$ with job set ${\mathcal{J}}_{1,2}$, and let $S_{2,1}^{\prime }\subseteq S_{2,1}$ be a set of permutations from the dominant set for the problem $F2|l_{ij}\le p_{ij}\le u_{ij}|C_{max}$ with job set ${\mathcal{J}}_{2,1}$. Then, $<S_{1,2}^{\prime },S_{2,1}^{\prime }>\subseteq S$ is a dominant set for the problem $J2|l_{ij}\le p_{ij}\le u_{ij},n_i\le 2|C_{max}$ with job set $\mathcal{J}={\mathcal{J}}_1\cup {\mathcal{J}}_2\cup {\mathcal{J}}_{1,2}\cup {\mathcal{J}}_{2,1}$.

Theorem 9.

Let a pair of identical permutations $({\pi }_{1,2},{\pi }_{1,2})$ determine a single-element J-solution for the problem $F2|l_{ij}\le p_{ij}\le u_{ij}|C_{max}$ with job set ${\mathcal{J}}_{1,2}$, and let a pair of identical permutations $({\pi }_{2,1},{\pi }_{2,1})$ determine a single-element J-solution for the problem $F2|l_{ij}\le p_{ij}\le u_{ij}|C_{max}$ with job set ${\mathcal{J}}_{2,1}$. Then, the pairs of permutations $\left\{({\pi }_{1,2},{\pi }_1,{\pi }_{2,1})and({\pi }_{1,2},{\pi }_2,{\pi }_{2,1})\right\}$ are a single-element dominant set $DS\left(T\right)$ for the problem $J2|l_{ij}\le p_{ij}\le u_{ij},n_i\le 2|C_{max}$ with job set $\mathcal{J}={\mathcal{J}}_1\cup {\mathcal{J}}_2\cup {\mathcal{J}}_{1,2}\cup {\mathcal{J}}_{2,1}$.

The following claim follows directly from Theorem 9.

Corollary 5.

If the conditions of Theorem 9 hold, then there exists a single pair of job permutations, which is an optimal pair of job permutations for the problem $J2|p,n_i\le 2|C_{max}$ with job set $\mathcal{J}$ and any scenario $p\in T$.

Theorem 9 implies also the following corollary proven in Appendix A.

Corollary 6.

If the conditions of Theorem 9 hold, then there exists a single pair of job permutations which is a J-solution for the problem $J2|l_{ij}\le p_{ij}\le u_{ij},n_i\le 2|C_{max}$ with job set $\mathcal{J}={\mathcal{J}}_1\cup {\mathcal{J}}_2\cup {\mathcal{J}}_{1,2}\cup {\mathcal{J}}_{2,1}$.

Note that the criterion for a single-element J-solution for the problem $F2|l_{ij}\le p_{ij}\le u_{ij}|C_{max}$ is given in Theorem 2.

5.2. Precedence Digraphs Determining a Minimal Dominant Set of Schedules

In Section 4.2, it is assumed that ${\mathcal{J}}_{1,2}={\mathcal{J}}_{1,2}^1\cup {\mathcal{J}}_{1,2}^2\cup {\mathcal{J}}_{1,2}^{*}$ and ${\mathcal{J}}_{2,1}={\mathcal{J}}_{2,1}^1\cup {\mathcal{J}}_{2,1}^2\cup {\mathcal{J}}_{2,1}^{*}$, i.e., ${\mathcal{J}}_{1,2}^0={\mathcal{J}}_{2,1}^0=\varnothing$. Based on the results presented in Section 4.2, we can determine a binary relation $A_{\prec }^{1,2}$ for the problem $F2|l_{ij}\le p_{ij}\le u_{ij}|C_{max}$ with job set ${\mathcal{J}}_{1,2}$ and a binary relation $A_{\prec }^{2,1}$ for this problem with job set ${\mathcal{J}}_{2,1}$. For job set ${\mathcal{J}}_{1,2}$, the binary relation $A_{\prec }^{1,2}$ determines the digraph $G_{1,2}=({\mathcal{J}}_{1,2},A_{\prec }^{1,2})$ with the vertex set ${\mathcal{J}}_{1,2}$ and the arc set $A_{\prec }^{1,2}$. For job set ${\mathcal{J}}_{2,1}$, the binary relation $A_{\prec }^{2,1}$ determines the digraph $G_{2,1}=({\mathcal{J}}_{2,1},A_{\prec }^{2,1})$ with the vertex set ${\mathcal{J}}_{2,1}$ and the arc set $A_{\prec }^{2,1}$.

Let us consider the problem $F2|l_{ij}\le p_{ij}\le u_{ij}|C_{max}$ with job set ${\mathcal{J}}_{1,2}$ and the corresponding digraph $G_{1,2}=({\mathcal{J}}_{1,2},A_{\prec }^{1,2})$ (the same results for the problem $F2|l_{ij}\le p_{ij}\le u_{ij}|C_{max}$ with job set ${\mathcal{J}}_{2,1}$ can be derived in a similar way).

Definition 5.

Two jobs, $J_x\in {\mathcal{J}}_{1,2}$ and $J_y\in {\mathcal{J}}_{1,2}$, $x\ne y$, are called conflict jobs if they are not in the relation $A_{\prec }^{1,2}$, i.e., $(J_x,J_y)\notin A_{\prec }^{1,2}$ and $(J_y,J_x)\notin A_{\prec }^{1,2}$.

Due to Definitions 2 and 3, for the conflict jobs $J_x\in {\mathcal{J}}_{1,2}$ and $J_y\in {\mathcal{J}}_{1,2}$, $x\ne y$, Inequalities (4) and (5) do not hold either for the case $v=x$ with $w=y$ or for the case $v=y$ with $w=x$.

Definition 6.

The subset ${\mathcal{J}}_x\subseteq {\mathcal{J}}_{1,2}$ is called a conflict set of jobs if, for any job $J_y\in {\mathcal{J}}_{1,2}\backslash {\mathcal{J}}_x$, either relation $(J_x,J_y)\in A_{\prec }^{1,2}$ or relation $(J_y,J_x)\in A_{\prec }^{1,2}$ holds for each job $J_x\in {\mathcal{J}}_x$ (provided that any proper subset of the set ${\mathcal{J}}_x$ does not possess such a property).

From Definition 6, it follows that the conflict set ${\mathcal{J}}_x$ is a minimal set (with respect to the inclusion). Obviously, there may exist several conflict sets in the set ${\mathcal{J}}_{1,2}$. (A conflict set of the jobs ${\mathcal{J}}_x\subseteq {\mathcal{J}}_{2,1}$ can be determined similarly.) Let the strict order $A_{\prec }^{1,2}$ for the problem $F2|l_{ij}\le p_{ij}\le u_{ij}|C_{max}$ with job set ${\mathcal{J}}_{1,2}$ be represented as follows:

$$J_1\prec J_2\prec \dots \prec J_k\prec \{J_{k+1},J_{k+2},\dots ,J_{k+r}\}\prec J_{k+r+1}\prec J_{k+r+2}\prec \dots \prec J_{m_{1,2}},$$

(10)

where all jobs between braces are conflict ones and each of these jobs is in relation $A_{\prec }^{1,2}$ with any job located outside the brackets in Relation (10). In such a case, an optimal order for processing jobs from the set $\{J_1,J_2,\dots ,J_k\}$ is determined as follows: $(J_1,J_2,\dots ,J_k)$.

Due to Theorem 5, we obtain that set $\mathsf{\Pi }\left(G_{1,2}\right)$ of the permutations generated by the digraph $G_{1,2}$ contains an optimal Johnson’s permutation for each vector $p_{1,2}$ of the durations of jobs from the set ${\mathcal{J}}_{1,2}$. Thus, due to Definition 1, the singleton $\left\{({\pi }_{1,2},{\pi }_{1,2})\right\}$, where ${\pi }_{1,2}\in \mathsf{\Pi }\left(G_{1,2}\right)$, is a J-solution for the problem $F2|l_{ij}\le p_{ij}\le u_{ij}|C_{max}$ with job set ${\mathcal{J}}_{1,2}$. Analogously, the singleton $\left\{({\pi }_{2,1},{\pi }_{2,1})\right\}$, where ${\pi }_{2,1}\in \mathsf{\Pi }\left(G_{2,1}\right)$, is a J-solution for the problem $F2|l_{ij}\le p_{ij}\le u_{ij}|C_{max}$ with job set ${\mathcal{J}}_{2,1}$. We can determine a dominant set of schedules for the problem $J2|l_{ij}\le p_{ij}\le u_{ij},n_i\le 2|C_{max}$ with job set $\mathcal{J}$ as follows: $<\mathsf{\Pi }\left(G_{1,2}\right),\mathsf{\Pi }\left(G_{2,1}\right)>\subseteq S$. The following theorems allow us to reduce a dominant set for the problem $J2|l_{ij}\le p_{ij}\le u_{ij},n_i\le 2|C_{max}$. We use the following notation: $L_2={\sum }_{J_i\in {\mathcal{J}}_{2,1}\cup {\mathcal{J}}_2}{l}_{i2}.$

Theorem 10.

Let the strict order $A_{\prec }^{1,2}$ over set ${\mathcal{J}}_{1,2}={\mathcal{J}}_{1,2}^{*}\cup {\mathcal{J}}_{1,2}^1\cup {\mathcal{J}}_{1,2}^2$ be determined as follows: $J_1\prec \dots \prec J_k\prec \{J_{k+1},J_{k+2},\dots ,J_{k+r}\}\prec J_{k+r+1}\prec \dots \prec J_{m_{1,2}}$. Consider the following inequality:

$$\sum _{i=1}^{k+r}{u}_{i1}\le L_2+\sum _{i=1}^k{l}_{i2},$$

(11)

If the above inequality holds, then set $S^{\prime }=<\left\{\pi \right\},\mathsf{\Pi }\left(G_{2,1}\right)>\subset S$ with $\pi \in \mathsf{\Pi }\left(G_{1,2}\right)$ is a dominant set of schedules for the problem $J2|l_{ij}\le p_{ij}\le u_{ij},n_i\le 2|C_{max}$ with job set $\mathcal{J}$.

Proof. 

We consider an arbitrary vector $p\in T$ of the job durations and an arbitrary permutation $\pi$ from the set $\mathsf{\Pi }\left(G_{1,2}\right)$. The set $\mathsf{\Pi }\left(G_{2,1}\right)$ contains at least one optimal Johnson’s permutation ${\pi }_{2,1}^{*}$ for the problem $F2|p_{2,1}|C_{max}$ with job set ${\mathcal{J}}_{2,1}$ and vector $p_{2,1}$ of the job durations (components of this vector are equal to the corresponding components of the vector p).

We consider a pair of job permutations $({\pi }^{\prime },{\pi }^{″})=((\pi ,{\pi }_1,{\pi }_{2,1}^{*}),$$({\pi }_{2,1}^{*},{\pi }_2,\pi ))\in S^{\prime }$ and show that it is an optimal pair of job permutations for the problem $J2|p,n_i\le 2|C_{max}$ with set $\mathcal{J}$ of the jobs and scenario p. To this end, we show that the value of $C_{max}({\pi }^{\prime },{\pi }^{″})=max\{c_1\left({\pi }^{\prime }\right),c_2\left({\pi }^{″}\right)\}$ cannot be reduced. Indeed, an idle time for machine $M_1$ is only possible if some job $J_j$ from the set ${\mathcal{J}}_{2,1}$ is processed on machine $M_2$ at the same time when job $J_j$ could be processed on machine $M_1$. In such a case, $c_1\left({\pi }^{\prime }\right)$ is equal to the makespan $C_{max}\left({\pi }_{2,1}^{*}\right)$ for the problem $F2|p_{2,1}|C_{max}$ with job set ${\mathcal{J}}_{2,1}$ and vector $p_{2,1}$ of the job durations. As permutation ${\pi }_{2,1}^{*}$ is a Johnson’s permutation, the value of

$$c_1\left({\pi }^{\prime }\right)=max\{\sum _{J_i\in {\mathcal{J}}_{1,2}\cup {\mathcal{J}}_{2,1}\cup {\mathcal{J}}_1}{p}_{i1},C_{max}\left({\pi }_{2,1}^{*}\right)\}$$

cannot be reduced. In the beginning of the permutation $\pi$, the jobs of set $\{J_1,J_2,\dots ,J_k\}$ are arranged in the Johnson’s order. Thus, if machine $M_2$ has an idle time while processing these jobs, this idle time cannot be reduced. From Inequality (11), it follows that machine $M_2$ has no idle time while processing jobs from the conflict set.

In the end of the permutation $\pi$, jobs of set $\{J_{k+r+1},\dots ,J_{m_{1,2}}\}$ are arranged in Johnson’s order. Therefore, if machine $M_2$ has an idle time while processing these jobs, this idle time cannot be reduced. Thus, the value of $c_2\left({\pi }^{″}\right)$ cannot be reduced by changing the order of jobs in the conflict set.

We obtain the qualities $C_{max}({\pi }^{\prime },{\pi }^{″})=max\{c_1\left({\pi }^{\prime }\right),c_2\left({\pi }^{″}\right)\}=C_{max}.$ The pair of job permutations $({\pi }^{\prime },{\pi }^{″})=((\pi ,{\pi }_1,{\pi }_{2,1}^{*}),({\pi }_{2,1}^{*},{\pi }_2,\pi ))$ is optimal for the problem $J2|p,n_i\le 2|C_{max}$ with scenario $p\in T$. Thus, set $S^{\prime }=<\left\{\pi \right\},\mathsf{\Pi }\left(G_{2,1}\right)>$ contains an optimal pair of job permutations for the problem $J2|p,n_i\le 2|C_{max}$ with scenario $p\in T$. As vector p is an arbitrary vector in set T, set $S^{\prime }$ contains an optimal pair of job permutations for each vector from set T. Due to Definition 4, set $S^{\prime }$ is a dominant set of schedules for the problem $J2|l_{ij}\le p_{ij}\le u_{ij},n_i\le 2|C_{max}$ with job set $\mathcal{J}$. □

Theorem 11.

Let the partial strict order $A_{\prec }^{1,2}$ over set ${\mathcal{J}}_{1,2}={\mathcal{J}}_{1,2}^{*}\cup {\mathcal{J}}_{1,2}^1\cup {\mathcal{J}}_{1,2}^2$ be determined as follows: $J_1\prec \dots \prec J_k\prec \{J_{k+1},J_{k+2},\dots ,J_{k+r}\}\prec J_{k+r+1}\prec \dots \prec J_{m_{1,2}}$. Consider the following inequality:

$$u_{k+s,1}\le L_2+\sum _{i=1}^{k+s-1}(l_{i2}-u_{i1})$$

(12)

If the above inequality holds for all $s\in \{1,2,\dots ,r\},$ then the set $S^{\prime }=<\left\{\pi \right\},S_{2,1}>$, where $\pi =(J_1,\dots ,J_{k-1},J_k,J_{k+1},J_{k+2},\dots ,J_{k+r},$$J_{k+r+1},\dots ,J_{m_{1,2}})\in \mathsf{\Pi }\left(G_{1,2}\right)$, is a dominant set for the problem $J2|l_{ij}\le p_{ij}\le u_{ij},n_i\le 2|C_{max}$ with job set $\mathcal{J}$.

Proof. 

We consider an arbitrary scenario $p\in T$ and a pair of job permutations $({\pi }^{\prime },{\pi }^{″})=((\pi ,{\pi }_1,{\pi }_{2,1}^{*}),$ $({\pi }_{2,1}^{*},{\pi }_2,\pi ))\in S^{\prime }$, where ${\pi }_{2,1}^{*}\in S_{2,1}$ is a Johnson’s permutation of the jobs from the set ${\mathcal{J}}_{2,1}$ with vector $p_{2,1}$ of the job durations (components of this vector are equal to the corresponding components of vector p). We next show that this pair of job permutations $({\pi }^{\prime },{\pi }^{″})$ is optimal for the individual deterministic problem $J2|p,n_i\le 2|C_{max}$ with scenario p, i.e., $C_{max}({\pi }^{\prime },{\pi }^{″})=C_{max}$.

If conditions of Theorem 11 hold, then machine $M_2$ processes jobs from the conflict set $\{J_{k+1},J_{k+2},\dots ,J_{k+r}\}$ without idle times. At the initial time $t=0$, machine $M_1$ begins to process jobs from the permutation $\pi$ without idle times. Let a time moment $t_1$ be as follows: $t_1={\sum }_{i=1}^{k+1}{p}_{i1}.$ At the time moment $t_1$, job $J_{k+1}$ is ready for processing on machine $M_2$.

On the other hand, at the time $t=0$, machine $M_2$ begins to process jobs from the set ${\mathcal{J}}_{2,1}\cup {\mathcal{J}}_2$ without idle times and then jobs from the permutation $(J_1,J_2,\dots ,J_{k+1})$. Let $t_2$ denote the first time moment when machine $M_2$ is ready for processing job $J_{k+1}$. Obviously, the following inequality holds: $t_2\ge L_2+{\sum }_{i=1}^{k+1}{p}_{i2}.$ From the condition in Inequality (12) with $s=1$, we obtain inequality ${\sum }_{i=1}^{k+1}{u}_{i1}\le L_2+{\sum }_{i=1}^k{l}_{i2}.$

Therefore, the following relations hold:

$$t_1=\sum _{i=1}^{k+1}{p}_{i1}\le \sum _{i=1}^{k+1}{u}_{i1}\le L_2+\sum _{i=1}^k{l}_{i2}\le L_2+\sum _{i=1}^{k+1}{p}_{i2}=t_2.$$

Machine $M_2$ processes job $J_{k+1}$ without an idle time between job $J_k$ and job $J_{k+1}$.

Analogously, using $s\in \{2,3,\dots ,r\}$, one can show that machine $M_2$ processes jobs from the conflict set $\{J_{k+1},J_{k+2},\dots ,J_{k+r}\}$ without idle times between jobs $J_{k+1}$ and $J_{k+2}$, between jobs $J_{k+2}$ and $J_{k+3}$, and so on to between jobs $J_{k+r-1}$ and $J_{k+r}$. To end this proof, we have to show that the value of $C_{max}({\pi }^{\prime },{\pi }^{″})=max\{c_1\left({\pi }^{\prime }\right),c_2\left({\pi }^{″}\right)\}$ cannot be reduced.

An idle time for machine $M_1$ is only possible between some jobs from the set ${\mathcal{J}}_{2,1}$. However, the permutation ${\pi }_{2,1}^{*}$ is a Johnson’s permutation of the jobs from the set ${\mathcal{J}}_{2,1}$ for the vector $p_{2,1}$ of the job durations. Therefore, the value of $c_1\left({\pi }^{\prime }\right)$ cannot be reduced. On the other hand, in the permutation $\pi$, all jobs $J_1,J_2,\dots ,J_k$ and all jobs $J_{k+r+1},\dots ,J_{m_{1,2}}$ are arranged in Johnson’s orders. Therefore, if machine $M_2$ has an idle time while processing these jobs, this idle time cannot be reduced. It is clear that machine $M_2$ has no idle time while processing jobs from the conflict set. Thus, the value of $c_2\left({\pi }^{″}\right)$ cannot be reduced by changing the order of jobs from the conflict set. We obtain the equalities $C_{max}({\pi }^{\prime },{\pi }^{″})=max\{c_1\left({\pi }^{\prime }\right),c_2\left({\pi }^{″}\right)\}=C_{max}.$

It is shown that the pair of job permutations $({\pi }^{\prime },{\pi }^{″})=((\pi ,{\pi }_1,{\pi }_{2,1}^{*}),({\pi }_{2,1}^{*},{\pi }_2,\pi ))\in S^{\prime }$ is optimal for the problem $J2|p,n_i\le 2|C_{max}$ with vector $p\in T$ of job durations. As vector p is an arbitrary one in set T, the set $S^{\prime }$ contains an optimal pair of job permutations for each scenario from set T. Due to Definition 4, the set $S^{\prime }$ is a dominant set of schedules for the problem $J2|l_{ij}\le p_{ij}\le u_{ij},n_i\le 2|C_{max}$ with job set $\mathcal{J}$. □

The proof of the following theorem is given in Appendix A.

Theorem 12.

Let the partial strict order $A_{\prec }^{1,2}$ over set ${\mathcal{J}}_{1,2}={\mathcal{J}}_{1,2}^{*}\cup {\mathcal{J}}_{1,2}^1\cup {\mathcal{J}}_{1,2}^2$ have the form $J_1\prec \dots \prec J_k\prec \{J_{k+1},J_{k+2},\dots ,J_{k+r}\}\prec J_{k+r+1}\prec \dots \prec J_{m_{1,2}}$. If inequalities

$$\sum _{i=r-s+2}^{r+1}{l}_{k+i,1}\ge \sum _{j=r-s+1}^r{u}_{k+j,2}$$

(13)

hold for all indexes $s\in \{1,2,\dots ,r\}$, then the set $S^{\prime }=<\left\{\pi \right\},S_{2,1}>$, where $\pi =(J_1,\dots ,J_{k-1},J_k,$$J_{k+1},J_{k+2},\dots ,J_{k+r},J_{k+r+1},\dots ,J_{m_{1,2}})\in \mathsf{\Pi }\left(G_{1,2}\right)$, is a dominant set of pairs of permutations for the problem $J2|l_{ij}\le p_{ij}\le u_{ij},n_i\le 2|C_{max}$ with job set $\mathcal{J}$.

Similarly, one can prove sufficient conditions for the existence of an optimal job permutation for the problem $F2|l_{ij}\le p_{ij}\le u_{ij}|C_{max}$ with job set ${\mathcal{J}}_{2,1}$, when the partial strict order $A_{\prec }^{2,1}$ on the set ${\mathcal{J}}_{2,1}={\mathcal{J}}_{2,1}^{*}\cup {\mathcal{J}}_{2,1}^1\cup {\mathcal{J}}_{2,1}^2$ has the following form: $J_1\prec \dots \prec J_k\prec \{J_{k+1},J_{k+2},\dots ,J_{k+r}\}\prec J_{k+r+1}\prec \dots \prec J_{m_{2,1}}$.

To apply Theorems 11 and 12, one can construct a job permutation that satisfies the strict order $A_{\prec }^{1,2}$. Then, one can check the conditions of Theorems 11 and 12 for the constructed permutation. If the set of jobs $\{J_1,J_2,\dots ,J_k\}$ is empty in the constructed permutation, one needs to check conditions of Theorem 12. If the set of jobs $\{J_{k+r+1},\dots ,J_{m_{1,2}}\}$ is empty, one needs to check the conditions of Theorem 11. It is needed to construct only one permutation to check Theorem 11 and only one permutation to check Theorem 12.

5.3. Two Illustrative Examples

Example 1.

We consider the uncertain job-shop scheduling problem $J2|l_{ij}\le p_{ij}\le u_{ij},n_i\le 2|C_{max}$ with lower and upper bounds of the job durations given in

Table 1. Input data for Example 1.

${\mathit{J}}_{\mathit{i}}$	${\mathit{l}}_{\mathit{i}1}$	${\mathit{u}}_{\mathit{i}1}$	${\mathit{l}}_{\mathit{i}2}$	${\mathit{u}}_{\mathit{i}2}$
$J_1$	6	7	6	7
$J_2$	8	9	5	6
$J_3$	7	9	5	6
$J_4$	2	3	-	-
$J_5$	-	-	16	20
$J_6$	1	3	3	4
$J_7$	1	3	3	4
$J_8$	1	3	3	4

.

These bounds determine the set T of possible scenarios. In Example 1, jobs $J_1$, $J_2$, and $J_3$ have the machine route $(M_1,M_2)$; jobs $J_6$, $J_7$, and $J_8$ have the machine route $(M_2,M_1)$; and job $J_4$ (job $J_5$, respectively) has to be processed only on machine $M_1$ (on machine $M_2$, respectively). Thus, ${\mathcal{J}}_{1,2}=\{J_1,J_2,J_3\}$, ${\mathcal{J}}_{2,1}=\{J_6,J_7,J_8\}$, ${\mathcal{J}}_1=\left\{J_4\right\}$, ${\mathcal{J}}_2=\left\{J_5\right\}$.

We check the conditions of Theorem 7 for a single pair of job permutations, which is optimal for all scenarios T. For the given jobs, the condition in Inequalities (7) of Theorem 7 holds due to the following relations:

${\sum }_{J_i\in {\mathcal{J}}_{1,2}}{u}_{i1}=u_{1,1}+u_{2,1}+u_{3,1}=7+9+9=25\le {\sum }_{J_i\in {\mathcal{J}}_{2,1}\cup {\mathcal{J}}_2}{l}_{i2}=l_{6,2}+l_{7,2}+l_{8,2}+l_{5,2}=3+3+3+16=25;$

${\sum }_{J_i\in {\mathcal{J}}_{1,2}}{l}_{i2}=l_{1,2}+l_{2,2}+l_{3,2}=6+5+5=16\ge {\sum }_{J_i\in {\mathcal{J}}_{2,1}\cup {\mathcal{J}}_1}{u}_{i1}=u_{6,1}+u_{7,1}+u_{8,1}+u_{4,1}=3+3+3+3=12.$

Due to Theorem 7, the order of jobs from the set ${\mathcal{J}}_{1,2}=\{J_1,J_2,J_3\}$ and the order of jobs from the set ${\mathcal{J}}_{2,1}=\{J_6,J_7,J_8\}$ may be arbitrary in the optimal pair of job permutations for the problem $J2|l_{ij}\le p_{ij}\le u_{ij},n_i\le 2|C_{max}$ under consideration. Thus, any pair of job permutations $({\pi }^{\prime },{\pi }^{″})\in S$ is a single-element dominant set $DS\left(T\right)=\left\{({\pi }^{\prime },{\pi }^{″})\right\}$ for Example 1.

Example 2.

Let us now consider the problem $J2|l_{ij}\le p_{ij}\le u_{ij},n_i\le 2|C_{max}$ with numerical input data given in Table 1 with the following two exceptions: $l_{5,2}=2$ and $u_{5,2}=3$.

We check the condition in Inequalities (7) of Theorem 7 and obtain

$$\begin{array}{c}\sum _{J_i\in {\mathcal{J}}_{1,2}}{u}_{i1}=u_{1,1}+u_{2,1}+u_{3,1}=7+9+9=25\nleqq \sum _{J_i\in {\mathcal{J}}_{2,1}\cup {\mathcal{J}}_2}{l}_{i2}=l_{6,2}+l_{7,2}+l_{8,2}+l_{5,2}=3+3+3+2=11.\end{array}$$

(14)

Thus, the condition of Inequalities (7) does not hold for Example 2. We check the condition of Inequalities (8) of Theorem 7 and obtain

$$\begin{array}{c}\sum _{J_i\in {\mathcal{J}}_{2,1}}{u}_{i2}=u_{6,2}+u_{7,2}+u_{8,2}=4+4+4=12\le \sum _{J_i\in {\mathcal{J}}_{1,2}\cup {\mathcal{J}}_1}{l}_{i1}=l_{1,1}+l_{2,1}+l_{3,1}+l_{4,1}=6+8+7+2=23.\end{array}$$

(15)

However, we see that the condition of Equation (8) does not hold:

${\sum }_{J_i\in {\mathcal{J}}_{2,1}}{l}_{i1}=l_{6,1}+l_{7,1}+l_{8,1}=1+1+1=3\ngeqq {\sum }_{J_i\in {\mathcal{J}}_{1,2}\cup {\mathcal{J}}_2}{u}_{i2}=u_{1,2}+u_{2,2}+u_{3,2}+u_{5,2}=7+6+6+3=22.$

From Equation (14), it follows that the condition of Inequalities (9) of Corollary 3 does not hold. On the other hand, due to Equation (15), conditions of Corollary 4 hold. Thus, the order for processing jobs from set ${\mathcal{J}}_{2,1}\subseteq \mathcal{J}$ in the optimal schedule $({\pi }^{\prime },{\pi }^{″})=\left(\right({\pi }_{1,2},{\pi }_1,$${\pi }_{2,1}),({\pi }_{2,1},{\pi }_2,{\pi }_{1,2}))$ for the problem $J2|l_{ij}\le p_{ij}\le u_{ij},n_i\le 2|C_{max}$ may be arbitrary. One can fix permutation ${\pi }_{2,1}$ with the increasing order of the indexes of their jobs: ${\pi }_{2,1}=(J_6,J_7,J_8)$. Since the orders of jobs from the sets ${\mathcal{J}}_1$ and ${\mathcal{J}}_2$ are fixed in the optimal schedule (Remark 1), i.e., ${\pi }_1=\left(J_4\right)$ and ${\pi }_2=\left(J_5\right)$, we need to determine the order for processing jobs in set ${\mathcal{J}}_{1,2}$. To this end, we consider the problem $F2|l_{ij}\le p_{ij}\le u_{ij}|C_{max}$ with job set ${\mathcal{J}}_{1,2}$. We see that conditions of Theorem 2 do not hold for the jobs in set ${\mathcal{J}}_{1,2}$ since $J_1\in {\mathcal{J}}_{1,2}^{*}$, $J_2\in {\mathcal{J}}_{1,2}^2$, and $J_3\in {\mathcal{J}}_{1,2}^2$; however the following inequalities hold: $u_{2,2}>l_{3,2}$ and $u_{3,2}>l_{2,2}$.

We next construct the binary relation $A_{\prec }^{1,2}$ over set ${\mathcal{J}}_{1,2}$ based on Definition 3 and Theorem 1. Due to checking Inequalities (4) and (5), we conclude that the inequality in Equation (5) holds for the pair of jobs $J_1$ and $J_2$. We obtain the relation $J_1\prec J_2$. Analogously, we obtain the relation $J_1\prec J_3$. For the pair of jobs $J_2$ and $J_3$, neither Inequality (4) nor Inequality (5) hold. Therefore, the partial strict order $A_{\prec }^{1,2}$ over set ${\mathcal{J}}_{1,2}$ has the following form: $J_1\prec \{J_2,J_3\}$. The job set $\{J_2,J_3\}$ is a conflict set of these jobs (Definition 6).

Let us check whether the sufficient conditions given in Section 5.2 hold.

We check the conditions of Theorem 10 for the jobs from set ${\mathcal{J}}_{1,2}$. For $k=1$ and $r=2$, we obtain the following equalities: $L_2={\sum }_{J_i\in {\mathcal{J}}_{2,1}\cup {\mathcal{J}}_2}{l}_{i2}=l_{6,2}+l_{7,2}+l_{8,2}+l_{5,2}=3+3+3+2=11.$ The condition of Theorem 10 does not hold since the following relations hold:

$$\sum _{i=1}^{k+r}{u}_{i1}=u_{1,1}+u_{2,1}+u_{3,1}=7+9+9=25\nleqq L_2+\sum _{i=1}^k{l}_{i2}=L_2+l_{1,2}=11+6=17.$$

For checking the conditions of Theorem 11, we need to check both permutations of the jobs from set ${\mathcal{J}}_{1,2}$, which satisfy the partial strict order $A_{\prec }^{1,2}$: $\mathsf{\Pi }\left({\mathcal{G}}_{1,2}\right)=\{{\pi }_{1,2}^1,{\pi }_{1,2}^2\}$, where ${\pi }_{1,2}^1=\{J_1,J_2,J_3\}$ and ${\pi }_{1,2}^2=\{J_1,J_3,J_2\}$.

We consider permutation ${\pi }_{1,2}^1$. As in the previous case, $L_2=11$, $k=1$, $r=2$, and we must consider two inequalities in the condition in Equaiton (12) with $s=1$ and $s=2$. For $s=1$, we obtain the following:

$$u_{1+1,1}=u_{2,1}=9\le L_2+\sum _{i=1}^{1+1-1}(l_{i2}-u_{i1})=L_2+\sum _{i=1}^1(l_{i2}-u_{i1})=11+(l_{1,2}-u_{1,1})=11+(6-7)=10.$$

However, for $s=2$, we obtain

$$u_{1+2,1}=u_{3,1}=9\nleqq L_2+\sum _{i=1}^{1+2-1}(l_{i2}-u_{i1})=L_2+\sum _{i=1}^2(l_{i2}-u_{i1})$$

$$=11+(l_{1,2}-u_{1,1})+(l_{2,2}-u_{2,1})=11+(6-7)+(5-9)=6.$$

Thus, the conditions of Theorem 11 do not hold for permutation ${\pi }_{1,2}^1$.

We consider permutation ${\pi }_{1,2}^2$, where $J_{k+1}=J_3$ and $J_{k+2}=J_2$. Again, we must test the two inequalities in Equation (12), where either $s=1$ or $s=2$. For $s=1$, we obtain

$$u_{k+1,1}=u_{3,1}=9\le L_2+\sum _{i=1}^{k+1-1}(l_{i2}-u_{i1})=L_2+\sum _{i=1}^1(l_{i2}-u_{i1})=11+(l_{1,2}-u_{1,1})=11+(6-7)=10.$$

However, for $s=2$, we obtain

$$u_{k+2,1}=u_{2,1}=9\nleqq L_2+\sum _{i=1}^{k+2-1}(l_{i2}-u_{i1})=L_2+\sum _{i=1}^{k+1}(l_{i2}-u_{i1})=11+(l_{1,2}-u_{1,1})+(l_{3,2}-u_{3,1})$$

$$=11+(6-7)+(5-9)=6.$$

Thus, the conditions of Theorem 11 do not hold for permutation ${\pi }_{1,2}^2$.

Note that we do not check the conditions of Theorem 12 since the conflict set of jobs $\{J_2,J_3\}$ is located at the end of the partial strict order $A_{\prec }^{1,2}$. We conclude that none of the proven sufficient conditions are satisfied for a schedule optimality. Thus, there does not exist a pair of permutations of the jobs in set $\mathcal{J}={\mathcal{J}}_{1,2}\cup {\mathcal{J}}_{2,1}\cup {\mathcal{J}}_1\cup {\mathcal{J}}_2$ which is optimal for any scenario $p\in T$. The J-solution $S\left(T\right)$ for Example 2 consists of the following two pairs of job permutations: $\{({\pi }_1^{\prime },{\pi }_1^{″}),({\pi }_2^{\prime },{\pi }_2^{″})\}=S\left(T\right)$, where

$${\pi }_1^{\prime }=({\pi }_{1,2}^1,{\pi }_1,{\pi }_{2,1})=(J_1,J_2,J_3,J_4,J_6,J_7,J_8),{\pi }_1^{″}=({\pi }_{2,1},{\pi }_2,{\pi }_{1,2}^1)=(J_6,J_7,J_8,J_5,J_1,J_2,J_3),$$

$${\pi }_2^{\prime }=({\pi }_{1,2}^2,{\pi }_1,{\pi }_{2,1})=(J_1,J_3,J_2,J_4,J_6,J_7,J_8),{\pi }_2^{″}=({\pi }_{2,1},{\pi }_2,{\pi }_{1,2}^2)=(J_6,J_7,J_8,J_5,J_1,J_3,J_2).$$

We next show that none of these two pairs of job permutations is optimal for all scenarios $p\in T$ using the following two scenarios: $p^{\prime }=(7,6,9,5,9,6,2,0,0,2,1,3,1,3,1,3)\in T$ and $p^{″}=(7,6,9,6,9,5,2,0,0,2,1,3,1,3,1,3)\in T.$ For scenario $p^{\prime }$, only pair of permutations $({\pi }_2^{\prime },{\pi }_2^{″})$ is optimal with $C_{max}({\pi }_2^{\prime },{\pi }_2^{″})=30$ since $C_{max}({\pi }_1^{\prime },{\pi }_1^{″})=31>30$. On the other hand, for scenario $p^{″}$, only the pair of permutations $({\pi }_1^{\prime },{\pi }_1^{″})$ is optimal with $C_{max}({\pi }_1^{\prime },{\pi }_1^{″})=30$ since $C_{max}({\pi }_2^{\prime },{\pi }_2^{″})=31>30$.

Note that the whole set S of the semi-active schedules has the cardinality $\left|S\right|=m_{1,2}!·m_{2,1}!=3!·3!=6·6=36$. Thus, for solving Example 2, one needs to consider only two pairs of job permutations $\{({\pi }_1^{\prime },{\pi }_1^{″}),({\pi }_2^{\prime },{\pi }_2^{″})\}=S\left(T\right)\subset S$ instead of 36 semi-active schedules.

5.4. An Algorithm for Checking Conditions for the Existence of a Single-Element Dominant Set

We describe Algorithm 1 for checking the existence of an optimal permutation for the problem $F2|l_{ij}\le p_{ij}\le u_{ij}|C_{max}$ with job set ${\mathcal{J}}_{1,2}$ if the partial strict order $A_{\prec }^{1,2}$ on the set ${\mathcal{J}}_{1,2}$ has the following form: $J_1\prec \dots \prec J_k\prec \{J_{k+1},J_{k+2},\dots ,J_{k+r}\}\prec J_{k+r+1}\prec \dots \prec J_{m_{1,2}}$. Algorithm 1 considers a set of conflict jobs and checks whether the sufficient conditions given in Section 5.2 hold. For a conflict set of jobs, it is needed to construct two permutations and to check the condition in Inequality (12) for the first permutation and the condition in Inequality (13) for the second one. If at least one of these conditions holds, Algorithm 1 constructs a permutation which is optimal for the problem $F2|l_{ij}\le p_{ij}\le u_{ij}|C_{max}$ with any scenario $p\in T$.

Obviously, testing the conditions of Theorems 11 and 12 takes $O\left(r\right)$, where the conflict set contains r jobs. The construction of the permutation of r jobs takes $O(rlogr)$. Therefore, the total complexity of Algorithm 1 is $O(rlogr)$.

Remark 3.

If Algorithm 1 is completed at Step 7 (STOP 1), we suggest to consider a set of conflict jobs $\{J_{k+1},J_{k+2},\dots ,J_{k+r}\}$ and construct a Johnson’s permutation for the deterministic problem $F2|p^{\prime }|C_{max}$ with job set ${\mathcal{J}}^{\prime }=\{J_{k+1},J_{k+2},\dots J_{k+r}\}$, where vector $p^{\prime }=(p_{k+1,1}^{\prime },p_{k+1,2}^{\prime },\dots p_{k+r,1}^{\prime },p_{k+r,2}^{\prime })$ of the durations of conflict jobs $\{J_{k+1},J_{k+2},\dots J_{k+r}\}$ is calculated for each operation $O_{ij}$ of the conflict job $J_i\in \{J_{k+1},J_{k+2},\dots J_{k+r}\}$ on the corresponding machine $M_j\in \mathcal{M}$ as folows:

$$p_{ij}^{\prime }=(u_{ij}+l_{ij})/2$$

(16)

Theorem 11 and Theorem 12 imply the following claim.

Corollary 7.

Algorithm 1 constructs a permutation ${\pi }^{*}$ either satisfying conditions of Theorem 11 or Theorem 12 (such permutation ${\pi }^{*}$ is optimal for the problem $F2|l_{ij}\le p_{ij}\le u_{ij}|C_{max}$ with job set ${\mathcal{J}}_{1,2}$ and any scenario $p\in T$) or establishes that an optimal job permutation for the problem $F2|l_{ij}\le p_{ij}\le u_{ij}|C_{max}$ with any scenario $p\in T$ does not exist.

The set of jobs ${\mathcal{J}}_{2,1}$ for the problem $F2|l_{ij}\le p_{ij}\le u_{ij}|C_{max}$ with job set $\mathcal{J}={\mathcal{J}}_{2,1}$ can be tested similarly to the set of jobs ${\mathcal{J}}_{1,2}$.

Algorithm 1: Checking conditions for the existence of a single-element dominant set of schedules for the problem $F2|l_{ij}\le p_{ij}\le u_{ij}|C_{max}$

Input:  Segments $[l_{ij},u_{ij}]$ for all jobs $J_i\in \mathcal{J}$ and machines $M_j\in \mathcal{M}$, a partial strict order $A_{\prec }^{1,2}$ on the set ${\mathcal{J}}_{1,2}={\mathcal{J}}_{1,2}^{*}\cup {\mathcal{J}}_{1,2}^1\cup {\mathcal{J}}_{1,2}^2$ in the form $J_1\prec \dots \prec J_k\prec$$\{J_{k+1},J_{k+2},\dots ,$$J_{k+r}\}\prec$$J_{k+r+1}\prec \dots \prec J_{m_{1,2}}$. Output:  EITHER an optimal job permutation for the problem    $F2|l_{ij}\le p_{ij}\le u_{ij}|C_{max}$ with job set ${\mathcal{J}}_{1,2}$ and any scenario $p\in T$, (see STOP 0) OR there no permutation ${\pi }_{1,2}$ of jobs from set ${\mathcal{J}}_{1,2}$, which is optimal    for all scenarios $p\in T$, (see STOP 1). Step 1: Set ${\delta }_s=l_{k+s,2}-u_{k+s,1}$ for all $s\in \{1,2,\dots ,r\}$   construct a partition of the set of conflicting jobs into two subsets $X_1$ and $X_2$,   where $J_{k+s}\in X_1$ if ${\delta }_s\ge 0$, and $J_{k+s}\in X_2$, otherwise. Step 2: Construct a permutation ${\pi }^1=(J_1,J_2,\dots ,J_k,{\pi }_1,{\pi }_2,J_{k+r+1},\dots ,J_{m_{1,2}})$, where the permutation   ${\pi }_1$ contains jobs from the set $X_1$ in the non-decreasing order of the values $u_{k+i,1}$ and the   permutation ${\pi }_2$ contains jobs from the set $X_2$ in the non-increasing order of the values   $l_{k+i,2}$, renumber jobs in the permutations ${\pi }_1$ and ${\pi }_2$ based on their orders. Step 3: IF for the permutation ${\pi }^1$ conditions of Theorem 11 hold THEN GOTO step 8. Step 4: Set ${\delta }_s=l_{k+s,1}-u_{k+s,2}$ for all $s\in \{1,2,\dots ,r\}$   construct a partition of the set of conflicting jobs into two subsets   $Y_1$ and $Y_2$, where $J_{k+s}\in Y_1$ if ${\delta }_s\ge$ 0, and $J_{k+s}\in Y_2$, otherwise. Step 5: Construct a permutation ${\pi }^2=(J_1,J_2,\dots ,J_k,{\pi }_2,{\pi }_1,J_{k+r+1},\dots ,J_{m_{1,2}})$, where the permutation   ${\pi }_1$ contains jobs from the set $Y_1$ in the non-increasing order of the values $u_{k+i,2}$, and the   permutation ${\pi }_2$ contains jobs from the set $Y_2$ in the non-decreasing order of the   values $l_{k+i,1}$, renumber jobs in the permutations ${\pi }_1$ and ${\pi }_2$ based on their orders. Step 6: IF for the permutation ${\pi }^2$ conditions of Theorem 12 hold THEN GOTO step 9. Step 7: ELSE there is no a single dominant permutation for problem   $F2|l_{ij}\le p_{ij}\le u_{ij}|C_{max}$ with job set ${\mathcal{J}}_{1,2}$ and any scenario $p\in T$ STOP 1. Step 8: RETURN permutation ${\pi }^1,$ which is a single dominant permutation   for the problem $F2|l_{ij}\le p_{ij}\le u_{ij}|C_{max}$ with job set ${\mathcal{J}}_{1,2}$ STOP 0. Step 9: RETURN permutation ${\pi }^2,$ which is a single dominant permutation   for the problem $F2|l_{ij}\le p_{ij}\le u_{ij}|C_{max}$ with job set ${\mathcal{J}}_{1,2}$ STOP 0.

6. Algorithms for Constructing a Small Dominant Set of Schedules for the Problem $\mathit{J}\mathbf{2}|{\mathit{l}}_{\mathit{i}\mathit{j}}\le {\mathit{p}}_{\mathit{i}\mathit{j}}\le {\mathit{u}}_{\mathit{i}\mathit{j}},{\mathit{n}}_{\mathit{i}}\le \mathbf{2}|{\mathit{C}}_{\mathit{m}\mathit{a}\mathit{x}}$

In this section, we describe Algorithm 2 for constructing a small dominant set $DS\left(T\right)$ of schedules for the problem $J2|l_{ij}\le p_{ij}\le u_{ij},n_i\le 2|C_{max}$. Algorithm 2 is developed for use at the off-line phase of scheduling (before processing any job from the set $\mathcal{J}$). Based on the initial data, Algorithm 2 checks the conditions of Theorem 7 for a single optimal pair of job permutations for the uncertain problem $J2|l_{ij}\le p_{ij}\le u_{ij},n_i\le 2|C_{max}$. If the sufficient conditions of Theorem 7 do not hold, Algorithm 2 proceeds to consider the problem $F2|l_{ij}\le p_{ij}\le u_{ij}|C_{max}$ with job set ${\mathcal{J}}_{1,2}$ and the problem $F2|l_{ij}\le p_{ij}\le u_{ij}|C_{max}$ with job set ${\mathcal{J}}_{2,1}$. For each of these problems, the conditions of Theorem 2 are checked. If these conditions do not hold, then strict orders of the jobs $\mathcal{J}$ based on Inequalities (4) and (5) are constructed. In this general case, Algorithm 2 constructs a partial strict order $A_{\prec }^{1,2}$ of the jobs from set ${\mathcal{J}}_{1,2}$ and a partial strict order $A_{\prec }^{2,1}$ of the jobs from set ${\mathcal{J}}_{2,1}$. Each of these partial orders may contain one or several conflict sets of jobs. For each such conflict set of jobs, Algorithm 2 checks whether the sufficient conditions given in Section 5.2 hold. Thus, if some sufficient conditions for a schedule optimality presented in Section 4 and Section 5 are satisfied, then there exists a pair of permutations of jobs from set $\mathcal{J}$ which is optimal for any scenario $p\in T$. Algorithm 2 constructs such a pair of job permutations $\left\{({\pi }^{\prime },{\pi }^{″})\right\}=DS\left(T\right)$. Otherwise, the precedence digraphs determining a minimal dominant set $DS\left(T\right)$ of schedules is constructed by Algorithm 2. The more job pairs are involved in the binary relations $A_{\prec }^{1,2}$ and $A_{\prec }^{2,1}$, the more job permutations will be deleted from set S while constructing a J-solution $S\left(T\right)\subseteq S$ for the problems $F2|l_{ij}\le p_{ij}\le u_{ij}|C_{max}$ with job sets ${\mathcal{J}}_{1,2}$ and ${\mathcal{J}}_{2,1}$.

Algorithm 2: Construction of a small dominant set of schedules for the problem $J2|l_{ij}\le p_{ij}\le u_{ij},n_i\le 2|C_{max}$

Input:  Lower bounds $l_{ij}$ and upper bounds $u_{ij}$, $0<l_{ij}\le u_{ij}$, of the durations of all operations $O_{ij}$ of jobs $J_i\in \mathcal{J}$ processed on machines $M_j\in \mathcal{M}=\{M_1,M_2\}$. Output:  EITHER pair of permutations $({\pi }^{\prime },{\pi }^{″})=(({\pi }_{1,2},{\pi }_1,{\pi }_{2,1}),({\pi }_{2,1},{\pi }_2,{\pi }_{1,2}))$,    where ${\pi }^{\prime }$ is a permutation of jobs from set ${\mathcal{J}}_{1,2}\cup {\mathcal{J}}_1\cup {\mathcal{J}}_{2,1}$ on machine    $M_1$, ${\pi }^{″}$ is a permutation of jobs from set ${\mathcal{J}}_{1,2}\cup {\mathcal{J}}_2\cup {\mathcal{J}}_{2,1}$ on machine $M_2$,    such that $\left\{({\pi }^{\prime },{\pi }^{\prime \prime })\right\}=DS\left(T\right)$, (see STOP 0), OR permutation ${\pi }_{2,1}$ of jobs from set ${\mathcal{J}}_{2,1}$ on machines $M_1$ and $M_2$ and    a partial strict order $A_{\prec }^{1,2}$ of jobs from set ${\mathcal{J}}_{1,2}$, OR permutation ${\pi }_{1,2}$ of jobs from set ${\mathcal{J}}_{1,2}$ on machines $M_1$ and $M_2$ and    a partial strict order $A_{\prec }^{2,1}$ of jobs from set ${\mathcal{J}}_{2,1}$, OR a partial strict order $A_{\prec }^{1,2}$ of jobs from set ${\mathcal{J}}_{1,2}$ and    a partial strict order $A_{\prec }^{2,1}$ of jobs from set ${\mathcal{J}}_{2,1}$, (see STOP 1). Step 1: Determine a partition $\mathcal{J}={\mathcal{J}}_1\cup {\mathcal{J}}_2\cup {\mathcal{J}}_{1,2}\cup {\mathcal{J}}_{2,1}$ of the job set $\mathcal{J}$,   permutation ${\pi }_1$ of jobs from set ${\mathcal{J}}_1$ and permutation ${\pi }_2$ of jobs from   set ${\mathcal{J}}_2$, arrange the jobs in the increasing order of their indexes. Step 2: IF the first inequality in condition (7) of Theorem 7 holds THEN BEGIN   Construct a permutation ${\pi }_{1,2}$ of jobs from set ${\mathcal{J}}_{1,2}$,     arrange them in the increasing order of their indexes;   IF the second inequality in condition (7) of Theorem 7 holds     THEN construct a permutation ${\pi }_{2,1}$ of jobs from set ${\mathcal{J}}_{2,1}$,     arrange them in the increasing order of their indexes GOTO Step 10 END Step 3: IF the first inequality in condition (8) of Theorem 7 holds THEN BEGIN   Construct a permutation ${\pi }_{2,1}$ of jobs from set ${\mathcal{J}}_{2,1}$,     arrange them in the increasing order of their indexes;   IF the second inequality in condition (8) of Theorem 7 holds THEN     construct a permutation ${\pi }_{1,2}$ of jobs from set ${\mathcal{J}}_{1,2}$,     arrange the jobs in the increasing order of their indexes END Step 4: IF both permutations ${\pi }_{1,2}$ and ${\pi }_{2,1}$ are constructed THEN GOTO Step 10. Step 5: IF permutation ${\pi }_{1,2}$ is not constructed THEN fulfill Algorithm 3. Step 6: IF permutation ${\pi }_{2,1}$ is not constructed THEN fulfill Algorithm 4. Step 7: IF both permutations ${\pi }_{1,2}$ and ${\pi }_{2,1}$ are constructed THEN GOTO Step 10. Step 8: IF permutation ${\pi }_{2,1}$ is constructed THEN GOTO Step 11. Step 9: IF permutation ${\pi }_{1,2}$ is constructed THEN GOTO Step 12 ELSE GOTO Step 13. Step 10: RETURN pair of permutations $({\pi }^{\prime },{\pi }^{″})$, where ${\pi }^{\prime }$ is the permutation   of jobs from set ${\mathcal{J}}_{1,2}\cup {\mathcal{J}}_1\cup {\mathcal{J}}_{2,1}$ processed on machine $M_1$ and ${\pi }^{″}$ is   the permutation of jobs from set ${\mathcal{J}}_{1,2}\cup {\mathcal{J}}_2\cup {\mathcal{J}}_{2,1}$ processed   on machine $M_2$ such that $\left\{({\pi }^{\prime },{\pi }^{\prime \prime })\right\}=DS\left(T\right)$ STOP 0. Step 11: RETURN the permutation ${\pi }_{2,1}$ of jobs from set ${\mathcal{J}}_{2,1}$ processed on machines $M_1$ and $M_2$,   the partial strict order $A_{\prec }^{1,2}$ of jobs from set ${\mathcal{J}}_{1,2}$ GOTO Step 14. Step 12: RETURN the permutation ${\pi }_{1,2}$ of jobs from set ${\mathcal{J}}_{1,2}$ processed on machines $M_1$ and $M_2$,   the partial strict order $A_{\prec }^{2,1}$ of jobs from set ${\mathcal{J}}_{2,1}$ GOTO Step 14. Step 13: RETURN the partial strict order $A_{\prec }^{1,2}$ of jobs from set ${\mathcal{J}}_{1,2}$   and the partial strict order $A_{\prec }^{2,1}$ of jobs from set ${\mathcal{J}}_{2,1}$ Step 14: STOP 1.

Algorithm 2 may be applied for solving the problem $J2|l_{ij}\le p_{ij}\le u_{ij},n_i\le 2|C_{max}$ exactly or approximately as follows. If at least one of the sufficient conditions proven in Section 5.1 hold, then Algorithm 2 constructs a pair of job permutations $({\pi }^{\prime },{\pi }^{″})=(({\pi }_{1,2},{\pi }_1,{\pi }_{2,1}),({\pi }_{2,1},{\pi }_2,{\pi }_{1,2}))$, which is optimal for any scenario $p\in T$ (Step 10).

It may happen that the constructed strict order on the set ${\mathcal{J}}_{1,2}$ or on the set ${\mathcal{J}}_{2,1}$ is not a linear strict order. If for at least one of the sets ${\mathcal{J}}_{1,2}$ or ${\mathcal{J}}_{2,1}$, the constructed partial strict order is not a linear one, a heuristic solution for the problem $J2|l_{ij}\le p_{ij}\le u_{ij},n_i\le 2|C_{max}$ is constructed similar to that for the problem $F2|l_{ij}\le p_{ij}\le u_{ij}|C_{max}$ solved by Algorithm 1 (see Section 5.4). If Algorithm 2 is completed at Steps 11-13 (STOP 1), we consider a set of conflict jobs $\{J_{k+1},J_{k+2},\dots ,J_{k+r}\}$ and construct a Jackson’s pair of job permutation for the deterministic problem $J2|p^{\prime },n_i\le 2|C_{max}$ with job set $\mathcal{J}=\{J_{k+1},J_{k+2},\dots J_{k+r}\}$, where the vector $p^{\prime }=(p_{k+1,1}^{\prime },p_{k+1,2}^{\prime },\dots p_{k+r,1}^{\prime },p_{k+r,2}^{\prime })$ of the durations of conflict jobs $\{J_{k+1},J_{k+2},\dots J_{k+r}\}$ is calculated using the equality of Equation (16) for each operation $O_{ij}$ of the conflict job $J_i\in \{J_{k+1},J_{k+2},\dots J_{k+r}\}$ on the corresponding machine $M_j\in \mathcal{M}$ (Remark 3).

Algorithm 3: Construction of a strict order $A_{\prec }^{1,2}$ on the set ${\mathcal{J}}_{1,2}$

Input:  Lower bounds $l_{ij}$ and upper bounds $u_{ij}$, $0<l_{ij}\le u_{ij}$, of the durations of all operations $O_{ij}$ of jobs $J_i\in \mathcal{J}$ on machines $M_j\in \mathcal{M}=\{M_1,M_2\}$. Output:  EITHER permutation ${\pi }_{1,2}$, which is optimal for the problem   $F2|l_{ij}\le p_{ij}\le u_{ij}|C_{max}$ with any scenario $p\in T$ for the jobs ${\mathcal{J}}_{1,2}$, OR partial strict order $A_{\prec }^{1,2}$ on the set ${\mathcal{J}}_{1,2}$. Step 1: Construct a partition ${\mathcal{J}}_{1,2}={\mathcal{J}}_{1,2}^1\cup {\mathcal{J}}_{1,2}^2\cup {\mathcal{J}}_{1,2}^{*}$ of the set ${\mathcal{J}}_{1,2}$ of the jobs. Step 2: IF conditions of Theorem 2 hold THEN Step 3: Construct permutation ${\pi }_{1,2}=({\pi }_{1,2}^1,J_{1,2}^{*},{\pi }_{1,2}^2)$, where ${\pi }_{1,2}^1$ is a permutation for     processing jobs from the set ${\mathcal{J}}_{1,2}^1$ in the non-decreasing order of the values $u_{i1}$,     ${\pi }_{1,2}^2$ is a permutation for processing jobs from the set ${\mathcal{J}}_{1,2}^2$     in the non-increasing order of the values $u_{i2}$GOTO Step 7 ELSE Step 4: FOR each pair of jobs $J_v\in {\mathcal{J}}_{1,2}$ and $J_w\in {\mathcal{J}}_{1,2}$, $v\ne w$, DO     IF at least one of two conditions (4) and (5) holds THEN     determine the relation $J_v\prec J_w$ END FOR Step 5: Renumber jobs in the set ${\mathcal{J}}_{1,2}$ such that relation $v<w$ holds if $J_v\prec J_w$. Step 6: FOR each conflict set of jobs DO     IF condition of Theorem 10 holds THEN     Order jobs in the conflict set in the increasing order of their indexes GOTO Step 7     ELSE fulfill Algorithm 1 END FOR Step 7: IF the partial strict order $A_{\prec }^{1,2}$ is linear THEN     construct a permutation ${\pi }_{1,2}$ generated by the linear order $A_{\prec }^{1,2}$ STOP.

Algorithm 4 is obtained from the above Algorithm 3 by replacing the set ${\mathcal{J}}_{1,2}$ of jobs by the set ${\mathcal{J}}_{2,1}$ of jobs, machine $M_1$ by machine $M_2$, and vice versa. Obviously, testing the conditions of Theorems 11 and 12 takes $O\left(r\right)$, where conflict set contains r jobs. Construction of permutation of r jobs takes $O(rlogr)$. Therefore, the total complexity of Algorithm 1 is $O(rlogr)$.

Testing the conditions of Theorem 2 takes $O(m_{1,2}log{m}_{1,2})$ time. A strict order $A_{\prec }^{1,2}$ on the set ${\mathcal{J}}_{1,2}$ is constructed by comparing no more than $m_{1,2}(m_{1,2}-1)$ pairs of jobs in the set ${\mathcal{J}}_{1,2}$. Thus, it takes $O\left(m_{1,2}(m_{1,2}-1)\right)$ time. The complexity of Algorithm 1 is $O(rlogr)$ time provided that the conflict set contains r jobs, where $r\le m_{1,2}$. Since a strict order $A_{\prec }^{1,2}$ is constructed once in Algorithm 3, we conclude that a total complexity of Algorithm 3 (and Algorithm 4) is $O\left(n^2\right)$ time.

In Algorithm 2, testing the condition of Theorem 7 takes $O(max\{m_{1,2},m_{2,1}\})$ time. Every Algorithm 3 or Algorithm 4 is fulfilled at most once. Therefore, the complexity of Algorithm 2 is $O\left(n^2\right)$ time.

7. Computational Experiments

We describe the conducted computational experiments and discuss the results obtained for randomly generated instances of the problem $J2|l_{ij}\le p_{ij}\le u_{ij},n_i\le 2|C_{max}$. In the computational experiments, each tested series consisted of 1000 randomly generated instances with the same numbers $n\in \{10,20,\dots ,100,200,\dots ,1000,2000,\dots ,10.000\}$ of jobs in the set $\mathcal{J}$ provided that a maximum relative length $\delta$ of the given segment of the possible durations of the operations $O_{ij}$ takes the following values: $\{5\%,10\%,$$15\%,20\%,30\%,40\%,$ and $50\%\}$. The lower bounds $l_{ij}$ and upper bounds $u_{ij}$ for possible values of the durations $p_{ij}$ of the operations $O_{ij}$, $p_{ij}\in [l_{ij},u_{ij}]$ using the value $\delta$ have been determined as follows. First, a value of the lower bound $l_{ij}$ is randomly chosen from the segment $[10,1000]$ using a uniform distribution. Then, the upper bound $u_{ij}$ is calculated using the following equality:

$$u_{ij}=l_{ij}\left(1+\frac{\delta }{100}\right)$$

(17)

For example, we assume that $\delta =5\%$. Then, for the lower bounds $l_{ij}=50$ and $l_{ij}=500$, the upper bounds $u_{ij}=52.5$ and $u_{ij}=525$ are calculated using Reference (17). If $\delta =50\%$, then based on the lower bounds $l_{ij}=50$ and $l_{ij}=500$ and on Reference (17), we obtain the upper bounds $u_{ij}=75$ and $u_{ij}=750$. Thus, rather wide ranges for the tested durations of the jobs $\mathcal{J}$ were considered.

In the experiments, the bounds $l_{ij}$ and $u_{ij}$ were decimal fractions with the maximum possible number of digits after the decimal point. For all tested instances of the problem $J2|l_{ij}\le p_{ij}\le u_{ij},n_i\le 2|C_{max}$, a strict inequality $l_{ij}<u_{ij}$ was guarantied for each job $J_i\in \mathcal{J}$ and each machine $M_j\in \mathcal{M}$.

We used Algorithms 1 – 4 described in Section 5.4 and Section 6 for solving the problem $J2|l_{ij}\le p_{ij}\le u_{ij},n_i\le 2|C_{max}$. These algorithms were coded in C# and tested on a PC with Intel Core i7-7700 (TM) 4 Quad, 3.6 GHz, and 32.00 GB RAM. Since Algorithms 1 – 4 are polynomial in number n jobs in set $\mathcal{J}$, the calculations were carried out quickly. In the experiments, we tested 15 classes of randomly generated instances of the problem $J2|l_{ij}\le p_{ij}\le u_{ij},n_i\le 2|C_{max}$ with different ratios between numbers $m_1$, $m_2$, $m_{1,2}$, and $m_{2,1}$ of the jobs in subsets ${\mathcal{J}}_1$, ${\mathcal{J}}_2$, ${\mathcal{J}}_{1,2}$, and ${\mathcal{J}}_{2,1}$ of the set $\mathcal{J}$. The obtained computational results are presented in

Table A1. Computational results for randomly generated instances with ratio $25\%:25\%:25\%:25\%$ of the number of jobs in the subsets.

$\mathit{\delta }\%$	5%				10%				15%				20%				30%				40%				50%
$\mathit{n}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$
20	100	6	100	0	100	19	100	0	100	35	100	0	100	70	100	0	100	139	100	0	100	250	100	0	100	339	100	0
40	100	0	-	0	100	4	100	0	100	20	100	0	100	33	100	0	100	101	100	0	100	136	100	0	100	333	100	0
50	100	7	100	0	100	3	100	0	100	16	100	0	100	8	100	0	100	50	100	0	100	114	100	0	100	224	100	0
70	100	0	-	0	100	0	-	0	100	2	100	0	100	3	100	0	100	11	100	0	100	71	100	0	100	149	100	0
80	100	0	-	0	100	0	-	0	100	0	-	0	100	3	100	0	100	0	-	0	100	35	100	0	100	122	100	0
100	100	0	-	0	100	0	-	0	100	0	-	0	100	0	-	0	100	0	-	0	100	19	100	0	100	84	100	0
200	100	0	-	0	100	0	-	0	100	0	-	0	100	0	-	0	100	0	-	0	100	0	-	0	100	5	100	0
300	100	0	-	0	100	0	-	0	100	0	-	0	100	0	-	0	100	0	-	0	100	0	-	0	100	0	-	0
400	100	0	-	0	100	0	-	0	100	0	-	0	100	0	-	0	100	0	-	0	100	0	-	0	100	0	-	0
500	100	0	-	0	100	0	-	0	100	0	-	0	100	0	-	0	100	0	-	0	100	0	-	0	100	0	-	0
600	100	0	-	0	100	0	-	0	100	0	-	0	100	0	-	0	100	0	-	0	100	0	-	0	100	0	-	0
700	100	0	-	0	100	0	-	0	100	0	-	0	100	0	-	0	100	0	-	0	100	0	-	0	100	0	-	0
800	100	0	-	0	100	0	-	0	100	0	-	0	100	0	-	0	100	0	-	0	100	0	-	0	100	0	-	0
900	100	0	-	0	100	0	-	0	100	0	-	0	100	0	-	0	100	0	-	0	100	0	-	0	100	0	-	0
1000	100	0	-	0	100	0	-	0	100	0	-	0	100	0	-	0	100	0	-	0	100	0	-	0	100	0	-	0
2000	100	0	-	0	100	0	-	0	100	0	-	0	100	0	-	0	100	0	-	0	100	0	-	0	100	0	-	0
3000	100	0	-	0	100	0	-	0	100	0	-	0	100	0	-	0	100	0	-	0	100	0	-	0	100	0	-	0
4000	100	0	-	0	100	0	-	0	100	0	-	0	100	0	-	0	100	0	-	0	100	0	-	0	100	0	-	0
5000	100	0	-	0	100	0	-	0	100	0	-	0	100	0	-	0	100	0	-	0	100	0	-	0	100	0	-	0
6000	100	0	-	0	100	0	-	0	100	0	-	0	100	0	-	0	100	0	-	0	100	0	-	0	100	0	-	0
7000	100	0	-	0	100	0	-	0	100	0	-	0	100	0	-	0	100	0	-	0	100	0	-	0	100	0	-	0
8000	100	0	-	0	100	0	-	0	100	0	-	0	100	0	-	0	100	0	-	0	100	0	-	0	100	0	-	0
9000	100	0	-	0	100	0	-	0	100	0	-	0	100	0	-	0	100	0	-	0	100	0	-	0	100	0	-	0
10,000	100	0	-	0	100	0	-	0	100	0	-	0	100	0	-	0	100	0	-	0	100	0	-	0	100	0	-	0
Aver.	100	0.54	100	0	100	1.08	100	0	100	3.04	100	0	100	4.88	100	0	100	12.54	100	0	100	26.04	100	0	100	52.33	100	0

,

Table A2. Computational results for randomly generated instances with ratio $10\%:10\%:40\%:40\%$ of the number of jobs in the subsets.

$\mathit{\delta }\%$	5%				10%				15%				20%				30%				40%				50%
$\mathit{n}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$
10	100	71	100	0	100	153	100	0	99.6	241	98.34	0	99.4	320	98.13	0	98.1	481	96.05	0	95.8	618	93.20	0	91.9	713	88.64	0
20	100	235	100	0	100	531	100	0	100	811	100	0	100	1032	100	0	100	1341	100	0	99.9	1450	99.93	0	99.5	1424	99.65	0
30	100	460	100	0	100	887	100	0	100	1334	100	0	100	1643	100	0	100	1912	100	0	99.9	1893	99.95	0	100	1808	100	0
40	100	636	100	0	100	1185	100	0	100	1659	100	0	100	2068	100	0	100	2352	100	0	100	2162	100	0	99.9	1953	99.95	0
50	100	824	100	0	100	1496	100	0	100	2074	100	0	100	2411	100	0	100	2546	100	0	100	2211	100	0	100	2009	100	0
60	100	893	100	0	100	1542	100	0	100	2222	100	0	100	2619	100	0	100	2758	100	0	100	2440	100	0	100	2109	100	0
70	100	841	100	0	100	1589	100	0	100	2285	100	0	100	2775	100	0	100	2935	100	0	100	2477	100	0	100	2106	100	0
80	100	981	100	0	100	1570	100	0	100	2342	100	0	100	2896	100	0	100	2995	100	0	100	2567	100	0	100	2249	100	0
90	100	878	100	0	100	1660	100	0	100	2310	100	0	100	2905	100	0	100	3103	100	0	100	2598	100	0	100	2273	100	0
100	100	826	100	0	100	1633	100	0	100	2368	100	0	100	3056	100	0	100	3114	100	0	100	2585	100	0	100	2321	100	0
200	100	411	100	0	100	1145	100	0	100	1999	100	0	100	3065	100	0	100	3392	100	0	100	2709	100	0	100	2250	100	0
300	100	181	100	0	100	721	100	0	100	1708	100	0	100	2888	100	0	100	3365	100	0	100	2579	100	0	100	2117	100	0
400	100	51	100	0	100	302	100	0	100	981	100	0	100	2466	100	0	100	3263	100	0	100	2469	100	0	100	1966	100	0
500	100	11	100	0	100	240	100	0	100	813	100	0	100	2307	100	0	100	3138	100	0	100	2362	100	0	100	1838	100	0
600	100	0	-	0	100	88	100	0	100	499	100	0	100	2076	100	0	100	2951	100	0	100	2202	100	0	100	1692	100	0
700	100	0	-	0	100	45	100	0	100	528	100	0	100	1894	100	0	100	2779	100	1	100	2015	100	1	100	1585	100	1
800	100	0	-	0	100	36	100	0	100	294	100	0	100	1707	100	0	100	2656	100	0	100	1866	100	1	100	1485	100	1
900	100	0	-	0	100	0	-	0	100	318	100	0	100	1442	100	0	100	2392	100	1	100	1677	100	1	100	1420	100	1
1000	100	0	-	0	100	0	-	0	100	196	100	0	100	1275	100	0	100	2255	100	1	100	1630	100	1	100	1298	100	1
2000	100	0	-	0	100	0	-	0	100	3	100	0	100	441	100	0	100	1452	100	3	100	1137	100	3	100	1044	100	2
3000	100	0	-	0	100	0	-	0	100	0	-	0	100	160	100	0	100	1127	100	6	100	1025	100	5	100	1011	100	4
4000	100	0	-	0	100	0	-	0	100	0	-	0	100	86	100	0	100	1032	100	9	100	1005	100	8	100	1000	100	7
5000	100	0	-	0	100	0	-	0	100	0	-	0	100	34	100	0	100	1011	100	14	100	1000	100	12	100	1000	100	10
6000	100	0	-	0	100	0	-	0	100	0	-	0	100	23	100	0	100	1002	100	21	100	1001	100	17	100	1001	100	14
7000	100	0	-	0	100	0	-	0	100	0	-	0	100	8	100	0	100	1000	100	28	100	1000	100	23	100	1000	100	19
8000	100	0	-	0	100	0	-	0	100	0	-	0	100	6	100	0	100	1001	100	37	100	1000	100	31	100	1000	100	25
9000	100	0	-	0	100	0	-	0	100	0	-	0	100	3	100	0	100	1000	100	48	100	1000	100	39	100	1000	100	32
10,000	100	0	-	0	100	0	-	0	100	0	-	0	100	4	100	1	100	1000	100	61	100	1000	100	49	100	1000	100	40
Aver.	100	261	100	0	100	529	100	0	99.99	892	99.92	0	99.98	1486	99.93	0.04	99.93	2120	99.86	8.21	99.84	1774	99.75	6.82	99.69	1560	99.58	5.61

,

Table A3. Computational results for randomly generated instances with ratio $10\%:40\%:10\%:40\%$ of the number of jobs in the subsets.

$\mathit{\delta }\%$	5%				10%				15%				20%				30%				40%				50%
$\mathit{n}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$
10	98.7	104	87.5	0	97.3	207	86.96	0	96.9	287	89.20	0	94.5	359	84.68	0	92.5	543	86.19	0	88.5	597	80.74	0	81.5	713	74.05	0
20	99.7	466	99.36	0	99.6	830	99.52	0	99.3	1057	99.24	0	98.5	1244	98.79	0	95.3	1433	96.65	0	91	1467	93.73	0	84.6	1501	89.61	0
30	100	1070	100	0	99.8	1597	99.87	0	99.7	1879	99.84	0	98.2	2007	99.10	0	96.7	2053	98.30	0	91.4	1945	95.58	0	82.1	1790	89.83	0
40	100	1700	100	0	100	2355	100	0	99.8	2660	99.92	0	99.7	2628	99.89	0	97.6	2462	99.03	0	92.4	2135	96.35	0	85.5	1979	92.52	0
50	100	2425	100	0	99.7	3174	99.91	0	99.9	3197	99.97	0	99.8	3048	99.93	0	97.8	2664	99.17	0	92.5	2283	96.54	0	82.2	2075	91.42	0
60	100	3218	100	0	100	3808	100	0	100	3702	100	0	99.9	3394	99.97	0	98.5	2881	99.41	0	91.9	2442	96.60	0	80.5	2172	90.75	0
70	100	3911	100	0	100	4385	100	0	99.9	4063	99.98	0	99.9	3648	99.97	0	98.7	2959	99.56	0	91.9	2517	96.62	0	78	2146	89.47	0
80	100	4817	100	0	100	4902	100	0	99.8	4370	99.95	0	99.9	3829	99.97	0	98.5	3103	99.52	0	92.2	2627	96.99	0	77.3	2257	89.77	0
90	100	5518	100	0	100	5398	100	0	100	4656	100	0	100	3910	100	0	97.7	3154	99.21	0	92.5	2675	97.12	0	79.5	2249	90.84	0
100	100	6195	100	0	100	5697	100	0	99.9	4853	99.98	0	100	4047	100	0	98.2	3207	99.44	0	91.3	2706	96.78	0	75.6	2328	89.48	0
200	100	10,620	100	0	100	7608	100	0	100	5717	100	0	100	4645	100	0	98.9	3320	99.64	0	90.8	2717	96.61	0	72.7	2281	87.90	0
300	100	13,110	100	0	100	8259	100	0	100	6070	100	0	100	4782	100	0	99.5	3369	99.85	0	94.3	2605	97.81	0	74.5	2117	87.81	0
400	100	14,309	100	1	100	8634	100	0	100	6113	100	0	100	4650	100	0	99.8	3247	99.94	0	94.3	2460	97.68	0	73.1	2002	86.56	0
500	100	14,935	100	0	100	8658	100	0	100	6102	100	0	100	4630	100	0	99.9	3137	99.97	0	95.1	2297	97.87	0	78.5	1808	88.11	0
600	100	15,780	100	0	100	8832	100	0	100	6021	100	0	100	4492	100	0	100	2911	100	0	97.2	2153	98.70	0	77.8	1705	86.98	0
700	100	15,971	100	0	100	8753	100	0	100	5789	100	0	100	4379	100	0	100	2786	100	0	97.7	1996	98.85	0	82.4	1613	89.09	0
800	100	16,439	100	0	100	8806	100	0	100	5793	100	0	100	4176	100	0	100	2533	100	0	98.8	1846	99.35	0	84	1487	89.24	0
900	100	16,268	100	0	100	8574	100	1	100	5608	100	1	100	4005	100	1	100	2379	100	0	98.8	1717	99.30	0	89.1	1366	92.02	0
1000	100	16,614	100	1	100	8419	100	1	100	5400	100	1	100	3807	100	1	100	2279	100	1	99.6	1655	99.76	1	90.9	1302	93.01	0
2000	100	15,539	100	2	100	6906	100	2	100	3715	100	2	100	2422	100	2	100	1401	100	1	100	1135	100	1	98.4	1040	98.46	1
3000	100	13,884	100	4	100	5259	100	4	100	2599	100	4	100	1624	100	3	100	1109	100	3	100	1021	100	3	99.8	1006	99.80	3
4000	100	12,302	100	7	100	3911	100	7	100	1874	100	6	100	1291	100	6	100	1044	100	5	100	1004	100	4	99.8	1001	99.80	4
5000	100	10,421	100	13	100	2935	100	11	100	1485	100	10	100	1126	100	9	100	1008	100	8	100	1000	100	6	100	1000	100	5
6000	100	8822	100	17	100	2299	100	16	100	1262	100	14	100	1043	100	13	100	1004	100	10	100	1000	100	9	100	1000	100	8
7000	100	7426	100	24	100	1855	100	22	100	1145	100	20	100	1026	100	17	100	1000	100	14	100	1001	100	11	100	1000	100	10
8000	100	6346	100	33	100	1569	100	30	100	1084	100	26	100	1007	100	23	100	1000	100	18	100	1000	100	15	100	1000	100	13
9000	100	5378	100	42	100	1362	100	38	100	1038	100	33	100	1002	100	30	100	1000	100	24	100	1000	100	19	100	1000	100	17
10,000	100	4529	100	54	100	1237	100	48	100	1028	100	42	100	1000	100	38	100	1000	100	29	100	1000	100	24	100	1000	100	20
Aver.	99.94	8861	99.53	7.07	99.87	4865	99.51	6.43	99.83	3520	99.57	5.68	99.66	2829	99.37	5.11	98.91	2142	99.14	4.04	95.79	1786	97.61	3.32	86.71	1569	92.38	2.89

,

Table A4. Computational results for randomly generated instances with ratio $10\%:30\%:10\%:50\%$ of the number of jobs in the subsets.

$\mathit{\delta }\%$	5%				10%				15%				20%				30%				40%				50%
$\mathit{n}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$
10	99.4	194	96.91	0	97.4	334	92.22	0	95.5	474	90.51	0	94.3	566	89.93	0	88.3	749	84.38	0	79.1	849	75.03	0	74.1	934	71.95	0
20	99.9	767	99.87	0	99.4	1232	99.51	0	98.4	1489	98.86	0	97.5	1680	98.39	0	94.7	1762	96.99	0	85.6	1770	91.64	0	75.1	1724	85.15	0
30	99.7	1532	99.80	0	99.5	2150	99.77	0	99.2	2399	99.67	0	99	2499	99.52	0	96	2367	98.31	0	86.8	2200	93.77	0	71.7	1941	85.27	0
40	99.8	2422	99.92	0	99.7	3151	99.90	0	99.8	3295	99.94	0	98.9	2972	99.63	0	95.2	2581	98.06	0	83	2326	92.48	0	69.5	2055	85.06	0
50	100	3422	100	0	99.9	4013	99.98	0	99.9	3844	99.97	0	99.5	3451	99.86	0	95.3	2857	98.35	0	82.1	2486	92.76	0	64.2	2202	83.47	0
60	100	4425	100	0	100	4681	100	0	99.9	4189	99.98	0	99.4	3750	99.84	0	94.8	2981	98.26	0	83.7	2566	93.53	0	64	2238	83.60	0
70	100	5338	100	0	100	5181	100	0	100	4569	100	0	99.3	4027	99.83	0	94.3	3183	98.21	0	79.6	2594	92.14	0	61.1	2284	82.75	0
80	100	6169	100	0	100	5770	100	0	99.9	4915	99.98	0	99.6	4112	99.90	0	95.6	3257	98.62	0	80.5	2625	92.42	0	58	2260	81.15	0
90	100	6998	100	0	100	6018	100	0	100	4984	100	0	99.6	4213	99.91	0	94.6	3332	98.38	0	78.5	2680	91.87	0	52.3	2270	78.72	0
100	100	7714	100	0	100	6298	100	0	100	5197	100	0	99.6	4358	99.91	0	94.5	3367	98.31	0	75.8	2642	90.61	0	54.6	2299	79.99	0
200	100	12,228	100	0	100	7920	100	0	100	5951	100	0	100	4748	100	0	95.7	3330	98.71	0	73.5	2665	90.02	0	45.4	2233	75.41	0
300	100	14,375	100	0	100	8735	100	0	100	6096	100	0	100	4723	100	0	96.4	3285	98.90	0	69.6	2464	87.66	0	43.4	2064	72.53	0
400	100	15,022	100	0	100	8762	100	0	100	6135	100	0	100	4712	100	0	96.4	3036	98.81	0	70.5	2286	87.05	0	48.1	1820	71.43	0
500	100	15,705	100	0	100	8823	100	0	100	5876	100	0	100	4497	100	0	97.5	2842	99.12	0	73.5	2100	87.38	0	55.1	1686	73.37	0
600	100	16,442	100	0	100	8712	100	0	100	5753	100	0	100	4252	100	0	97.6	2674	99.10	0	74.8	1941	87.02	0	62.6	1530	75.56	0
700	100	15,910	100	0	100	8670	100	0	100	5609	100	0	100	3976	100	0	99.1	2510	99.64	0	76.5	1776	86.77	0	69.3	1420	78.31	0
800	100	16,215	100	1	100	8419	100	1	100	5492	100	1	100	3773	100	1	99.3	2271	99.69	1	81.9	1648	89.02	1	75.9	1319	81.73	1
900	100	16,347	100	1	100	8268	100	1	100	5254	100	1	100	3597	100	1	99.2	2173	99.63	1	84.8	1575	90.35	1	80.7	1245	84.50	1
1000	100	16,355	100	1	100	8133	100	1	100	5064	100	1	100	3369	100	1	99.7	1998	99.85	1	86.8	1426	90.74	1	84.9	1189	87.30	1
2000	100	14,679	100	3	100	5955	100	3	100	3095	100	3	100	1972	100	2	100	1243	100	2	98.6	1056	98.67	2	97.7	1017	97.74	2
3000	100	12,643	100	6	100	4207	100	6	100	2036	100	5	100	1354	100	5	100	1038	100	4	99.9	1003	99.90	4	100	1001	100	3
4000	100	10,375	100	12	100	2927	100	11	100	1467	100	10	100	1152	100	9	100	1011	100	7	100	1000	100	6	100	1000	100	6
5000	100	8524	100	19	100	2140	100	18	100	1205	100	15	100	1032	100	14	100	1003	100	11	100	1000	100	9	100	1000	100	8
6000	100	6942	100	28	100	1724	100	26	100	1095	100	23	100	1014	100	20	100	1000	100	16	100	1000	100	14	100	1000	100	12
7000	100	5463	100	40	100	1398	100	35	100	1050	100	32	100	1007	100	28	100	1002	100	23	100	1000	100	18	100	1000	100	16
8000	100	4543	100	54	100	1240	100	48	100	1028	100	43	100	1002	100	45	100	1000	100	30	100	1000	100	24	100	1000	100	21
9000	100	3751	100	69	100	1135	100	62	100	1005	100	55	100	1001	100	48	100	1000	100	38	100	1000	100	32	100	1000	100	26
10,000	100	3056	100	86	100	1078	100	77	100	1003	100	68	100	1000	100	60	100	1000	100	48	100	1000	100	40	100	1000	100	33
Aver.	99.96	8841	99.87	11.43	99.85	4896	99.69	10.32	99.74	3556	99.60	9.18	99.53	2850	99.53	8.36	97.29	2138	98.62	6.50	85.90	1774	92.89	5.43	75.28	1562	86.25	4.64

,

Table A5. Computational results for randomly generated instances with ratio $10\%:20\%:10\%:60\%$ of the number of jobs in the subsets.

$\mathit{\delta }\%$	5%				10%				15%				20%				30%				40%				50%
$\mathit{n}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$
10	98.8	263	95.44	0	97.5	491	94.91	0	94.5	657	91.48	0	91	791	88.50	0	81.5	1014	81.36	0	74.9	1102	76.59	0	66	1186	70.49	0
20	99.7	1034	99.71	0	98.8	1601	99.19	0	98.8	1904	99.32	0	97.6	1984	98.74	0	89.9	2113	95.13	0	80.4	1968	89.94	0	63	1845	79.73	0
30	99.9	2131	99.95	0	99.8	2778	99.93	0	99	3059	99.67	0	98.3	2878	99.37	0	89.6	2608	95.82	0	74.3	2270	88.46	0	60.3	2060	80.34	0
40	100	3224	100	0	99.9	3747	99.97	0	99.8	3698	99.95	0	98.3	3392	99.50	0	90.9	2877	96.63	0	71.8	2469	88.42	0	52	2174	77.60	0
50	100	4370	100	0	100	4704	100	0	99.6	4174	99.90	0	99	3701	99.73	0	89.4	2988	96.32	0	66.6	2566	86.83	0	47.1	2228	75.94	0
60	100	5473	100	0	100	5368	100	0	99.9	4608	99.98	0	98.2	3987	99.55	0	89.3	3098	96.51	0	67.2	2643	87.48	0	42.6	2279	74.59	0
70	100	6454	100	0	100	5985	100	0	99.9	4968	99.98	0	99.4	4125	99.85	0	87.5	3214	96.02	0	62.6	2669	85.69	0	38.6	2291	72.85	0
80	100	7498	100	0	99.9	6235	99.98	0	99.8	5194	99.94	0	98.8	4333	99.70	0	87.3	3372	96.14	0	61.4	2716	85.64	0	33.6	2260	70.40	0
90	99.9	8281	99.99	0	100	6560	100	0	99.8	5243	99.96	0	98.9	4502	99.76	0	87.8	3388	96.40	0	61.4	2757	85.78	0	32	2361	71.03	0
100	100	9169	100	0	100	7056	100	0	99.7	5507	99.95	0	99.2	4586	99.83	0	83.7	3360	94.97	0	58.2	2689	84.27	0	27.7	2287	68.21	0
200	100	13,366	100	0	100	8131	100	0	99.9	6029	99.98	0	99	4814	99.79	0	83.1	3329	94.89	0	43.9	2541	77.80	0	10.3	2172	58.52	0
300	100	14,999	100	0	100	8869	100	0	100	6010	100	0	98.9	4675	99.76	0	82	3127	94.18	0	32.2	2329	70.85	0	4.6	1870	48.66	0
400	100	15,704	100	0	100	8848	100	0	100	6048	100	0	99.7	4490	99.93	0	82.5	2899	93.96	0	28.3	2120	66.08	0	1.3	1710	42.28	0
500	100	15,775	100	0	100	8720	100	0	100	5825	100	0	99.7	4290	99.93	0	83.2	2638	93.63	0	21.6	1885	58.30	0	0.7	1541	35.56	0
600	100	16,336	100	0	100	8420	100	1	100	5582	100	0	100	3938	100	0	87.7	2420	94.88	1	18	1727	52.52	0	0	1408	28.98	0
700	100	16,298	100	1	100	8466	100	1	100	5360	100	1	100	3733	100	1	88.4	2203	94.73	1	15	1574	46.00	1	0	1282	22.00	1
800	100	16,707	100	1	100	8030	100	1	100	5023	100	1	99.9	3479	99.97	1	88.7	2077	94.56	1	12.9	1457	40.15	1	0.2	1207	17.32	1
900	100	16,135	100	1	100	7936	100	1	100	4808	100	1	100	3265	100	1	89.5	1934	94.52	1	10.8	1368	34.80	1	0	1172	14.68	1
1000	100	16,015	100	1	100	7665	100	1	100	4528	100	1	100	3049	100	1	91.6	1737	95.16	1	9.6	1314	31.20	1	0	1144	12.59	1
2000	100	13,921	100	4	100	5101	100	4	100	2549	100	4	100	1622	100	3	98.6	1138	98.77	3	1.2	1024	3.52	3	0	1002	0.20	3
3000	100	11,344	100	9	100	3400	100	9	100	1636	100	8	100	1210	100	7	99.8	1014	99.80	6	0.4	1003	0.70	5	0	1000	0	5
4000	100	8769	100	17	100	2283	100	16	100	1245	100	14	100	1054	100	13	100	1003	100	10	0.1	1000	0.1	9	0	1000	0	8
5000	100	6948	100	28	100	1691	100	25	100	1102	100	27	100	1023	100	21	100	1001	100	16	0	1000	0	14	0	1000	0	11
6000	100	5409	100	42	100	1362	100	38	100	1041	100	34	100	1003	100	30	100	1000	100	27	0	1000	0	20	0	1000	0	17
7000	100	4121	100	59	100	1214	100	53	100	1016	100	47	100	1001	100	42	100	1000	100	34	0	1000	0	27	0	1000	0	23
8000	100	3368	100	80	100	1093	100	71	100	1006	100	62	100	1000	100	66	100	1000	100	43	0	1000	0	36	0	1000	0	30
9000	100	2646	100	102	100	1048	100	90	100	1000	100	80	100	1000	100	71	100	1000	100	56	0	1000	0	47	0	1000	0	39
10,000	100	2248	100	126	100	1024	100	119	100	1002	100	100	100	1000	100	89	100	1000	100	70	0	1000	0	63	0	1000	0	48
Aver.	99.94	8857	99.82	16.82	99.85	4923	99.79	15.36	99.67	3565	99.65	13.57	99.14	2854	99.43	12.36	91.14	2127	96.23	9.64	31.17	1757	47.90	8.14	17.14	1553	36.50	6.71

,

Table A6. Computational results for randomly generated instances with ratio $10\%:10\%:10\%:70\%$ of the number of jobs in the subsets.

$\mathit{\delta }\%$	5%				10%				15%				20%				30%				40%				50%
$\mathit{n}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$
10	98.6	371	96.23	0	96.2	612	93.63	0	93.6	853	92.15	0	89.5	1015	89.06	0	82.1	1231	84.73	0	67.1	1301	73.10	0	54.3	1348	63.65	0
20	99.8	1432	99.86	0	99.3	1988	99.65	0	97.2	2273	98.77	0	95.5	2345	98.04	0	85.9	2222	93.61	0	67.5	2119	84.29	0	50.7	1952	74.13	0
30	99.7	2713	99.89	0	99.6	3341	99.88	0	99.2	3397	99.76	0	96.9	3204	99.03	0	85.9	2777	94.63	0	65.2	2344	84.98	0	43.5	2139	72.98	0
40	99.9	4056	99.98	0	99.7	4439	99.93	0	99.2	4015	99.80	0	97.1	3722	99.19	0	85	2983	94.90	0	58.4	2525	82.89	0	36.5	2191	70.61	0
50	100	5231	100	0	99.9	5130	99.98	0	99.7	4593	99.93	0	97.7	3952	99.42	0	80.4	3165	93.52	0	55	2595	82.35	0	28.6	2200	67.18	0
60	100	6574	100	0	99.9	5804	99.98	0	99.3	4934	99.84	0	97.1	4182	99.26	0	84.1	3283	94.94	0	49.9	2656	80.80	0	25.6	2255	66.39	0
70	99.9	7444	99.99	0	100	6365	100	0	99.4	5115	99.88	0	97.8	4328	99.49	0	80.4	3261	93.90	0	48.3	2706	80.60	0	21	2330	65.75	0
80	100	8505	100	0	100	6737	100	0	99.7	5415	99.94	0	96.5	4422	99.21	0	75.3	3304	92.37	0	42.7	2667	78.29	0	16.8	2258	63.02	0
90	100	9185	100	0	99.8	7333	99.97	0	99.8	5623	99.96	0	97.7	4555	99.50	0	76.4	3417	92.98	0	37.6	2696	76.34	0	13.3	2288	61.32	0
100	100	9909	100	0	99.9	7305	99.99	0	99.6	5571	99.93	0	98.2	4546	99.60	0	74.4	3449	92.49	0	35.8	2695	75.92	0	11.8	2314	61.62	0
200	100	13,806	100	0	100	8387	100	0	99.8	6146	99.97	0	96.2	4736	99.18	0	63.5	3261	88.75	0	16.1	2527	66.68	0	2.7	2006	51.40	0
300	100	15,550	100	0	100	8870	100	0	99.9	6084	99.98	0	97.3	4563	99.41	0	53.6	3067	84.84	0	6.9	2215	57.97	0	0.6	1765	43.63	0
400	100	15,856	100	0	100	8573	100	0	99.9	5852	99.98	0	96.9	4304	99.28	0	48.3	2737	81.11	0	3.4	2049	52.76	0	0	1596	37.34	0
500	100	16,158	100	0	100	8576	100	0	100	5760	100	0	97.9	4067	99.48	1	44.9	2471	77.70	0	1.8	1727	43.14	0	0.1	1402	28.74	0
600	100	16,216	100	1	100	8425	100	1	99.9	5416	99.98	1	98.8	3724	99.68	1	42.9	2217	74.24	1	1.6	1539	36.00	1	0	1279	21.81	1
700	100	16,338	100	1	100	8142	100	1	100	5055	100	1	99.1	3432	99.74	1	40.4	2059	71.01	1	1.4	1420	30.56	1	0	1197	16.46	1
800	100	16,548	100	1	100	7909	100	1	100	4744	100	1	99	3206	99.69	1	36.8	1821	65.29	1	0.4	1319	24.49	1	0	1133	11.74	1
900	100	16,000	100	1	100	7494	100	1	100	4477	100	1	99	2929	99.66	1	30.5	1716	59.50	1	0.1	1264	20.97	1	0	1098	8.93	1
1000	100	15,806	100	1	100	7294	100	1	100	4123	100	1	99.3	2694	99.74	1	36.1	1535	58.37	1	0.1	1177	15.12	1	0	1057	5.39	1
2000	100	13,179	100	6	100	4424	100	5	100	2200	100	5	100	1431	100	4	24.3	1059	28.52	4	0	1007	0.70	3	0	1002	0.20	3
3000	100	9960	100	13	100	2746	100	12	100	1407	100	11	100	1103	100	10	20.2	1007	20.75	8	0	1000	0	7	0	1001	0.10	7
4000	100	7402	100	24	100	1843	100	22	100	1130	100	20	100	1027	100	17	16.2	1000	16.2	15	0	1000	0	12	0	1000	0	10
5000	100	5616	100	40	100	1450	100	36	100	1042	100	31	100	1008	100	28	12.2	1000	12.2	23	0	1000	0	19	0	1000	0	15
6000	100	4234	100	59	100	1204	100	53	100	1019	100	56	100	1000	100	42	9.8	1000	9.8	34	0	1000	0	28	0	1000	0	23
7000	100	3236	100	82	100	1083	100	64	100	1007	100	65	100	1000	100	58	7.7	1000	7.7	47	0	1000	0	38	0	1000	0	31
8000	100	2511	100	121	100	1040	100	98	100	1002	100	90	100	1000	100	76	7.6	1000	7.6	61	0	1000	0	51	0	1000	0	43
9000	100	2059	100	140	100	1015	100	124	100	1001	100	110	100	1000	100	96	6.2	1000	6.2	79	0	1000	0	65	0	1000	0	52
10,000	100	1728	100	174	100	1011	100	154	100	1001	100	159	100	1000	100	120	5	1000	5	97	0	1000	0	80	0	1000	0	65
Aver.	99.93	8844	99.85	23.71	99.80	4948	99.75	20.46	99.51	3581	99.64	19.71	98.13	2839	99.20	16.32	47.00	2109	60.82	13.32	19.98	1734	41.00	11	10.91	1529	31.87	9.07

,

Table A7. Computational results for randomly generated instances with ratio $5\%:20\%:5\%:70\%$ of the number of jobs in the subsets.

$\mathit{\delta }\%$	5%				10%				15%				20%				30%				40%				50%
$\mathit{n}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$
20	98.8	1353	99.04	0	96.7	1993	98.29	0	93.3	2325	97.08	0	86.9	2343	94.15	0	71.4	2210	86.38	0	52.1	2091	76.09	0	34.8	1941	65.33	0
40	99.2	4101	99.80	0	98.7	4426	99.71	0	93.5	3918	98.34	0	88.8	3685	96.93	0	60.9	3007	86.63	0	33.2	2539	73.02	0	19	2189	62.27	0
60	99.1	6628	99.86	0	98.7	5712	99.75	0	93.1	4893	98.51	0	82.5	4106	95.64	0	48.8	3176	83.44	0	21.1	2584	68.89	0	10.9	2267	60.17	0
80	99.5	8614	99.93	0	98.3	6701	99.75	0	94.7	5335	98.93	0	79.5	4447	95.21	0	38.9	3272	80.96	0	14.5	2738	68.04	0	5.7	2254	57.59	0
100	99.9	10,165	99.99	0	98.7	7202	99.81	0	92.6	5740	98.69	0	76.5	4634	94.80	0	29.4	3338	78.16	0	10.5	2711	66.58	0	2.7	2224	55.94	0
200	100	13,856	100	0	98.6	8509	99.84	0	87.5	6083	97.93	0	59.5	4691	91.20	0	13.4	3333	73.69	0	4.8	2546	62.33	0	0.7	2041	51.20	0
300	100	15,201	100	0	99.3	8705	99.92	0	82.4	6187	97.07	0	44.5	4566	87.69	0	7.3	3025	69.16	0	2.4	2287	57.24	0	0.1	1833	45.50	0
400	99.9	15,924	99.99	0	98.4	8964	99.82	0	75.3	5888	95.77	0	32.3	4338	84.23	0	9.2	2727	66.59	0	1.9	1970	50.20	0	0.1	1592	37.25	0
500	100	16,186	100	0	98	8588	99.76	0	71	5652	94.80	0	28.6	3987	81.89	1	12.6	2468	64.55	0	1.5	1794	45.09	0	0	1379	27.48	0
600	100	16,531	100	1	97.5	8437	99.70	1	65.2	5391	93.51	1	26.8	3660	79.92	1	16.4	2184	61.72	1	0.6	1556	36.05	1	0	1287	22.30	1
700	100	16,251	100	1	98.7	8282	99.84	1	63.8	4967	92.65	1	24.6	3441	78.00	1	17.1	2087	60.28	2	0.3	1452	31.34	1	0	1186	15.68	1
800	100	16,462	100	1	98.3	7937	99.79	1	62.1	4736	91.91	1	26.5	3192	76.94	1	19.3	1806	55.26	1	0	1338	25.26	1	0	1131	11.58	1
900	100	16,099	100	1	97	7613	99.61	1	58.8	4439	90.70	1	28.7	2885	75.22	1	23.5	1694	54.84	1	0.4	1237	19.48	1	0	1118	10.55	1
1000	100	15,750	100	1	96.6	7157	99.52	1	59.2	4186	90.18	1	29.7	2708	74.04	1	23	1551	50.35	1	0.1	1211	17.51	1	0	1080	7.41	1
2000	100	13,055	100	6	97.8	4521	99.51	5	65.8	2164	84.20	5	76.3	1416	83.26	5	23.5	1063	28.03	4	0	1012	1.19	3	0	1003	0.30	3
3000	100	10,038	100	13	99.5	2766	99.82	12	86.4	1403	90.31	11	94	1109	94.59	10	17.9	1007	18.47	8	0	1000	0	7	0	1000	0	6
4000	100	7568	100	25	99.6	1823	99.78	22	96.3	1118	96.69	20	98.5	1021	98.53	18	15.9	1001	15.98	14	0	1000	0	12	0	1000	0	10
5000	100	5613	100	40	100	1430	100	35	97.4	1056	97.54	32	99.5	1008	99.50	29	11.4	1000	11.4	23	0	1000	0	19	0	1000	0	16
6000	100	4157	100	59	100	1187	100	54	99.5	1014	99.51	48	99.9	1002	99.90	46	10.4	1000	10.4	34	0	1000	0	33	0	1000	0	23
7000	100	3108	100	85	100	1076	100	74	99.7	1007	99.70	66	100	1000	100	60	8.6	1000	8.6	47	0	1000	0	39	0	1000	0	31
8000	100	2581	100	110	100	1051	100	98	99.7	1004	99.70	88	100	1000	100	78	6.4	1000	6.4	65	0	1000	0	50	0	1000	0	41
9000	100	2029	100	140	100	1014	100	131	100	1000	100	115	100	1000	100	99	6.7	1000	6.7	79	0	1000	0	63	0	1000	0	52
10,000	100	1672	100	175	100	1010	100	166	100	1000	100	138	100	1000	100	122	5.9	1000	5.9	99	0	1000	0	80	0	1000	0	66
Aver.	99.84	9693	99.94	28.61	98.71	5048	99.75	26.17	84.23	3500	95.81	22.96	68.85	2706	90.51	20.57	21.65	1954	47.13	16.48	6.23	1612	30.36	13.52	3.22	1414	23.07	11

,

Table A8. Computational results for randomly generated instances with ratio $5\%:15\%:5\%:75\%$ of the number of jobs in the subsets.

$\mathit{\delta }\%$	5%				10%				15%				20%				30%				40%				50%
$\mathit{n}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$
20	99	1475	99.32	0	96.5	2242	98.44	0	93.4	2450	97.18	0	84.7	2514	93.52	0	68.7	2340	86.07	0	49.2	2103	74.99	0	30.8	1952	63.73	0
40	99.4	4487	99.84	0	98.2	4516	99.53	0	93.5	4245	98.35	0	85.9	3850	96.21	0	52.9	3112	84.38	0	30.1	2565	71.85	0	13.7	2149	59.19	0
60	100	6924	100	0	97.6	5942	99.58	0	91.7	4936	98.30	0	80.3	4225	95.24	0	43.5	3242	82.02	0	17.7	2620	67.82	0	5.9	2282	58.15	0
80	99.8	9113	99.98	0	98.7	6863	99.78	0	92.2	5512	98.55	0	75.3	4487	94.25	0	32.8	3350	79.37	0	12.3	2686	66.57	0	3.1	2301	57.32	0
100	99.9	10,503	99.99	0	98.3	7707	99.78	0	91.4	5884	98.45	0	73	4606	93.90	0	25.9	3411	77.84	0	4.4	2744	64.72	0	1.1	2292	56.68	0
200	100	14,104	100	0	97.7	8731	99.73	0	83.2	6090	97.14	0	53	4744	89.80	0	10.2	3300	72.42	0	0.9	2486	59.90	0	0	2009	50.02	0
300	99.8	15,767	99.99	0	98.2	8987	99.80	0	77.5	6167	96.25	0	36.8	4562	85.88	0	2.3	2969	66.86	0	0	2144	53.36	0	0	1739	42.50	0
400	99.9	15,948	99.99	0	97.5	8704	99.71	0	69	5775	94.53	0	25.9	4239	82.33	0	2.1	2675	63.18	0	0	1939	48.38	0	0	1522	34.30	0
500	99.9	16,456	99.99	1	96.7	8566	99.61	1	63.5	5460	93.28	1	20.8	3926	79.67	1	1.3	2393	58.71	1	0	1695	40.94	0	0	1357	26.31	0
600	100	16,327	100	1	96.6	8386	99.59	1	58.8	5149	91.96	1	17	3616	76.94	1	1.5	2102	53.09	1	0	1510	33.77	1	0	1280	21.88	1
700	100	16,349	100	1	95.8	8152	99.48	1	52.1	4831	90.04	1	14.2	3287	73.81	1	0.6	1911	47.83	1	0	1373	27.17	1	0	1190	15.97	1
800	100	16,329	100	1	94.8	7753	99.33	1	52	4584	89.49	1	15.7	3044	72.17	1	0.4	1732	42.44	1	0	1311	23.72	1	0	1123	10.95	1
900	100	16,036	100	1	96.4	7430	99.52	2	50.3	4206	88.11	1	17.4	2760	70.04	1	0.4	1550	35.68	1	0	1223	18.23	1	0	1084	7.75	1
1000	100	15,802	100	2	94.9	7018	99.27	2	50.3	3859	87.12	2	18.8	2588	68.62	2	0.2	1460	31.64	1	0	1155	13.42	1	0	1057	5.39	1
2000	100	12,622	100	6	94.3	4221	98.63	6	65.2	2006	82.65	6	36.5	1340	52.61	5	0	1044	4.21	4	0	1009	0.89	4	0	1000	0	3
3000	100	9378	100	15	97.3	2524	98.93	14	84.7	1308	88.30	13	36.7	1080	41.39	12	0	1008	0.79	11	0	1000	0	8	0	1000	0	7
4000	100	6813	100	28	99.7	1677	99.82	25	96.4	1092	96.70	23	40.8	1012	41.50	20	0	1000	0	16	0	1000	0	14	0	1000	0	11
5000	100	4874	100	48	99.8	1318	99.85	42	98.6	1031	98.64	38	38.1	1004	38.35	33	0	1000	0	27	0	1000	0	21	0	1000	0	18
6000	100	3737	100	69	100	1178	100	62	99.4	1010	99.41	55	37.8	1003	37.99	49	0	1000	0	39	0	1000	0	31	0	1000	0	26
7000	100	2782	100	96	100	1062	100	84	99.8	1004	99.80	77	35.9	1000	35.9	68	0	1000	0	54	0	1000	0	41	0	1000	0	36
8000	100	2280	100	128	100	1024	100	112	100	1000	100	101	33.2	1000	33.2	90	0	1000	0	71	0	1000	0	57	0	1000	0	52
9000	100	1802	100	163	100	1006	100	142	99.9	1001	99.9	127	33.9	1000	33.9	112	0	1000	0	94	0	1000	0	73	0	1000	0	61
10,000	100	1536	100	199	100	1010	100	176	100	1000	100	160	31	1000	31	141	0	1000	0	114	0	1000	0	91	0	1000	0	75
Aver.	99.9	9628	99.96	33	97.78	5044	99.58	29.17	81.00	3461	94.96	26.39	40.99	2691	66.01	23.35	10.56	1939	38.55	18.96	4.98	1590	28.95	15	2.37	1406	22.18	12.78

,

Table A9. Computational results for randomly generated instances with ratio $5\%:5\%:5\%:85\%$ of the number of jobs in the subsets.

$\mathit{\delta }\%$	5%				10%				15%				20%				30%				40%				50%
$\mathit{n}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$
20	98.8	1896	99.31	0	94.9	2585	97.95	0	90.4	2763	96.20	0	82.2	2777	93.30	0	61.1	2532	83.37	0	41.9	2220	72.03	0	24.2	2063	61.66	0
40	99.5	5138	99.90	0	97.4	5066	99.49	0	92.9	4468	98.30	0	79.9	3928	94.63	0	46.8	3040	81.71	0	21.4	2588	68.66	0	8.7	2231	58.09	0
60	99.8	7963	99.97	0	98	6409	99.69	0	91.5	5209	98.33	0	72.5	4332	93.44	0	35.5	3301	80.01	0	11.5	2681	66.21	0	3.2	2349	58.49	0
80	99.7	9889	99.97	0	97.8	7272	99.68	0	88.7	5564	97.90	0	62.9	4545	91.44	0	25	3415	77.39	0	6.7	2718	65.16	0	0.6	2273	55.70	0
100	99.4	11,142	99.95	0	97.5	7878	99.67	0	86.9	5749	97.67	0	64.1	4732	92.16	0	17.4	3326	74.74	0	3.5	2705	64.07	0	0.2	2257	55.38	0
200	99.8	14,582	99.99	0	96.9	8778	99.64	0	73.5	6081	95.54	0	38.2	4773	86.80	0	2.9	3190	69.28	0	0.2	2407	58.33	0	0	1915	47.78	0
300	100	15,862	100	0	95.8	8856	99.51	0	63.9	5907	93.84	0	21.9	4440	82.27	0	0.6	2808	64.32	0	0	2070	51.64	0	0	1651	39.37	0
400	100	16,410	100	0	93.8	8685	99.25	0	51.1	5715	91.32	0	11.6	4129	78.40	0	0.1	2496	59.90	0	0	1777	43.73	0	0	1438	30.39	0
500	100	16,610	100	1	92.8	8433	99.13	1	43.5	5286	89.14	1	8.4	3665	74.92	1	0	2170	53.98	1	0	1514	33.95	1	0	1280	21.88	1
600	100	16,129	100	1	90.5	8109	98.79	1	37.3	4975	87.32	1	4.5	3355	71.51	1	0	1966	49.14	1	0	1407	28.86	1	0	1178	15.11	1
700	100	16,180	100	1	90.6	7795	98.78	1	34.7	4557	85.63	1	2.6	3089	68.37	1	0	1757	43.09	1	0	1289	22.34	1	0	1117	10.47	1
800	100	15,972	100	1	90.8	7404	98.76	1	29.3	4281	83.44	1	2.1	2723	63.90	1	0	1607	37.77	1	0	1206	17.08	1	0	1090	8.26	1
900	100	15,602	100	2	88.3	6867	98.28	2	24.7	3918	80.78	2	0.7	2547	61.01	2	0	1448	30.94	1	0	1145	12.66	1	0	1044	4.21	1
1000	100	15,428	100	2	86.6	6570	97.95	2	19.3	3586	77.44	2	0.3	2279	56.16	2	0	1314	23.90	2	0	1093	8.51	2	0	1031	3.01	1
2000	100	11,672	100	8	83	3610	95.29	8	6.2	1716	45.34	7	0	1220	18.03	7	0	1029	2.82	6	0	1010	0.99	5	0	1000	0	4
3000	100	8320	100	19	79.4	2171	90.51	18	1.9	1186	17.28	17	0	1044	4.21	15	0	1001	0.10	12	0	1000	0	10	0	1000	0	8
4000	100	5648	100	37	80.9	1472	87.02	34	1.5	1050	6.19	30	0	1007	0.70	27	0	1000	0	22	0	1000	0	18	0	1000	0	15
5000	100	4110	100	61	82.8	1186	85.50	56	0.3	1019	2.16	49	0	1002	0.20	44	0	1000	0	35	0	1000	0	29	0	1000	0	23
6000	100	2976	100	91	83.8	1091	85.15	80	0.3	1003	0.60	72	0	1000	0	91	0	1000	0	51	0	1000	0	44	0	1000	0	34
7000	100	2280	100	125	89	1036	89.38	110	0.1	1001	0.20	99	0	1000	0	88	0	1000	0	70	0	1000	0	57	0	1000	0	53
8000	100	1803	100	164	88.8	1010	88.91	145	0	1000	0	136	0	1000	0	115	0	1000	0	93	0	1000	0	75	0	1000	0	62
9000	100	1517	100	209	89.5	1003	89.53	184	0.1	1000	0.1	164	0	1000	0	147	0	1000	0	117	0	1000	0	96	0	1000	0	79
10,000	100	1290	100	270	90.5	1003	90.53	230	0	1000	0	204	0	1000	0	182	0	1000	0	147	0	1000	0	119	0	1000	0	98
Aver.	99.87	9496	99.96	43.13	90.41	4969	95.15	37.96	36.44	3393	58.47	34.17	19.65	2634	49.19	31.48	8.23	1887	36.19	24.35	3.70	1558	26.70	20	1.60	1388	20.43	16.61

,

Table A10. Computational results for randomly generated instances with ratio $3\%:2\%:5\%:90\%$ of the number of jobs in the subsets.

$\mathit{\delta }\%$	5%				10%				15%				20%				30%				40%				50%
$\mathit{n}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$
100	99.7	11511	0.9997	0	95.4	8016	0.994	0	79	5914	0.963	0	50.5	4697	0.892	0	0.6	3217	0.688	0	1	2712	0.631	0	0	2282	0.559	0
200	99.7	15,060	0.9998	0	94	8798	0.993	0	60.4	6244	0.935	0	24.3	4606	0.833	0	0.1	2812	0.643	0	0	2352	0.574	0	0	1897	0.472	0
300	99.6	15,656	0.9997	0	88	8797	0.986	0	41	5866	0.898	0	10.2	4394	0.792	0	0	2395	0.582	1	0	2002	0.499	0	0	1572	0.364	0
400	99.5	16,208	0.9997	0	81.6	8503	0.978	1	26	5641	0.868	1	3.5	3960	0.756	1	0	2142	0.533	1	0	1721	0.418	0	0	1376	0.273	1
500	99.7	16,397	0.9998	1	77.2	8360	0.973	1	20.3	5140	0.844	1	1.4	3621	0.726	1	0	1868	0.464	1	0	1555	0.357	1	0	1242	0.195	1
600	99.6	16,083	0.9998	1	71.9	7983	0.964	1	14.2	4801	0.821	1	0.7	3294	0.697	1	0	1688	0.408	1	0	1374	0.272	1	0	1171	0.146	1
700	99.6	15,873	0.9997	1	69.1	7623	0.959	1	11.2	4438	0.800	1	0.4	2956	0.663	1	0	1525	0.344	1	0	1221	0.181	1	0	1093	0.085	1
800	99.6	15,935	0.9997	2	64.6	7140	0.950	2	8.1	4116	0.776	2	0.5	2671	0.627	2	0	1403	0.287	2	0	1178	0.151	1	0	1066	0.062	1
900	99.6	15,490	0.9997	2	63.6	6760	0.945	2	4.9	3735	0.745	2	0.1	2368	0.578	2	0	1324	0.245	2	0	1110	0.099	2	0	1045	0.043	1
1000	99.7	15,121	0.9998	2	60.5	6413	0.937	3	4.4	3405	0.719	2	0	2154	0.536	2	0	1019	0.019	7	0	1091	0.083	2	0	1027	0.026	2
2000	99.9	11,277	0.9999	10	30.5	3309	0.790	9	0	1624	0.384	9	0	1195	0.163	8	0	1003	0.003	14	0	1004	0.004	7	0	1000	0	5
3000	99.8	7873	0.9997	25	19.2	1949	0.585	21	0	1154	0.133	21	0	1027	0.026	17	0	1000	0	25	0	1001	0.001	12	0	1000	0	10
4000	99.7	5275	0.9994	43	15.6	1380	0.388	39	0	1042	0.040	35	0	1007	0.007	31	0	1000	0	40	0	1000	0	22	0	1000	0	17
5000	99.9	3641	0.9997	70	9.8	1141	0.209	64	0	1008	0.008	57	0	1001	0.001	50	0	1000	0	59	0	1000	0	33	0	1000	0	27
6000	100	2667	1	102	9.1	1041	0.127	98	0	1001	0.001	82	0	1000	0	73	0	1000	0	62	0	1000	0	48	0	1000	0	39
7000	100	2045	1	141	7.6	1024	0.098	127	0	1001	0.001	118	0	1000	0	100	0	1000	0	92	0	1000	0	73	0	1000	0	54
8000	100	1633	1	186	6.2	1005	0.067	166	0	1000	0	147	0	1000	0	163	0	1000	0	105	0	1000	0	85	0	1000	0	71
9000	100	1407	1	236	4.5	1003	0.048	210	0	1000	0	186	0	1000	0	165	0	1000	0	133	0	1000	0	109	0	1000	0	89
10,000	100	1248	1	294	2.5	1000	0.025	274	0	1000	0	231	0	1000	0	206	0	1000	0	168	0	1000	0	137	0	1000	0	112
Aver.	99.77	10021	1.00	58.74	45.84	4803	0.63	53.63	14.18	3112	0.47	47.16	4.82	2313	0.38	43.32	0.04	1495	0.22	37.58	0.05	1333	0.17	28.11	0	1198	0.12	22.74

,

Table A11. Computational results for randomly generated instances with ratio $2\%:3\%:5\%:90\%$ of the number of jobs in the subsets.

$\mathit{\delta }\%$	5%				10%				15%				20%				30%				40%				50%
$\mathit{n}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$
100	99	11,556	0.999	0	94	7914	0.992	0	75	5859	0.956	0	46.8	4631	0.881	0	9.3	3418	0.731	0	0.9	2679	0.624	0	0	2206	0.544	0
200	99.3	14,862	1.000	0	90.1	8619	0.988	0	51.3	6177	0.919	0	18.5	4644	0.820	0	0.4	3093	0.676	0	0	2324	0.567	0	0	1889	0.468	0
300	99.4	15,924	1.000	0	85.8	8892	0.984	0	35.3	5901	0.888	0	6.7	4360	0.783	0	0.2	2749	0.635	0	0	2034	0.508	0	0	1611	0.379	0
400	99.6	16,312	1.000	0	77.8	8622	0.974	1	22.4	5652	0.861	1	2.6	3936	0.752	1	0	2412	0.585	1	0	1733	0.422	1	0	1371	0.270	0
500	99.7	16,305	1.000	1	72.6	8415	0.967	1	13.2	5135	0.829	1	1.2	3653	0.728	1	0	2122	0.528	1	0	1528	0.346	1	0	1232	0.188	1
600	99.2	16,297	1.000	1	66.1	7956	0.956	1	9.5	4917	0.814	1	0.5	3199	0.688	1	0	1850	0.459	1	0	1388	0.280	1	0	1179	0.152	1
700	99.7	16,252	1.000	1	58.2	7472	0.943	1	7.6	4480	0.793	2	0	2895	0.655	1	0	1660	0.398	1	0	1233	0.189	1	0	1080	0.074	1
800	99.5	16,075	1.000	2	51.8	7186	0.933	2	3.3	4088	0.763	2	0	2662	0.624	2	0	1506	0.336	1	0	1178	0.151	1	0	1061	0.057	1
900	99.4	15,617	1.000	2	48.6	6771	0.923	2	2.6	3828	0.744	2	0	2398	0.583	2	0	1379	0.275	2	0	1141	0.124	3	0	1036	0.035	1
1000	99.4	15,297	1.000	2	42.5	6381	0.909	3	2.2	3435	0.715	4	0	2114	0.527	2	0	1352	0.260	2	0	1092	0.084	3	0	1025	0.024	2
2000	98.8	11,349	0.999	10	20.1	3332	0.760	9	0	1646	0.392	9	0	1182	0.154	8	0	1024	0.023	7	0	1000	0	6	0	1001	0.001	5
3000	98.1	7777	0.998	23	5.4	1938	0.512	21	0	1166	0.142	19	0	1038	0.037	17	0	1002	0.002	14	0	1000	0	13	0	1000	0	10
4000	97.4	5297	0.995	45	3.9	1391	0.309	47	0	1037	0.036	35	0	1003	0.003	31	0	1000	0	26	0	1000	0	20	0	1000	0	17
5000	99.1	3802	0.998	70	2.2	1131	0.135	64	0	1009	0.009	56	0	1000	0	50	0	1000	0	46	0	1000	0	33	0	1000	0	27
6000	99	2686	0.996	102	0.8	1047	0.053	99	0	1003	0.003	82	0	1000	0	84	0	1000	0	58	0	1000	0	47	0	1000	0	39
7000	99.6	1996	0.998	142	0.5	1011	0.016	126	0	1001	0.001	112	0	1000	0	100	0	1000	0	87	0	1000	0	66	0	1000	0	54
8000	99.9	1641	0.999	185	0.2	1004	0.006	178	0	1000	0	150	0	1000	0	132	0	1000	0	106	0	1000	0	86	0	1000	0	70
9000	99.8	1387	0.999	236	0.2	1005	0.007	211	0	1000	0	186	0	1000	0	180	0	1000	0	134	0	1000	0	109	0	1000	0	89
10,000	99.9	1247	0.999	293	0	1001	0.001	260	0	1000	0	231	0	1000	0	205	0	1000	0	165	0	1000	0	134	0	1000	0	111
Aver.	99.25	10,088	1.00	58.68	37.94	4794	0.60	54	11.71	3123	0.47	47	4.02	2301	0.38	43	0.52	1609	0.26	34.32	0.05	1333	0.17	27.63	0	1194	0.12	22.58

,

Table A12. Computational results for randomly generated instances with ratio $2\%:2\%:1\%:95\%$ of the numbers of jobs in the subsets.

$\mathit{\delta }\%$	5%				10%				15%				20%				30%				40%				50%
$\mathit{n}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$
100	97.4	12,124	0.998	0	86.5	7871	0.982	0	58.4	5867	0.926	0	27.3	4689	0.840	0	2.8	3377	0.705	0	0.2	2727	0.630	0	0	1898	0.473	0
200	97.1	15,322	0.998	0	74.2	8612	0.969	0	30.8	6247	0.886	0	6.1	4774	0.799	0	0	3086	0.674	0	0	2326	0.568	0	0	1586	0.369	0
300	95.5	15,872	0.997	0	57	8728	0.950	0	10.8	5787	0.843	0	0.9	4379	0.771	0	0	2664	0.624	0	0	1969	0.492	0	0	1348	0.258	0
400	95	16,354	0.997	1	40.9	8608	0.930	1	5.4	5518	0.827	1	0	3918	0.743	1	0	2334	0.570	1	0	1685	0.407	1	0	1232	0.188	1
500	94.1	16,103	0.996	1	30.9	8194	0.914	1	1.1	5012	0.801	1	0	3606	0.720	1	0	2076	0.518	1	0	1439	0.305	1	0	1135	0.119	1
600	91.4	16,241	0.995	1	21	7792	0.898	1	0.7	4690	0.787	1	0	3096	0.677	1	0	1750	0.429	1	0	1322	0.244	2	0	1067	0.063	1
700	92.3	16,138	0.995	1	16.7	7403	0.886	2	0	4265	0.765	2	0	2837	0.647	2	0	1604	0.377	1	0	1201	0.167	1	0	1058	0.055	1
800	89.6	15,785	0.993	2	10.7	7081	0.873	2	0.2	3909	0.744	2	0	2544	0.606	2	0	1464	0.317	2	0	1150	0.130	1	0	1039	0.038	2
900	87.3	15,368	0.992	2	6.9	6505	0.856	2	0	3595	0.721	2	0	2321	0.569	2	0	1347	0.258	2	0	1094	0.086	2	0	1019	0.019	2
1000	84.5	15,200	0.990	3	5.2	6203	0.847	3	0	3266	0.694	3	0	2082	0.520	3	0	1254	0.203	2	0	1069	0.065	2	0	1000	0	6
2000	48.3	10,867	0.952	11	0.1	3141	0.682	11	0	1536	0.349	10	0	1163	0.140	9	0	1015	0.015	7	0	1002	0.002	6	0	1000	0	11
3000	27.9	7207	0.900	26	0	1847	0.459	24	0	1124	0.110	21	0	1011	0.011	19	0	1001	0.001	16	0	1000	0	13	0	1000	0	21
4000	14.1	4913	0.825	49	0	1304	0.233	46	0	1019	0.019	41	0	1003	0.003	35	0	1000	0	28	0	1000	0	23	0	1000	0	30
5000	6.9	3353	0.722	80	0	1125	0.111	71	0	1002	0.002	63	0	1001	0.001	57	0	1000	0	48	0	1000	0	36	0	1000	0	47
6000	3.4	2359	0.591	118	0	1037	0.036	104	0	1003	0.003	92	0	1000	0	81	0	1000	0	65	0	1000	0	53	0	1000	0	44
7000	1.9	1895	0.482	175	0	1017	0.017	142	0	1000	0	126	0	1001	0.001	112	0	1000	0	90	0	1000	0	73	0	1000	0	65
8000	0.8	1509	0.343	210	0	1003	0.003	184	0	1000	0	164	0	1000	0	146	0	1000	0	138	0	1000	0	95	0	1000	0	78
9000	0.7	1308	0.241	269	0	1001	0.001	235	0	1000	0	210	0	1000	0	187	0	1000	0	150	0	1000	0	121	0	1000	0	164
10,000	0.5	1155	0.139	330	0	1001	0.001	290	0	1000	0	257	0	1000	0	230	0	1000	0	183	0	1000	0	151	0	1000	0	123
Aver.	54.14	9951	0.80	67.32	18.43	4709	0.56	58.89	5.65	3044	0.45	52.42	1.81	2286	0.37	46.74	0.15	1577	0.25	38.68	0.01	1315	0.16	30.58	0	1125	0.08	31.42

,

Table A13. Computational results for randomly generated instances with ratio $1\%:2\%:2\%:95\%$ of the number of jobs in the subsets.

$\mathit{\delta }\%$	5%				10%				15%				20%				30%				40%				50%
$\mathit{n}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$
100	97.3	11,883	0.998	0	85.4	8060	0.981	0	58.5	5861	0.928	0	30.4	4718	0.846	0	3.2	3449	0.714	0	0.5	2646	0.621	0	0	2167	0.537	0
200	96.1	15,255	0.997	0	72.7	8727	0.968	0	29	6058	0.881	0	4.9	4698	0.795	0	0	3070	0.673	0	0	2301	0.565	0	0	1828	0.451	0
300	96.9	16,030	0.998	0	57.9	8787	0.950	0	10.6	5869	0.845	0	1.7	4304	0.770	0	0	2730	0.632	0	0	1956	0.488	0	0	1545	0.353	0
400	93.7	15,829	0.996	1	44.7	8623	0.934	1	3.9	5462	0.823	1	0	3931	0.745	1	0	2349	0.574	1	0	1629	0.386	1	0	1389	0.280	1
500	92.8	16,212	0.995	1	31.2	8178	0.915	1	1.4	5161	0.806	1	0.2	3590	0.721	1	0	2038	0.508	1	0	1472	0.321	1	0	1241	0.194	1
600	94	16,414	0.996	1	22.9	7766	0.899	1	0.8	4733	0.789	1	0	3212	0.687	1	0	1806	0.446	1	0	1310	0.237	1	0	1160	0.138	1
700	91.4	15,944	0.994	1	14	7296	0.880	2	0.2	4171	0.760	2	0	2799	0.643	1	0	1562	0.360	1	0	1235	0.190	1	0	1077	0.071	1
800	89.7	15,772	0.993	2	9.3	7079	0.870	2	0.1	3918	0.745	2	0	2510	0.602	2	0	1452	0.311	2	0	1135	0.119	1	0	1064	0.060	1
900	85.4	15,267	0.990	2	6.2	6618	0.858	2	0	3584	0.720	2	0	2259	0.557	2	0	1314	0.239	2	0	1106	0.096	2	0	1025	0.024	2
1000	84	15,005	0.989	3	3.3	6135	0.841	3	0	3251	0.692	3	0	2074	0.517	3	0	1263	0.208	2	0	1066	0.062	2	0	1014	0.014	2
2000	48.7	10,938	0.953	13	0	3157	0.683	10	0	1501	0.334	9	0	1145	0.127	9	0	1007	0.007	7	0	1001	0.001	6	0	1000	0	6
3000	27.6	7287	0.900	28	0	1792	0.441	24	0	1115	0.103	21	0	1021	0.021	22	0	1001	0.001	16	0	1000	0	13	0	1000	0	11
4000	13.7	4925	0.825	49	0	1290	0.225	44	0	1029	0.028	39	0	1006	0.006	35	0	1000	0	28	0	1000	0	24	0	1000	0	21
5000	7.9	3378	0.727	80	0	1102	0.093	72	0	1006	0.006	63	0	1000	0	56	0	1000	0	45	0	1000	0	36	0	1000	0	34
6000	4.4	2449	0.610	117	0	1049	0.047	104	0	1000	0	91	0	1000	0	81	0	1000	0	67	0	1000	0	53	0	1000	0	43
7000	2.1	1878	0.479	160	0	1019	0.019	141	0	1001	0.001	126	0	1000	0	112	0	1000	0	89	0	1000	0	74	0	1000	0	60
8000	0.9	1514	0.345	210	0	1004	0.004	185	0	1000	0	169	0	1000	0	147	0	1000	0	117	0	1000	0	96	0	1000	0	78
9000	0.4	1298	0.233	286	0	1001	0.001	236	0	1000	0	208	0	1000	0	186	0	1000	0	149	0	1000	0	121	0	1000	0	100
10,000	0.2	1165	0.143	330	0	1000	0	290	0	1000	0	303	0	1000	0	230	0	1000	0	184	0	1000	0	149	0	1000	0	123
Aver.	54.06	9918	0.80	67.58	18.29	4720	0.56	58.84	5.50	3034	0.45	54.79	1.96	2277	0.37	46.79	0.17	1581	0.25	37.47	0.03	1308	0.16	30.58	0	1185	0.11	25.53

,

Table A14. Computational results for randomly generated instances with ratio $1\%:1\%:3\%:95\%$ of the number of jobs in the subsets.

$\mathit{\delta }\%$	5%				10%				15%				20%				30%				40%				50%
n	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$
100	98.6	11,377	0.999	0	88.5	7897	0.985	0	61.8	5894	0.933	0	30	4695	0.846	0	3.5	3376	0.708	0	0.4	2676	0.620	0	0	2222	0.545	0
200	98	15,012	0.999	0	76.8	8729	0.972	0	30.8	6003	0.881	0	8.4	4701	0.800	0	0	3170	0.682	0	0	2327	0.569	0	0	1856	0.460	0
300	97.4	15,847	0.998	0	67.8	8727	0.963	0	14.3	5842	0.851	0	1.5	4258	0.767	0	0	2746	0.634	0	0	1959	0.489	0	0	1558	0.358	0
400	96.7	16,261	0.998	1	49.6	8486	0.939	1	6.1	5500	0.828	1	0.4	3922	0.745	1	0	2339	0.572	1	0	1724	0.420	1	0	1330	0.248	0
500	95.9	16,266	0.997	1	38.1	8240	0.923	1	2.7	5142	0.810	1	0	3540	0.716	1	0	2060	0.515	1	0	1457	0.314	1	0	1230	0.187	1
600	95	15,911	0.997	1	29.3	7829	0.909	1	1.3	4759	0.791	1	0	3151	0.682	1	0	1830	0.454	1	0	1325	0.245	1	0	1126	0.112	1
700	92.6	15,922	0.995	1	23.1	7315	0.894	2	0.3	4317	0.769	2	0	2806	0.643	2	0	1643	0.391	1	0	1208	0.172	1	0	1093	0.085	1
800	94.4	15,727	0.996	2	15.8	7005	0.879	2	0.4	3906	0.745	2	0	2508	0.601	2	0	1469	0.319	2	0	1154	0.133	1	0	1051	0.049	1
900	92.4	15,311	0.995	2	12.7	6628	0.868	2	0	3606	0.721	2	0	2262	0.557	2	0	1380	0.275	2	0	1102	0.093	2	0	1030	0.029	2
1000	90.2	14,979	0.993	3	8.1	6215	0.852	3	0	3231	0.690	3	0	2011	0.503	3	0	1255	0.203	3	0	1060	0.057	2	0	1020	0.020	2
2000	67.9	10,778	0.970	11	0.5	3068	0.676	10	0	1567	0.362	9	0	1147	0.128	9	0	1013	0.013	7	0	1000	0	6	0	1000	0	5
3000	51.3	7398	0.934	27	0	1775	0.437	24	0	1129	0.114	22	0	1024	0.023	19	0	1000	0	17	0	1000	0	13	0	1000	0	18
4000	34.2	4903	0.866	49	0	1306	0.234	48	0	1017	0.017	39	0	1003	0.003	35	0	1000	0	28	0	1000	0	23	0	1000	0	19
5000	22.9	3312	0.767	79	0	1113	0.102	71	0	1009	0.009	63	0	1000	0	56	0	1000	0	45	0	1000	0	36	0	1000	0	30
6000	17.6	2440	0.662	116	0	1030	0.029	103	0	1001	0.001	92	0	1000	0	82	0	1000	0	65	0	1000	0	53	0	1000	0	44
7000	15.4	1838	0.540	160	0	1016	0.016	141	0	1000	0	125	0	1000	0	111	0	1000	0	89	0	1000	0	73	0	1000	0	60
8000	10	1470	0.388	208	0	1007	0.007	185	0	1000	0	165	0	1000	0	146	0	1000	0	117	0	1000	0	95	0	1000	0	79
9000	8.4	1339	0.316	266	0	1000	0	236	0	1000	0	208	0	1000	0	185	0	1000	0	148	0	1000	0	121	0	1000	0	100
10,000	7.8	1171	0.213	331	0	1000	0	292	0	1000	0	322	0	1000	0	229	0	1000	0	200	0	1000	0	162	0	1000	0	124
Aver.	62.46	9856	0.82	66.21	21.59	4705	0.56	59.05	6.19	3049	0.45	55.63	2.12	2265	0.37	46.53	0.18	1594	0.25	38.26	0.02	1315	0.16	31.11	0	1185	0.11	25.63

and

Table A15. Computational results for randomly generated instances with ratio $1\%:1\%:1\%:97\%$ of the number of jobs in the subsets.

$\mathit{\delta }\%$	5%				10%				15%				20%				30%				40%				50%
n	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$	$\mathit{O}\mathit{p}\mathit{t}$	$\mathit{N}\mathit{C}$	$\mathit{S}\mathit{C}$	$\mathit{t}$
100	96.9	12,063	0.997	0	84.9	7901	0.980	0	52.5	5921	0.916	0	26.1	4713	0.837	0	2.4	3366	0.705	0	0	2618	0.612	0	0	2180	0.534	0
200	96.1	15,300	0.997	0	68.1	8663	0.962	0	22.1	6051	0.868	0	4.1	4665	0.791	0	0	3116	0.677	0	0	2355	0.574	0	0	1837	0.456	0
300	93.6	15,913	0.996	0	50.4	8790	0.942	0	6.9	5883	0.840	0	0.8	4267	0.765	0	0	2741	0.634	0	0	1939	0.483	0	0	1554	0.356	0
400	93.4	16,711	0.996	1	32.3	8577	0.919	1	3.1	5548	0.822	1	0	3935	0.745	1	0	2357	0.576	1	0	1667	0.400	1	0	1328	0.247	1
500	90.6	16,157	0.994	1	20.6	8180	0.902	1	1.2	5054	0.803	1	0	3430	0.708	1	0	2048	0.512	1	0	1447	0.309	1	0	1198	0.165	1
600	89.5	16,069	0.993	1	13.2	7871	0.889	1	0.1	4747	0.788	1	0	3089	0.676	1	0	1808	0.447	1	0	1326	0.246	1	0	1128	0.113	1
700	87.1	16,038	0.992	2	8.4	7320	0.874	2	0	4260	0.763	2	0	2710	0.630	1	0	1641	0.389	1	0	1200	0.167	1	0	1093	0.085	1
800	84.6	15,770	0.990	2	4.5	7035	0.863	2	0	3760	0.733	2	0	2510	0.602	2	0	1458	0.314	2	0	1148	0.129	1	0	1040	0.038	1
900	78.4	15,360	0.986	2	3.8	6525	0.851	3	0	3467	0.711	2	0	2233	0.552	2	0	1354	0.261	2	0	1091	0.083	2	0	1024	0.023	2
1000	73.7	15,050	0.982	3	2.1	6045	0.837	3	0	3186	0.686	3	0	2041	0.510	3	0	1236	0.191	2	0	1073	0.068	2	0	1016	0.016	2
2000	30.1	10,811	0.935	12	0	3034	0.670	11	0	1538	0.350	10	0	1147	0.128	9	0	1012	0.012	8	0	1003	0.003	7	0	1000	0	6
3000	11.8	7095	0.875	28	0	1790	0.441	25	0	1110	0.099	22	0	1020	0.020	20	0	1000	0	16	0	1000	0	13	0	1000	0	11
4000	3.5	4711	0.795	51	0	1274	0.215	61	0	1030	0.029	41	0	1001	0.001	36	0	1000	0	29	0	1000	0	24	0	1000	0	21
5000	0.7	3274	0.696	84	0	1104	0.094	74	0	1003	0.003	67	0	1000	0	59	0	1000	0	47	0	1000	0	41	0	1000	0	32
6000	0.3	2335	0.573	121	0	1039	0.038	107	0	1001	0.001	95	0	1000	0	85	0	1000	0	68	0	1000	0	55	0	1000	0	46
7000	0.1	1747	0.428	166	0	1009	0.009	147	0	1000	0	130	0	1000	0	117	0	1000	0	93	0	1000	0	76	0	1000	0	63
8000	0	1487	0.328	218	0	1005	0.005	194	0	1000	0	170	0	1000	0	151	0	1000	0	123	0	1000	0	100	0	1000	0	81
9000	0	1281	0.219	280	0	1000	0	266	0	1000	0	217	0	1000	0	194	0	1000	0	155	0	1000	0	126	0	1000	0	105
10,000	0	1164	0.141	344	0	1000	0	305	0	1000	0	268	0	1000	0	239	0	1000	0	298	0	1000	0	156	0	1000	0	130
Aver.	48.97	9912	0.78	69.26	15.17	4693	0.55	63.32	4.52	3029	0.44	54.32	1.63	2251	0.37	48.47	0.13	1586	0.25	44.58	0	1309	0.16	31.95	0	1179	0.11	26.53

for 15 classes of the solved instances. Each tested class of the instances of the problem $J2|l_{ij}\le p_{ij}\le u_{ij},n_i\le 2|C_{max}$ is characterized by the following ratio of the percentages of the number of jobs in the subsets ${\mathcal{J}}_1$, ${\mathcal{J}}_2$, ${\mathcal{J}}_{1,2}$, and ${\mathcal{J}}_{2,1}$ of the set $\mathcal{J}$:

$$\frac{m_1}{n}·100\%:\frac{m_2}{n}·100\%:\frac{m_{1,2}}{n}·100\%:\frac{m_{2,1}}{n}·100\%$$

(18)

Table A1, Table A2, Table A3, Table A4, Table A5, Table A6, Table A7, Table A8 and Table A9 present the computational results obtained for classes 1–9 of the tested instances characterized by the following ratios (Equation (18)):

$25\%:25\%:25\%:25\%$ (Table A1); $10\%:10\%:40\%:40\%$ (Table A2);

$10\%:40\%:10\%:40\%$ (Table A3); $10\%:30\%:10\%:50\%$ (Table A4);

$10\%:20\%:10\%:60\%$ (Table A5); $10\%:10\%:10\%:70\%$ (Table A6);

$5\%:20\%:5\%:70\%$ (Table A7); $5\%:15\%:5\%:75\%$ (Table A8);

$5\%:5\%:5\%:85\%$ (Table A9).

Note that all instances from class 1 of the instances with the ratio from Equation (18), $25\%:25\%:25\%:25\%$, were optimally solved by Algorithms 1–4 for all values of $\delta \in \{5\%,10\%,$$15\%,20\%,30\%,40\%,$ and $50\%\}$. We also tested classes 10–15 of the hard instances of the problem $J2|l_{ij}\le p_{ij}\le u_{ij},n_i\le 2|C_{max}$ characterized by the following ratios (Equation (18)):

$3\%:2\%:5\%:90\%$ (Table A10); $2\%:3\%:5\%:90\%$ (Table A11);

$2\%:2\%:1\%:95\%$ (Table A12); $1\%:2\%:2\%:95\%$ (Table A13);

$1\%:1\%:3\%:95\%$ (Table A14); $1\%:1\%:1\%:97\%$ (Table A15).

All Table A1, Table A2, Table A3, Table A4, Table A5, Table A6, Table A7, Table A8, Table A9, Table A10, Table A11, Table A12, Table A13, Table A14 and Table A15 are organized as follows. Number n of given jobs $\mathcal{J}$ in the instances of the problem $J2|l_{ij}\le p_{ij}\le u_{ij},n_i\le 2|C_{max}$ are presented in column 1. The values of $\delta$ (a maximum relative length of the given segment of the job durations) in percentages are presented in the first line of each table. For the fixed value of $\delta$, the obtained computational results are presented in four columns called $Opt$, $NC$, $SC$, and t. The column $Opt$ determines the percentage of instances from the series of 1000 randomly generated instances which were optimally solved using Algorithms 1–4. For each such instance, an optimal pair $({\pi }^{\prime },{\pi }^{″})$ of the job permutations was constructed in spite of the uncertain durations of the given jobs $\mathcal{J}$. In other words, the equality $C_{max}({\pi }^{\prime },{\pi }^{″})=C_{max}({\pi }^{*},{\pi }^{**})$ holds, where $({\pi }^{*},{\pi }^{**})\in S$ is a pair of job permutations which is optimal for the deterministic problem $J2|p^{*},n_i\le 2|C_{max}$ associated with the factual scenario $p^{*}\in T$. The factual scenario $p^{*}\in T$ for the instance of the uncertain problem $J2|l_{ij}\le p_{ij}\le u_{ij},n_i\le 2|C_{max}$ is assumed to be unknown until completing the jobs $\mathcal{J}$.

Column $NC$ presents total number of conflict sets of the jobs in the partial strict orders $A_{\prec }^{1,2}$ on the job sets ${\mathcal{J}}_{1,2}$ and partial strict orders $A_{\prec }^{2,1}$ on the job sets ${\mathcal{J}}_{2,1}$ constructed by Algorithm 2. The value of $NC$ is equal to the total number of decision points, where Algorithm 2 has to select an order for processing jobs from the corresponding conflict set. To make a correct decision for such an order means to construct a permutation of all jobs from the conflict set, which is optimal for the factual scenario (which is unknown before scheduling). In particular, if all conflict sets have received correct decisions in Algorithm 2, then the constructed pair of job permutations will be optimal for the problem $J2|p^{*},n_i\le 2|C_{max}$, where $p^{*}\in T$ is the factual scenario.

Column $SC$ presents a percentage of the correct decisions made for determining optimal orders of the conflict jobs by Algorithm 2 with Algorithms 3 and 4. Column t presents a total CPU time (in seconds) for solving all 1000 instances of the corresponding series.

Average percentages of the instances which were optimally solved ($Opt$) are presented in Figure 1 for classes 1–9 of the tested instances and in Figure 2 for classes 10–15 of the hard-tested instances.

Percentages of the average values of the correct decisions ($SC$) made for determining optimal orders of the conflict jobs for classes 1–9 are presented in Figure 3. Most instances from these nine classes were optimally solved (

Table 2. Average percentage of the instances which were optimally solved.

$\mathit{\delta }\%$	5%	10%	15%	20%	30%	40%	50%	Average
Instances from Table A1, Table A2, Table A3, Table A4, Table A5, Table A6, Table A7, Table A8 and Table A9	99.93	98.48	88.93	80.66	63.97	50.18	44.10	75.18
Instances from Table A10, Table A11, Table A12, Table A13, Table A14 and Table A15	69.78	24.89	7.96	2.73	0.20	0.03	0.00	15.08

). 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 were optimally solved in spite of the data uncertainty. If the value $\delta$ is increased, the percentage of the optimally solved instances decreased. If the value $\delta$ was equal to $50\%$, then $45\%$ of the tested instances was optimally solved.

For all series of the hard instances presented in Table A10, Table A11, Table A12, Table A13, Table A14 and Table A15 (see the third line in Table 2), only a few instances were optimally solved. If $\delta =5\%$, then $70\%$ of the tested instances was optimally solved. If value $\delta$ belongs to the set $\{20\%,30\%,40\%,50\%\}$, then only $1\%$ of the tested instances was optimally solved. There were no hard-tested instances optimally solved for the value of $\delta =50\%$.

Percentages of the average values of the correct decisions made for determining optimal orders of the conflict jobs by Algorithm 2, Algorithm 3 and Algorithm 4 for the hard classes 10–15 of the tested instances are presented in Figure 4. Note that there is a correlation between values of $Opt$ and $SC$ presented in Figure 1 and Figure 3 for classes 1–9 of the tested instances and those presented in Figure 2 and Figure 4 for classes 10–15 of the hard-tested instances.

8. Concluding Remarks and Future Works

The uncertain flow-shop scheduling problem $F2|l_{ij}\le p_{ij}\le u_{ij}|C_{max}$ and its generalization the job-shop problem $J2|l_{ij}\le p_{ij}\le u_{ij},n_i\le 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 }^{″})$ of job permutations (Theorems 7–12). Using these properties, we derived Algorithms 1–4 for constructing optimal pairs $({\pi }^{\prime },{\pi }^{″})$ of job permutations or a small dominant set of schedules for the problem $J2|l_{ij}\le p_{ij}\le u_{ij},n_i\le 2|C_{max}$. If it is impossible to construct a single pair $({\pi }^{\prime },{\pi }^{″})$ 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}\le p_{ij}\le u_{ij},n_i\le 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}\le p_{ij}\le u_{ij},n_i\le 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 \ge 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}\le p_{ij}\le u_{ij},n_i\le 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}\le p_{ij}\le u_{ij},n_i\le 2|C_{max}$ at the 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.

We suggest to investigate properties of the optimality box and optimality region for a pair $({\pi }^{\prime },{\pi }^{″})$ of the job permutations and to develop algorithms for constructing a pair $({\pi }^{\prime },{\pi }^{″})$ of the job permutations that have the largest optimality box (or the largest optimality region). We also suggest to apply the stability approach for solving the uncertain flow-shop and job-shop scheduling problems with $\left|\mathcal{M}\right|>2$ available machines.