# Differential Evolution Algorithm Combined with Uncertainty Handling Techniques for Stochastic Reentrant Job Shop Scheduling Problem

Authors: Rong Hu; Xing Wu; Bin Qian; Jianlin Mao; Huaiping Jin
Journal: Complexity
 (2022)

---

## Abstract

This paper considers two kinds of stochastic reentrant job shop scheduling problems (SRJSSP), i.e., the SRJSSP with the maximum tardiness criterion and the SRJSSP with the makespan criterion. Owing to the NP-complete complexity of the considered RJSSPs, an effective differential evolutionary algorithm (DEA) combined with two uncertainty handling techniques, namely, DEA_UHT, is proposed to address these problems. Firstly, to reasonably control the computation cost, the optimal computing budget allocation technique (OCBAT) is applied for allocating limited computation budgets to assure reliable evaluation and identification for excellent solutions or individuals, and the hypothesis test technique (HTT) is added to execute a statistical comparison to reduce some unnecessary repeated evaluation. Secondly, a reentrant-largest-order-value rule is designed to convert the DEA’s individual (i.e., a continuous vector) to the SRJSSP’s solution (i.e., an operation permutation). Thirdly, a conventional active decoding scheme for the job shop scheduling problem is extended to decode the solution for obtaining the criterion value. Fourthly, anInsert-based exploitation strategy and an Interchange-based exploration strategy are devised to enhance DEA’s exploitation ability and exploration ability, respectively. Finally, the test results and comparisons manifest the effectiveness and robustness of the proposed DEA_UHT.


---

## Body

## 1. Introduction

The job shop scheduling problem (JSSP) is one of the most well-known combinatorial optimization problems. As a variant of the JSSP, the reentrant JSSP (RJSSP) can be found in many real-life production and manufacturing environments, such as in semiconductor manufacturing enterprises [1, 2] and textile factories [3]. The main characteristic of the RJSSP is that one job may visit a set of machines more than once during the production process. Since the JSSP has NP-complete property [4] and it can be reduced to the RJSSP, the latter is also NP-complete. The studies on the RJSSP are still limited. Pan and Chen [5] presented two extended binary integer programming formulations for the RJSSP. Topaloglu and Kilincli [6] proposed a modified shifting bottleneck heuristic for the RJSSP with makespan criterion. Chen et al. [7] presented a hybrid estimation of distribution algorithm for the RJSSP with sequence-dependent setup times to minimize makespan.As we all know, uncertainties are very common in many real-world manufacturing scenarios. At present, some uncertain JSSPs have been studied. Most of them are the JSSP with stochastic processing times [8–22], and the rest are the JSSP with probabilistic machine availability [23], the JSSP with fuzzy processing times [24], and the JSSP with fuzzy machine availability [25]. In these studies, evolutionary algorithms are the main methodology, and makespan or tardiness/earliness is the main optimization criterion. In terms of the JSSP with stochastic processing times, how to evaluate the solution’s expected objective value (i.e., criterion value) reasonably is one of the key links in the design of the algorithm. The direct method is to sample the corresponding stochastic model multiple times to obtain multiple objective values, and then use the average of these sampling values as an approximate estimation of the expected objective value. Obviously, the more the sampling times, the more stable and reliable the estimated value is. This method is the most used method in existing research. However, such a method usually has a high computation cost. Thus, several researchers have adopted three types of techniques to control and reduce the computation cost. The first is the optimal computing budget allocation technique (OCBAT) [26]. Zhang et al. [13] and Yang et al. [16] utilized it to allocate limited computation budgets to assure more reliable evaluation for better solutions. The second is the problem conversion technique. Shen and Zhu [19] used it to convert the stochastic models of the JSSPs to the deterministic ones, in which the confidence or robustness level is considered. Then, the objective value of each solution was calculated via these deterministic models. The third is the objective value prediction technique, which is mainly driven by the simulation metamodel. Ghasemi et al. [22] constructed a metamodel by using genetic programming (GP) to directly predict the solution’s objective value. However, as for the uncertain RJSSPs, only Mohammadi [27] designed a simulated annealing algorithm and a genetic algorithm for the RJSSP with fuzzy processing times to minimize makespan, and the stochastic RJSSP has not been studied until now.From the above literature review, it can be known that it is very necessary to carry out a study on the stochastic RJSSP. Hence, the RJSSP with stochastic processing time is considered here. Recently, many effective evolutionary algorithms have been successfully designed to deal with different complex optimization problems [28–37]. For example, Duan et al. [28] developed a hybrid estimation of distribution algorithm for the distributed permutation flow shop scheduling problem (FSSP) with flowline eligibility. Guo et al. [31] proposed a particle swarm optimization algorithm for the dynamic multi-objective vehicle routing problem. Sang et al. [33] presented three invasive weed optimization algorithms for the distributed assembly permutation FSSP. Guo et al. [36] devised a novel interactive preference-based multiobjective evolutionary algorithm for the optimization problem of the bolt supporting network. Zhang et al. [37] designed a matrix-cube-based estimation of distribution algorithm for the distributed assembly permutation FSSP. Computational comparisons demonstrated that these evolutionary algorithms can obtain very satisfactory solutions with a reasonable computational time. Due to the NP-completeness of the stochastic RJSSP, an effective population-based evolutionary algorithm, i.e., differential evolution algorithm (DEA), is also selected to deal with this complex problem. DEA was firstly presented for addressing optimization problems in continuous domain [38, 39]. Because of its simple concept and quick convergence, DEA has gained many applications in a variety of fields. Nevertheless, owing to its continuous nature, the studies on DEA for the JSSPs is still very limited. Thus, in this paper, an enhanced DEA integrated with uncertainty handling techniques (DEA_UHT) is designed for solving the stochastic RJSSP under the maximum tardiness Tmax and the stochastic RJSSP under the makespan Cmax.The main features of DEA_UHT lie in two aspects: the reasonable uncertainty handling techniques and the effective DEA-based search. As for the uncertainty handling techniques, not only is the aforementioned OCBAT used to identify better solutions (i.e., individuals) with high confidence under limited computation cost but also the hypothesis test technique (HTT) is added to avoid the unnecessary repetitive evaluation for the poor solutions. That is, the solutions with high quality can be selected during the DEA’s search process, which is helpful to guide the algorithm search faster to the truly promising regions in the stochastic solution space. As for the DEA-based search, anInsert-based exploitation strategy and an Interchange-based exploration strategy are devised to enhance DEA’s exploitation ability and exploration ability, respectively. The test results and comparisons verify the effectiveness and robustness of the proposed DEA_UHT.The remainder of the paper is organized as follows. Two kinds of stochastic RJSSPs are introduced in the next section. The basic DEA, OCBAT, and HTT are briefly described in Section3. After presenting the solution representation, the extended decoding scheme, the revised OCBAT, and two special crossover strategies, DEA_UHT is proposed via combining DEA with OCBAT and HTT in Section 4. The test results and comparisons are given and analyzed in Section 5. Finally, concluding remarks and further study directions are summarized in Section 6.


## 2. Stochastic RJSSP

Consider the stochastic RJSSP that consists ofn jobs and m machines. Each job should be processed on each machine L (L > 1) times. The processing time of each job on each machine is a random value under a certain distribution. Let π=π1,π2,…,πn×m×L denote the operation-based solution or sequence to be processed, πjj∈1,…,n×m×L and πj∈1,…,n the jth job in π, lπj the repeat or reentrant times of job πj in π1,π2,…,πj, ξ the noise or uncertain factors, pπj,k,lπj,ξ the lπjth stochastic processing time of job πj on machine k, ECπj,lπj,ξ the lπjth expected completion time of job πj, dπj the due date of job πj, ELπj,ξ=ECπj,L,ξ−dπj the excepted lateness of job πj, ETπj,ξ=maxELπj,ξ,0 the excepted tardiness of job πj. Here pπj,k,lπj,ξ is supposed to be subjected to a uniform distribution U1−ξEPπj,k,lπj, 1+ξEPπj,k,lπj], where Pπj,k,lπj is the expected processing time and ξ denotes noise magnitude.Then, the expected maximum tardinessETmaxπ,ξ can be given as(1)ETmaxπ,ξ=maxET1,ξ,…,ETn,ξ.The stochastic RJSSP under the maximum tardiness (SRJSSP-Tmax) can be formulated as(2)minπ∈ΠETmaxπ,ξ,where Π denotes the set of all possible permutations.Similarly, the expected makespanECmaxπ,ξ can be given as(3)ECmaxπ,ξ=maxECπ1,L,ξ,…,ECπn,L,ξ.The stochastic RJSSP under the makespan (SRJSSP-Cmax) can be formulated as(4)minπ∈ΠECmaxπ,ξ,where Π denotes the set of all possible permutations.Obviously, infinite sampling of the above problem model can make the objective values of equations (1) and (3) stable, but in fact it is practically impossible. In the actual calculation, the value of equations (1) or (3) is usually approximated by the average of finite sampling values (e.g., Monte Carlo simulation) [8–18]. Thus, ETmaxπ,ξ can be estimated with(5)Tmaxπ,ξ¯=∑ll=1LLTmaxπ,ξLL.andECmaxπ,ξ can be estimated with(6)Cmaxπ,ξ¯=∑ll=1LLCmaxπ,ξLL.


## 3. Introduction to DEA, OCBAT, and HTT

### 3.1. DEA

Differential evolution algorithm (DEA) [38, 39] is a kind of evolutionary algorithms for solving continuous optimization problems. The basic DEA aims at finding the global optimal solutions by using the differentiations among current individuals. Specifically, each individual’s search behavior is dynamically controlled via changing the differentiation’s direction and step length. At each generation, the mutation and crossover operators are applied to current individuals to generate a candidate population, and then the selection operator is utilized to determine a new population of the next generation. Nowadays, there are several variants/schemes of DEA.


### 3.2. OCBAT

OCBAT is a dynamic allocation technique of computing budget [26, 40]. Specifically, it can optimize the sampling times for each candidate solution so that the truly better solutions can be identified under a given computation cost. Denote S the total number of potential solutions, nik (resp. nbk) the computation cost or sampling times allocated to solution i (resp. the current best solution) after the kth allocation, sik (resp. sbk) the standard deviation among the sampling objective values of solution i (resp. the current best solution) after the kth allocation, fik¯ (resp. fbk¯) the average sampling objective value of solution i (resp. the current best solution) after the kth allocation, δb,ik=fbk¯−fik¯ the difference between fbk¯ and fik¯ after the kth allocation, Tk the total sampling times after the kth allocation, and T the given total sampling times.According to the above definitions, the standard OCBAT’s algorithm is provided as follows:Step 0. Set k=0, nik=n0i=1,2,...,S and Tk=∑i=1Snik.Step 1. If ∑i=1Snik≥T, the algorithm should be stopped.Step 2. Execute nik samples (i.e., simulation replications) for each solution i, and then set Tk+1=Tk+Δ.Step 3. Calculate each nik+1 via using nbk+1=sbk∑i=1,i≠bSnik2/sik21/2 and nik+1/njk+1=sik/δb,ik/sjk/δb,jk2i≠j≠b.Step 4. Execute maxnik+1−nik,0 samples for each solution i.Step 5. Set k=k+1, and return to Step 1.Based on Reference [26], the recommended value ranges of n0 and Δ are [5, 20] and [S/5, S/10], respectively.


### 3.3. HTT

HTT is a statistical inference method that can be used to judge whether the difference between two solutionsi and j is caused by sampling error or essential difference [41]. Let the null hypothesis H0 be “fi=fj,” and then the alternative hypothesis H1 is “fi≠fj.” Based on the statistical theory, the critical region of H0 is defined as follows:(7)fi¯−fj¯≥Tα/2=tα/2ni+nj−2×ni−1si2+nj−1sj2ni+nj−2×ni+njninj,where t is the t distribution and α is the evidence level. When fi¯−fj¯>Tα/2, it can be judged that solution j is better than solutions i.


## 3.1. DEA

Differential evolution algorithm (DEA) [38, 39] is a kind of evolutionary algorithms for solving continuous optimization problems. The basic DEA aims at finding the global optimal solutions by using the differentiations among current individuals. Specifically, each individual’s search behavior is dynamically controlled via changing the differentiation’s direction and step length. At each generation, the mutation and crossover operators are applied to current individuals to generate a candidate population, and then the selection operator is utilized to determine a new population of the next generation. Nowadays, there are several variants/schemes of DEA.


## 3.2. OCBAT

OCBAT is a dynamic allocation technique of computing budget [26, 40]. Specifically, it can optimize the sampling times for each candidate solution so that the truly better solutions can be identified under a given computation cost. Denote S the total number of potential solutions, nik (resp. nbk) the computation cost or sampling times allocated to solution i (resp. the current best solution) after the kth allocation, sik (resp. sbk) the standard deviation among the sampling objective values of solution i (resp. the current best solution) after the kth allocation, fik¯ (resp. fbk¯) the average sampling objective value of solution i (resp. the current best solution) after the kth allocation, δb,ik=fbk¯−fik¯ the difference between fbk¯ and fik¯ after the kth allocation, Tk the total sampling times after the kth allocation, and T the given total sampling times.According to the above definitions, the standard OCBAT’s algorithm is provided as follows:Step 0. Set k=0, nik=n0i=1,2,...,S and Tk=∑i=1Snik.Step 1. If ∑i=1Snik≥T, the algorithm should be stopped.Step 2. Execute nik samples (i.e., simulation replications) for each solution i, and then set Tk+1=Tk+Δ.Step 3. Calculate each nik+1 via using nbk+1=sbk∑i=1,i≠bSnik2/sik21/2 and nik+1/njk+1=sik/δb,ik/sjk/δb,jk2i≠j≠b.Step 4. Execute maxnik+1−nik,0 samples for each solution i.Step 5. Set k=k+1, and return to Step 1.Based on Reference [26], the recommended value ranges of n0 and Δ are [5, 20] and [S/5, S/10], respectively.


## 3.3. HTT

HTT is a statistical inference method that can be used to judge whether the difference between two solutionsi and j is caused by sampling error or essential difference [41]. Let the null hypothesis H0 be “fi=fj,” and then the alternative hypothesis H1 is “fi≠fj.” Based on the statistical theory, the critical region of H0 is defined as follows:(7)fi¯−fj¯≥Tα/2=tα/2ni+nj−2×ni−1si2+nj−1sj2ni+nj−2×ni+njninj,where t is the t distribution and α is the evidence level. When fi¯−fj¯>Tα/2, it can be judged that solution j is better than solutions i.


## 4. DEA_UHT for Stochastic RJSSP

### 4.1. Encoding Scheme

Since DEA’s individual is a real vector, a conventional DEA cannot be directly used to deal with the discrete optimization problem. Thus, we utilize a reentrant-largest-order-value (RLOV) rule derived from the existing largest-order-value (LOV) rule [42] to transform DEA’s ith individual Xi=xi,1,xi,2,…,xi,n×m×L to the job sequence πi=πi,1,πi,2,…,πi,n×m×L. Based on the RLOV rule, the elements in Xi are firstly ranked by descending order to obtain a temporary discrete sequence φi=φi,1,φi,2,…,φi,n×m×L. Then, the operation-based solution πi can be generated via(8)πi,k=φi,k−1m×L+1,where x is an operator to get the integral part of (e.g., 2.78=2). Table 1 illustrates the encoding of vector Xi in DEA for a small RJSSP L=3,n=2,m=1.Table 1
Solution’s encoding scheme.
Dimensionk123456xi,k2.160.331.513.670.862.79φi,k364152πi,k122121


### 4.2. Decoding Scheme

Based on the characteristics of RJSSP, an optimal solution must be an active schedule under regular criteria (e.g., the maximum tardinessTmax and the makespan Cmax) [43]. This means that the solution’s quality can be improved via transforming the semi-active schedule into the active one. Therefore, when decoding a solution to a feasible schedule, each operation should be filled in the first idle time interval in the current Gantt chart instead of the last idle time interval. This active decoding scheme is utilized in our proposed algorithm.LetMi,j,l be the machine number of the jth operation that processes the lth reentrant job I, Ti,j,l the processing time of the lth reentrant job j on machine i, and Sπi,j the possible earliest starting time of job πi,j. Notice that the value of Sπi,j should meet the following inequality:(9)maxSπi,j,t1+TMπi,j,πi,j,lπi,j≤t2,where Mπi,j=Mπi,j,hπi,j,lπi,j, and [t1, t2] represents any idle time interval on the machine.Based on the above definitions, the decoding scheme that generates an active schedule for a RJSSP’s solutionπi is provided as follows:Step 1. Set kw=1 and lw=1, w=1,…,nandj=1.Step 2. If kπi,j>1 and (kπi,j mod m=1), then set lπi,j=lπi,j+1.Step 3. Set hπi,j=kπi,j−lπi,j−1×m.Step 4. Calculate Sπi,j, and set kπi,j=kπi,j+1.Step 5. Set j=j+1. If j≤n×m×L, then return to Step 2.


### 4.3. Application of Roulette Wheel Rule in OCBAT

For stochastic RJSSPs, the difference betweenδb,ik and δb,jk (i≠j) is usually much larger than that between si and sj. This can cause ∑i=1Smaxnik+1−nik,0≫Δ. Based on Step 4 of the standard OCBAT (see Section 3.2), the repeated times of Steps 1–5 of this standard algorithm may be much less than T−n0/Δ. That is, the number of times that OCBAT can be used to dynamically allocate computing budget is very limited. As a result, the reliable evaluation ability of OCBAT cannot be well utilized.Under this situation, the so-called “most starving” rule [40] is usually used to handle this obstacle. However, this rule sets Δ to 1 and needs to execute the OCBAT’s Steps 1–5 T times. This may increase the running time of the OCBAT’s algorithm. Since the OCBAT decides the budget fractions instead of the number, here we utilize the “roulette wheel” rule to allocate Δ. That is, Step 4 of the standard OCBAT should be changed to the following two substeps:Step 4.1. Calculate the allocation probability Pik+1Pik+1=nik+1/∑i=1Snik+1 for each solution i at (k+1) th allocation.Step 4.2. Apply the “roulette wheel” rule to allocate Δ to each solution i according to Pik+1, and update each nik+1.


### 4.4. Special Exploitation and Exploration Strategies

Based on References [44, 45], the solution space of the RJSSP can be regarded as a “big valley,” where the local optima are often close to each other, and close to the global optima at the bottom of the “big valley,” and either the Insert-based operator or the Interchange-based operator can execute a more compact search. Meanwhile, DEA has been proved to be an effective algorithm to find the promising solutions or regions in the whole valley [42, 44]. As for the stochastic RJSSP, the shape and the bottom regions of the big valley are always changing. Thus, to improve our DEA_UHT’s search ability, we devise an Insert-based exploitation strategy and an Interchange-based exploration strategy to replace DEA’s original mutation and crossover, which cannot obtain enough promising solutions. The former strategy selects some reliable good individuals identified by OCBAT and HTT to replace some poor individuals, and executes an Insert-based operator on these selected individuals. The latter strategy performs an Interchange-based operator guided by DEA’s basic scheme on all individuals except those replaced poor individuals. The detailed procedures of these strategies are provided in Step 5 in the next section.


### 4.5. DEA_UHT

In DEA_UHT, DEA-based search is devised according to the DE/rand-to-best/1/exp strategy to perform global search or exploration, where the base vector is the current best individual. Therefore, the information of the best individual can be shared by other individuals. By incorporating OCBAT, HTT, and two special exploitation and exploration strategies into DEA, a hybrid approach, namely, DEA_UHT, is proposed for the stochastic RJSSP.DenoteG a generation, Popt a population with size PS at generation t, W_Popt an archive set to save the individuals which need to adopt the special Insert-based crossover, Xit the ith individual with dimension N (N=n) in Popt, Tmp_Popt a temporary population with size PS in generation t, Tmp_Xit the ith individual in Tmp_Popt, xi,kt the kth variable/component of individual Xit, tmpk the kth variable of tmp, tmp01k the kth variable of tmp01, CR the crossover probability, F the scaling factor, O_dxi,kt=φi,kt the ordinal number of xi,kt in Xit in descending order (see Section 4.1), RO_dxi,kt=πi,kt the xi,kt’s corresponding job number in the job permutation πit (see Section 4.1), and random0,1 the random value in the interval [0, 1]. Based on these definitions, the framework of DEA_UHT is given as follows:Step 1. Input N, PS≥3, CR∈0,1, and let bounds be lowerxi,k=0 and upperxi,k=4, k=1,…,N.Step 2. Population initializationStep 2.1. Generate xi,k0=lowerxi,k+random0,1∗upperxi,k−lowerxi,k,k=1,…,N for i=1,…,PSStep 2.2. Use the algorithm of OCBAT in Sections3.2 and 4.3 to allocate T sampling budgets (i.e., evaluation times) for all individuals while estimating the objective values of all individuals and set W_Pop0=null set.Step 3. Set t=1 and select an individual Xbest0 from Pop0 as bestit with the minimum objective value.Step 4. Evolution phase (between Steps 4 and 9). Set i=1.Step 5.Mutation and crossover phase.Step 5.1. If Xit−1 belongs to W_Popt−1, then execute the Insert-based exploitation (see Section 4.4).Step 5.1.1. Randomly select one individual from the best five percent of Popt−1 and set it as tmp.Step 5.1.2. Randomly generate u and v (u<v), and randomly set r_i to 1 or 2.Step 5.1.3. If r_i=1, then insert tmpu after tmpv.Step 5.1.4. If r_i=2, then insert tmpv before tmpu.Step 5.1.5. Settmp_Xit=tmp and go to Step 6.Step 5.2. Perform the Interchange-based exploration (see Section 4.4). Set the trial vectortmp=Xit−1, tmp01=Xit−1 and L′=0. Randomly select r1,r2∈1,…,PS, where r1≠r2≠i, and randomly select k∈1,…,N.Step 5.2.1. Set tmpk=tmpk+F∗bestitk−tmpk+F∗xr1,kt−1−xr2,kt−1, and v1=O_dtmpk.Step 5.2.2. If RO_dtmpk<>RO_dtmp01k, then find u1 satisfying O_dtmp01u1=v1 and interchange tmp01k with tmp01u1; else randomly generate v1 (RO_dtmp01k<>RO_dtmp01v1) and interchange tmp01k with tmp01v1.Step 5.2.3. Set tmp=tmp01.Step 5.2.4. Set k=k+1 mod N and L′=L′+1.Step 5.2.5. If random0,1<CR and L′<2, then return to Step 5.2.1.Step 5.2.6. Set Tmp_Xit=tmp.Step 6. Set i = i+1. If i≤PS, then return to Step 5.Step 7. Use the algorithm of OCBAT in Sections 3.2 and 4.3 to estimate the objective values of all individuals of Tmp_popt.Step 8. Selection phase. Perform HHT in Section 3.3 on Tmp_Xit with Xit−1, i=1,…,PS.Step 8.1. If the null hypothesis holds and J¯Xit−1−J¯Tmp_Xit>τ, then set a Boolean variable b_replace = true; else set b_replace = falseStep 8.2. If b_replace = true then set Xit=Tmp_Xit; else set Xit=Xit−1.Step 8.3. If b_replace = true and J¯Tmp_Xit<J¯bestit, then set bestit=Tmp_Xit.Step 8.4. If b_replace = false and Xit−1 is in the worst 20 percent of Popt−1, then add Xit−1 to W_Popt.Step 9. Set t = t+1. If t≤t_max (the maximum generation), then return to Step 4.Step 10. Output πoutput (πoutput=bestit) and its objective value.From the above procedure, it can be known that DEA_UHT not only utilizes OCBAT to ensure reliable evaluation for good solutions but also adopts HTT to reduce repetitive search. Furthermore, the DEA-based search combined with two special strategies is devised to effectively execute exploration and exploitation in solution space. Meanwhile, “L′<2” in Step 5.2.5 is used to control the search range of the Interchange-based exploration. In addition, it is worth noting that although Step 5.1 (resp. Step 5.2) directly performs the Insert (resp. Interchange) operation on the individual, it is equivalent to performing the same Insert (resp. Interchange) operation on the corresponding permutation of this individual (see the RLOV rule in Section 4.1).


## 4.1. Encoding Scheme

Since DEA’s individual is a real vector, a conventional DEA cannot be directly used to deal with the discrete optimization problem. Thus, we utilize a reentrant-largest-order-value (RLOV) rule derived from the existing largest-order-value (LOV) rule [42] to transform DEA’s ith individual Xi=xi,1,xi,2,…,xi,n×m×L to the job sequence πi=πi,1,πi,2,…,πi,n×m×L. Based on the RLOV rule, the elements in Xi are firstly ranked by descending order to obtain a temporary discrete sequence φi=φi,1,φi,2,…,φi,n×m×L. Then, the operation-based solution πi can be generated via(8)πi,k=φi,k−1m×L+1,where x is an operator to get the integral part of (e.g., 2.78=2). Table 1 illustrates the encoding of vector Xi in DEA for a small RJSSP L=3,n=2,m=1.Table 1
Solution’s encoding scheme.
Dimensionk123456xi,k2.160.331.513.670.862.79φi,k364152πi,k122121


## 4.2. Decoding Scheme

Based on the characteristics of RJSSP, an optimal solution must be an active schedule under regular criteria (e.g., the maximum tardinessTmax and the makespan Cmax) [43]. This means that the solution’s quality can be improved via transforming the semi-active schedule into the active one. Therefore, when decoding a solution to a feasible schedule, each operation should be filled in the first idle time interval in the current Gantt chart instead of the last idle time interval. This active decoding scheme is utilized in our proposed algorithm.LetMi,j,l be the machine number of the jth operation that processes the lth reentrant job I, Ti,j,l the processing time of the lth reentrant job j on machine i, and Sπi,j the possible earliest starting time of job πi,j. Notice that the value of Sπi,j should meet the following inequality:(9)maxSπi,j,t1+TMπi,j,πi,j,lπi,j≤t2,where Mπi,j=Mπi,j,hπi,j,lπi,j, and [t1, t2] represents any idle time interval on the machine.Based on the above definitions, the decoding scheme that generates an active schedule for a RJSSP’s solutionπi is provided as follows:Step 1. Set kw=1 and lw=1, w=1,…,nandj=1.Step 2. If kπi,j>1 and (kπi,j mod m=1), then set lπi,j=lπi,j+1.Step 3. Set hπi,j=kπi,j−lπi,j−1×m.Step 4. Calculate Sπi,j, and set kπi,j=kπi,j+1.Step 5. Set j=j+1. If j≤n×m×L, then return to Step 2.


## 4.3. Application of Roulette Wheel Rule in OCBAT

For stochastic RJSSPs, the difference betweenδb,ik and δb,jk (i≠j) is usually much larger than that between si and sj. This can cause ∑i=1Smaxnik+1−nik,0≫Δ. Based on Step 4 of the standard OCBAT (see Section 3.2), the repeated times of Steps 1–5 of this standard algorithm may be much less than T−n0/Δ. That is, the number of times that OCBAT can be used to dynamically allocate computing budget is very limited. As a result, the reliable evaluation ability of OCBAT cannot be well utilized.Under this situation, the so-called “most starving” rule [40] is usually used to handle this obstacle. However, this rule sets Δ to 1 and needs to execute the OCBAT’s Steps 1–5 T times. This may increase the running time of the OCBAT’s algorithm. Since the OCBAT decides the budget fractions instead of the number, here we utilize the “roulette wheel” rule to allocate Δ. That is, Step 4 of the standard OCBAT should be changed to the following two substeps:Step 4.1. Calculate the allocation probability Pik+1Pik+1=nik+1/∑i=1Snik+1 for each solution i at (k+1) th allocation.Step 4.2. Apply the “roulette wheel” rule to allocate Δ to each solution i according to Pik+1, and update each nik+1.


## 4.4. Special Exploitation and Exploration Strategies

Based on References [44, 45], the solution space of the RJSSP can be regarded as a “big valley,” where the local optima are often close to each other, and close to the global optima at the bottom of the “big valley,” and either the Insert-based operator or the Interchange-based operator can execute a more compact search. Meanwhile, DEA has been proved to be an effective algorithm to find the promising solutions or regions in the whole valley [42, 44]. As for the stochastic RJSSP, the shape and the bottom regions of the big valley are always changing. Thus, to improve our DEA_UHT’s search ability, we devise an Insert-based exploitation strategy and an Interchange-based exploration strategy to replace DEA’s original mutation and crossover, which cannot obtain enough promising solutions. The former strategy selects some reliable good individuals identified by OCBAT and HTT to replace some poor individuals, and executes an Insert-based operator on these selected individuals. The latter strategy performs an Interchange-based operator guided by DEA’s basic scheme on all individuals except those replaced poor individuals. The detailed procedures of these strategies are provided in Step 5 in the next section.


## 4.5. DEA_UHT

In DEA_UHT, DEA-based search is devised according to the DE/rand-to-best/1/exp strategy to perform global search or exploration, where the base vector is the current best individual. Therefore, the information of the best individual can be shared by other individuals. By incorporating OCBAT, HTT, and two special exploitation and exploration strategies into DEA, a hybrid approach, namely, DEA_UHT, is proposed for the stochastic RJSSP.DenoteG a generation, Popt a population with size PS at generation t, W_Popt an archive set to save the individuals which need to adopt the special Insert-based crossover, Xit the ith individual with dimension N (N=n) in Popt, Tmp_Popt a temporary population with size PS in generation t, Tmp_Xit the ith individual in Tmp_Popt, xi,kt the kth variable/component of individual Xit, tmpk the kth variable of tmp, tmp01k the kth variable of tmp01, CR the crossover probability, F the scaling factor, O_dxi,kt=φi,kt the ordinal number of xi,kt in Xit in descending order (see Section 4.1), RO_dxi,kt=πi,kt the xi,kt’s corresponding job number in the job permutation πit (see Section 4.1), and random0,1 the random value in the interval [0, 1]. Based on these definitions, the framework of DEA_UHT is given as follows:Step 1. Input N, PS≥3, CR∈0,1, and let bounds be lowerxi,k=0 and upperxi,k=4, k=1,…,N.Step 2. Population initializationStep 2.1. Generate xi,k0=lowerxi,k+random0,1∗upperxi,k−lowerxi,k,k=1,…,N for i=1,…,PSStep 2.2. Use the algorithm of OCBAT in Sections3.2 and 4.3 to allocate T sampling budgets (i.e., evaluation times) for all individuals while estimating the objective values of all individuals and set W_Pop0=null set.Step 3. Set t=1 and select an individual Xbest0 from Pop0 as bestit with the minimum objective value.Step 4. Evolution phase (between Steps 4 and 9). Set i=1.Step 5.Mutation and crossover phase.Step 5.1. If Xit−1 belongs to W_Popt−1, then execute the Insert-based exploitation (see Section 4.4).Step 5.1.1. Randomly select one individual from the best five percent of Popt−1 and set it as tmp.Step 5.1.2. Randomly generate u and v (u<v), and randomly set r_i to 1 or 2.Step 5.1.3. If r_i=1, then insert tmpu after tmpv.Step 5.1.4. If r_i=2, then insert tmpv before tmpu.Step 5.1.5. Settmp_Xit=tmp and go to Step 6.Step 5.2. Perform the Interchange-based exploration (see Section 4.4). Set the trial vectortmp=Xit−1, tmp01=Xit−1 and L′=0. Randomly select r1,r2∈1,…,PS, where r1≠r2≠i, and randomly select k∈1,…,N.Step 5.2.1. Set tmpk=tmpk+F∗bestitk−tmpk+F∗xr1,kt−1−xr2,kt−1, and v1=O_dtmpk.Step 5.2.2. If RO_dtmpk<>RO_dtmp01k, then find u1 satisfying O_dtmp01u1=v1 and interchange tmp01k with tmp01u1; else randomly generate v1 (RO_dtmp01k<>RO_dtmp01v1) and interchange tmp01k with tmp01v1.Step 5.2.3. Set tmp=tmp01.Step 5.2.4. Set k=k+1 mod N and L′=L′+1.Step 5.2.5. If random0,1<CR and L′<2, then return to Step 5.2.1.Step 5.2.6. Set Tmp_Xit=tmp.Step 6. Set i = i+1. If i≤PS, then return to Step 5.Step 7. Use the algorithm of OCBAT in Sections 3.2 and 4.3 to estimate the objective values of all individuals of Tmp_popt.Step 8. Selection phase. Perform HHT in Section 3.3 on Tmp_Xit with Xit−1, i=1,…,PS.Step 8.1. If the null hypothesis holds and J¯Xit−1−J¯Tmp_Xit>τ, then set a Boolean variable b_replace = true; else set b_replace = falseStep 8.2. If b_replace = true then set Xit=Tmp_Xit; else set Xit=Xit−1.Step 8.3. If b_replace = true and J¯Tmp_Xit<J¯bestit, then set bestit=Tmp_Xit.Step 8.4. If b_replace = false and Xit−1 is in the worst 20 percent of Popt−1, then add Xit−1 to W_Popt.Step 9. Set t = t+1. If t≤t_max (the maximum generation), then return to Step 4.Step 10. Output πoutput (πoutput=bestit) and its objective value.From the above procedure, it can be known that DEA_UHT not only utilizes OCBAT to ensure reliable evaluation for good solutions but also adopts HTT to reduce repetitive search. Furthermore, the DEA-based search combined with two special strategies is devised to effectively execute exploration and exploitation in solution space. Meanwhile, “L′<2” in Step 5.2.5 is used to control the search range of the Interchange-based exploration. In addition, it is worth noting that although Step 5.1 (resp. Step 5.2) directly performs the Insert (resp. Interchange) operation on the individual, it is equivalent to performing the same Insert (resp. Interchange) operation on the corresponding permutation of this individual (see the RLOV rule in Section 4.1).


## 5. Simulation Results and Comparisons

### 5.1. Experimental Setup

To verify DEA_UHT’s performance, ten instances of the deterministic RJSSP are created via the following steps:Step 1. Select one out of ten JSSP’s classic benchmarks [46] in turn as PP(i.e., FT06, FT10, FT20, LA01, LA06, LA11, LA16, LA21, LA26, and LA31 [46]).Step 2. Set the reentrant times L=2.Step 3. Set each Mi,j,1 and each Ti,j,1 to the corresponding data in PP.Step 4. Set Mi,j,2=Mi+1,j,1 for i=1,…,n−1 and j=1,…,m.Step 5. Set Mn,j,2=M1,j,1 for j=1,…,m.Step 6. Set Ti,j,2=Ti,j+1,1 for j=1,…,n−1 and i=1,…,m.Step 7. Set Ti,n,2=Ti,1,1 for i=1,…,m.Using the above steps, ten RJSSP’s instances can be created. These instances are named FT06_R2, FT10_R2, FT20_R2, LA01_R2, LA06_R2, LA11_R2, LA16_R2, LA21_R2, LA26_R2, and LA31_R2, respectively. Each of these names is formed by adding “_R2” after the name of the corresponding JSSP’s benchmark. Obviously, these RJSSP’s instances are obtained by simply extending the classical JSSP’s instances. Since eachMi,j,1 and Ti,j,1 are randomly generated between [1, n] and [1, 100], respectively, the internal correlation within each RJSSP’s instance can be ignored. Using the above steps to obtain the RJSSP’s instances is just for the convenience of other researchers to generate the same instances.For any created instance, each job’s due date can be obtained via the following steps:Step 1. Randomly created a permutation π=π1,π2,…,πn×m×L for each RJSSP’s instance z.Step 2. Calculate each Czπj,Lπj∈π via the decoding scheme in Section 4.2.Step 3. Specify each job’s due date via(10)dzπj=Czπj,L+random−Czπj,L10,Czπj,L10,whererandom−Czπj,L/10,Czπj,L/10 is a random value between −Czπj,L/10,Czπj,L/10. Because the ability to address tight due dates affects an enterprise’s competence and the problem under tight due dates is more difficult to solve than under loose due dates, (10) is designed to obtain a tight due date.Next, the instances of the stochastic RJSSP can be obtained by changing each original processing timepπj,k,lπj of the above RJSSP’s instances to a uniform distribution U1−ξEPπj,k,lπj,1+ξEPπj,k,lπj, where EPπj,k,lπj is the expected processing time that equals to the original pπj,k,lπj and ξ denotes noise magnitude. To test the performance of the algorithm more comprehensively, two kinds of stochastic RJSSPs are considered. The first kind is the stochastic RJSSP under Tmax. Ten instances with ξ=0.3 and them with ξ=0.6 are generated. These instances are denoted by S1_Iname_R2_Tmax, where Iname indicates that S1_Iname_R2_Tmax is derived from the deterministic instance Iname. The second kind is the stochastic RJSSP under Cmax, whose ten instances with ξ=0.6 are generated. Similarly, these instances are donated by S1_Iname_R2_Cmax. Moreover, since it is a common scenario that only a part of the machines are unstable, a variant of the first kind of problem is also considered. This variant, namely, S2_Iname_R2_Tmax, only sets the processing time of each job on machine one and machine three to a uniform distribution U1−ξEPπj,k,lπj,1+ξEPπj,k,lπjk=1,3andξ=0.6The proposed DEA_UHT and the other compared algorithms were implemented in Delphi 2010 and the experiments were executed on an Intel 3.0 GHz PC with 8 GB memory. The main parameters of DEA_UHT are set as follows: the population sizePS=100, F  = 0.7, CR  = 0.1, T=1000, n0=5, and Δ=10. The maximum generation of each compared algorithm is set to 300. Each compared algorithm is executed thirty times independently on each instance.To show the effectiveness of DEA_UHT, two variants of it are compared. The abbreviations of these variants are given as follows:(i)
PDEA: DEA_UHT without OCBAT, HTT, theInsert-based exploitation strategy and the Interchange-based exploration strategy. The details can be described as follows:(1)
DEA_UHT without OCBAT. At Steps 2.2 and 7 of DEA_UHT, the algorithm of OCBAT is replaced with twenty evaluation times for each solution’s performance estimation.(2)
DEA_UHT without HTT. At Step 8 of DEA_UHT, the HTT-based selection is replaced with the normal DE’s selection.(3)
DEA_UHT without theInsert-based exploitation strategy: Step 5.1 is deleted.(4)
DEA_UHT without theInterchange-based exploitation strategy: Steps 5.2.2 and 5.2.3 are deleted, and “L′<2” in Step 5.2.5 is replaced with “L′<N.”(2)
DEA_UHT_O. DEA_UHT without HTT, the Insert-based exploitation strategy and the Interchange-based exploration strategy.


### 5.2. Simulation Results and Comparisons

The statistical results are summarized in Tables2 and 3, where ξ is the noise magnitude, BRE is the best expected maximum tardiness or makespan, and ARE is the average expected maximum tardiness or makespan. To make the statistical results clearer, in Tables 2 and 3, the best and the second-best values in each row are represented by using the bold and the italic fonts, respectively. For the final output solution πoutput obtained by each compared algorithm at each run, its expected objective value ETmaxπoutput,ξ or ECmaxπoutput,ξ is calculated with the expected processing time (i.e., the processing time without noise). Obviously, BRE and ARE can reflect the performance of these compared algorithms in a statistical sense. Moreover, to further show the statistical distributions of the results in Tables 1 and 2, the violin plots for the algorithm pairs “PDEA vs. DEA_UHT” and “DEA_UHT_O vs. DEA_UHT” are given in Figures 1 and 2.Table 2
Comparisons of PDEA, DEA_UHT_O, and DEA_UHT.
Problemn, m, LξPDEADEA_UHT_ODEA_UHTBREAREBREAREBREARES1_FT06_R2_Tmax6, 6, 20.317.0022.5316.0021.3711.0015.13S1_LA01_R2_Tmax10, 5, 20.3409.00479.07429.00469.87282.00369.27S1_LA06_R2_Tmax15, 5, 20.3848.00924.57777.00902.17614.00760.17S1_LA11_R2_Tmax20, 5, 20.31299.001374.031244.001341.901071.001179.30S1_FT10_R2_Tmax10, 10, 20.3579.00721.17537.00694.57199.00363.57S1_FT20_R2_Tmax20, 5, 20.31429.001518.731371.001489.83955.001090.87S1_LA16_R2_Tmax10, 10, 20.3558.00621.13485.00585.07221.00315.97S1_LA21_R2_Tmax15, 10, 20.3964.001128.671011.001075.13407.00538.00S1_LA26_R2_Tmax20, 10, 20.31436.001604.731449.001559.93847.00949.57S1_LA31_R2_Tmax30, 10, 20.32469.002611.972300.002546.901573.001848.00S1_FT06_R2_Tmax6, 6, 20.619.0025.8017.0022.4710.0016.37S1_LA01_R2_Tmax10, 5, 20.6464.00539.60414.00487.43307.00379.43S1_LA06_R2_Tmax15, 5, 20.6872.00947.50810.00915.33626.00780.53S1_LA11_R2_Tmax20, 5, 20.61304.001418.831289.001366.571170.001252.27S1_FT10_R2_Tmax10, 10, 20.6625.00765.93534.00698.93176.00375.43S1_FT20_R2_Tmax20, 5, 20.61477.001586.271403.001517.701043.001199.67S1_LA16_R2_Tmax10, 10, 20.6503.00675.83499.00617.30244.00370.60S1_LA21_R2_Tmax15, 10, 20.61035.001172.101002.001100.77557.00685.80S1_LA26_R2_Tmax20, 10, 20.61465.001663.931407.001559.27928.001033.50S1_LA31_R2_Tmax30, 10, 20.62560.002689.832405.002579.501761.001993.90Average1016.601124.61969.951077.60650.10775.87Table 3
Comparisons of PDEA, DEA_UHT_O, and DEA_UHT on two other kinds of stochastic RJSSP.
Problemn, m, LξPDEADEA_UHT_ODEA_UHTBREAREBREAREBREARES2_FT06_R2_Tmax6, 6, 20.619.0023.7717.0021.6010.0015.13S2_LA01_R2_Tmax10, 5, 20.6414.00485.80423.00470.63282.00371.93S2_LA06_R2_Tmax15, 5, 20.6862.00937.60811.00907.67650.00781.43S2_LA11_R2_Tmax20, 5, 20.61319.001387.101299.001339.531136.001243.43S2_FT10_R2_Tmax10, 10, 20.6525.00718.60512.00681.37210.00316.20S2_FT20_R2_Tmax20, 5, 20.61381.001528.301441.001512.571022.001192.00S2_LA16_R2_Tmax10, 10, 20.6521.00629.07475.00596.47262.00362.90S2_LA21_R2_Tmax15, 10, 20.6989.001133.57963.001101.43411.00569.77S2_LA26_R2_Tmax20, 10, 20.61421.001589.571418.001532.90855.00981.10S2_LA31_R2_Tmax30, 10, 20.62371.002588.872288.002542.001758.001910.33S1_FT06_R2_Cmax6, 6, 20.6108.00115.87107.00112.50102.00108.70S1_LA01_R2_Cmax10, 5, 20.61407.001499.431406.001452.531332.001375.33S1_LA06_R2_Cmax15, 5, 20.61913.002031.701908.001959.971852.001877.40S1_LA11_R2_Cmax20, 5, 20.62555.002652.232525.002610.672444.002476.73S1_FT10_R2_Cmax10, 10, 20.62186.002355.872196.002299.101961.002045.67S1_FT20_R2_Cmax20, 5, 20.62678.002829.072692.002782.902490.002572.93S1_LA16_R2_Cmax10, 10, 20.62136.002271.332142.002241.231864.002004.90S1_LA21_R2_Cmax15, 10, 20.62871.002963.772769.002863.102284.002485.43S1_LA26_R2_Cmax20, 10, 20.63440.003592.533380.003485.202843.002982.27S1_LA31_R2_Cmax30, 10, 20.64408.004694.074465.004585.603871.004071.83Average1676.201801.411661.851754.951381.951487.27Figure 1
Violin plots for comparison results in Table1. (a) PDEA vs DEA_UHT. (b) DEA_UHT_O vs DEA_UHT.
(a)(b)Figure 2
Violin plots for comparison results in Table2. (a) PDEA vs DEA_UHT. (b) DEA_UHT_O vs DEA_UHT.
(a)(b)From Tables2 and 3, it is clear that both the BRE values and the ARE values obtained by DEA_UHT are better than those obtained by PDEA, which validates the effectiveness via incorporating OCBAT, HTT, the Insert-based exploitation strategy, and the Interchange-based exploration strategy into PDEA. This also means that DEA_UHT can achieve a better balance between exploration and exploitation than PDEA and DEA_UHT_O. Meanwhile, most of the BRE values and all of the ARE values obtained by DEA_UHT_O are better than those obtained by PDEA, from which it can be concluded that OCBAT is necessary to improve the optimization performance. It is worth noting that the above conclusions can still be drawn when considering the instances in Tables 1 and 2, where ξ=0.1or0.3. In addition, from Figures 1 and 2, it can be seen that DEA_UHT has better statistical distributions and better median lines compared with PDEA and DEA_UHT_O. These violin plots confirm the competitiveness of DEA_UHT.To show the role of OCBAT, the computing budget allocation of OCBAT inDEA_UHT for the middle-size instance S1_LA11_R2_ is provided in Figure 3. In addition, to illustrate the effectiveness of DEA_UHT, the convergence curves of the compared algorithms on the same instance are given in Figure 4, where the curves are formed by connecting the ETmaxπ,ξ’s value of the best individual bestit at each generation of the corresponding algorithm. ETmaxπ,ξ here is calculated by setting ξ=0 (i.e., ETmaxbestit,ξ=Tmaxbestit). The computing budget allocation and the convergence curves for other instances are similar as those in Figures 3 and 4.Figure 3
Computing budget allocation of OCBAT in DEA_UHT for S1_LA11_R2_Tmax (generation t = 20).Figure 4
Convergence curves of the compared algorithms on S1_LA11_R2_Tmax (noise magnitude = 0.6).From Figure3, it is shown that OCBAT can intelligently assign more evaluation times to better individuals. That is to say, OCBAT can enhance the algorithm’s ability to find more reliable high-quality solutions or regions at each generation under the same computing budget. From Figure 4, it can be seen that the convergence speed of DEA_UHT is obviously faster than those of the other compared algorithms. This manifests that DEA_UHT can guide the whole population to move to the bottom of the expected “big valley” (i.e., the bottom of the “big valley” without noise) in solution space faster, and thus has better search performance. Moreover, the ETmaxπ,ξ’s values of DEA_UHT_O are less than those of PEDA in most cases, which verifies that OCBAT helps to guide the search to really promising regions in noisy environment.


## 5.1. Experimental Setup

To verify DEA_UHT’s performance, ten instances of the deterministic RJSSP are created via the following steps:Step 1. Select one out of ten JSSP’s classic benchmarks [46] in turn as PP(i.e., FT06, FT10, FT20, LA01, LA06, LA11, LA16, LA21, LA26, and LA31 [46]).Step 2. Set the reentrant times L=2.Step 3. Set each Mi,j,1 and each Ti,j,1 to the corresponding data in PP.Step 4. Set Mi,j,2=Mi+1,j,1 for i=1,…,n−1 and j=1,…,m.Step 5. Set Mn,j,2=M1,j,1 for j=1,…,m.Step 6. Set Ti,j,2=Ti,j+1,1 for j=1,…,n−1 and i=1,…,m.Step 7. Set Ti,n,2=Ti,1,1 for i=1,…,m.Using the above steps, ten RJSSP’s instances can be created. These instances are named FT06_R2, FT10_R2, FT20_R2, LA01_R2, LA06_R2, LA11_R2, LA16_R2, LA21_R2, LA26_R2, and LA31_R2, respectively. Each of these names is formed by adding “_R2” after the name of the corresponding JSSP’s benchmark. Obviously, these RJSSP’s instances are obtained by simply extending the classical JSSP’s instances. Since eachMi,j,1 and Ti,j,1 are randomly generated between [1, n] and [1, 100], respectively, the internal correlation within each RJSSP’s instance can be ignored. Using the above steps to obtain the RJSSP’s instances is just for the convenience of other researchers to generate the same instances.For any created instance, each job’s due date can be obtained via the following steps:Step 1. Randomly created a permutation π=π1,π2,…,πn×m×L for each RJSSP’s instance z.Step 2. Calculate each Czπj,Lπj∈π via the decoding scheme in Section 4.2.Step 3. Specify each job’s due date via(10)dzπj=Czπj,L+random−Czπj,L10,Czπj,L10,whererandom−Czπj,L/10,Czπj,L/10 is a random value between −Czπj,L/10,Czπj,L/10. Because the ability to address tight due dates affects an enterprise’s competence and the problem under tight due dates is more difficult to solve than under loose due dates, (10) is designed to obtain a tight due date.Next, the instances of the stochastic RJSSP can be obtained by changing each original processing timepπj,k,lπj of the above RJSSP’s instances to a uniform distribution U1−ξEPπj,k,lπj,1+ξEPπj,k,lπj, where EPπj,k,lπj is the expected processing time that equals to the original pπj,k,lπj and ξ denotes noise magnitude. To test the performance of the algorithm more comprehensively, two kinds of stochastic RJSSPs are considered. The first kind is the stochastic RJSSP under Tmax. Ten instances with ξ=0.3 and them with ξ=0.6 are generated. These instances are denoted by S1_Iname_R2_Tmax, where Iname indicates that S1_Iname_R2_Tmax is derived from the deterministic instance Iname. The second kind is the stochastic RJSSP under Cmax, whose ten instances with ξ=0.6 are generated. Similarly, these instances are donated by S1_Iname_R2_Cmax. Moreover, since it is a common scenario that only a part of the machines are unstable, a variant of the first kind of problem is also considered. This variant, namely, S2_Iname_R2_Tmax, only sets the processing time of each job on machine one and machine three to a uniform distribution U1−ξEPπj,k,lπj,1+ξEPπj,k,lπjk=1,3andξ=0.6The proposed DEA_UHT and the other compared algorithms were implemented in Delphi 2010 and the experiments were executed on an Intel 3.0 GHz PC with 8 GB memory. The main parameters of DEA_UHT are set as follows: the population sizePS=100, F  = 0.7, CR  = 0.1, T=1000, n0=5, and Δ=10. The maximum generation of each compared algorithm is set to 300. Each compared algorithm is executed thirty times independently on each instance.To show the effectiveness of DEA_UHT, two variants of it are compared. The abbreviations of these variants are given as follows:(i)
PDEA: DEA_UHT without OCBAT, HTT, theInsert-based exploitation strategy and the Interchange-based exploration strategy. The details can be described as follows:(1)
DEA_UHT without OCBAT. At Steps 2.2 and 7 of DEA_UHT, the algorithm of OCBAT is replaced with twenty evaluation times for each solution’s performance estimation.(2)
DEA_UHT without HTT. At Step 8 of DEA_UHT, the HTT-based selection is replaced with the normal DE’s selection.(3)
DEA_UHT without theInsert-based exploitation strategy: Step 5.1 is deleted.(4)
DEA_UHT without theInterchange-based exploitation strategy: Steps 5.2.2 and 5.2.3 are deleted, and “L′<2” in Step 5.2.5 is replaced with “L′<N.”(2)
DEA_UHT_O. DEA_UHT without HTT, the Insert-based exploitation strategy and the Interchange-based exploration strategy.


## 5.2. Simulation Results and Comparisons

The statistical results are summarized in Tables2 and 3, where ξ is the noise magnitude, BRE is the best expected maximum tardiness or makespan, and ARE is the average expected maximum tardiness or makespan. To make the statistical results clearer, in Tables 2 and 3, the best and the second-best values in each row are represented by using the bold and the italic fonts, respectively. For the final output solution πoutput obtained by each compared algorithm at each run, its expected objective value ETmaxπoutput,ξ or ECmaxπoutput,ξ is calculated with the expected processing time (i.e., the processing time without noise). Obviously, BRE and ARE can reflect the performance of these compared algorithms in a statistical sense. Moreover, to further show the statistical distributions of the results in Tables 1 and 2, the violin plots for the algorithm pairs “PDEA vs. DEA_UHT” and “DEA_UHT_O vs. DEA_UHT” are given in Figures 1 and 2.Table 2
Comparisons of PDEA, DEA_UHT_O, and DEA_UHT.
Problemn, m, LξPDEADEA_UHT_ODEA_UHTBREAREBREAREBREARES1_FT06_R2_Tmax6, 6, 20.317.0022.5316.0021.3711.0015.13S1_LA01_R2_Tmax10, 5, 20.3409.00479.07429.00469.87282.00369.27S1_LA06_R2_Tmax15, 5, 20.3848.00924.57777.00902.17614.00760.17S1_LA11_R2_Tmax20, 5, 20.31299.001374.031244.001341.901071.001179.30S1_FT10_R2_Tmax10, 10, 20.3579.00721.17537.00694.57199.00363.57S1_FT20_R2_Tmax20, 5, 20.31429.001518.731371.001489.83955.001090.87S1_LA16_R2_Tmax10, 10, 20.3558.00621.13485.00585.07221.00315.97S1_LA21_R2_Tmax15, 10, 20.3964.001128.671011.001075.13407.00538.00S1_LA26_R2_Tmax20, 10, 20.31436.001604.731449.001559.93847.00949.57S1_LA31_R2_Tmax30, 10, 20.32469.002611.972300.002546.901573.001848.00S1_FT06_R2_Tmax6, 6, 20.619.0025.8017.0022.4710.0016.37S1_LA01_R2_Tmax10, 5, 20.6464.00539.60414.00487.43307.00379.43S1_LA06_R2_Tmax15, 5, 20.6872.00947.50810.00915.33626.00780.53S1_LA11_R2_Tmax20, 5, 20.61304.001418.831289.001366.571170.001252.27S1_FT10_R2_Tmax10, 10, 20.6625.00765.93534.00698.93176.00375.43S1_FT20_R2_Tmax20, 5, 20.61477.001586.271403.001517.701043.001199.67S1_LA16_R2_Tmax10, 10, 20.6503.00675.83499.00617.30244.00370.60S1_LA21_R2_Tmax15, 10, 20.61035.001172.101002.001100.77557.00685.80S1_LA26_R2_Tmax20, 10, 20.61465.001663.931407.001559.27928.001033.50S1_LA31_R2_Tmax30, 10, 20.62560.002689.832405.002579.501761.001993.90Average1016.601124.61969.951077.60650.10775.87Table 3
Comparisons of PDEA, DEA_UHT_O, and DEA_UHT on two other kinds of stochastic RJSSP.
Problemn, m, LξPDEADEA_UHT_ODEA_UHTBREAREBREAREBREARES2_FT06_R2_Tmax6, 6, 20.619.0023.7717.0021.6010.0015.13S2_LA01_R2_Tmax10, 5, 20.6414.00485.80423.00470.63282.00371.93S2_LA06_R2_Tmax15, 5, 20.6862.00937.60811.00907.67650.00781.43S2_LA11_R2_Tmax20, 5, 20.61319.001387.101299.001339.531136.001243.43S2_FT10_R2_Tmax10, 10, 20.6525.00718.60512.00681.37210.00316.20S2_FT20_R2_Tmax20, 5, 20.61381.001528.301441.001512.571022.001192.00S2_LA16_R2_Tmax10, 10, 20.6521.00629.07475.00596.47262.00362.90S2_LA21_R2_Tmax15, 10, 20.6989.001133.57963.001101.43411.00569.77S2_LA26_R2_Tmax20, 10, 20.61421.001589.571418.001532.90855.00981.10S2_LA31_R2_Tmax30, 10, 20.62371.002588.872288.002542.001758.001910.33S1_FT06_R2_Cmax6, 6, 20.6108.00115.87107.00112.50102.00108.70S1_LA01_R2_Cmax10, 5, 20.61407.001499.431406.001452.531332.001375.33S1_LA06_R2_Cmax15, 5, 20.61913.002031.701908.001959.971852.001877.40S1_LA11_R2_Cmax20, 5, 20.62555.002652.232525.002610.672444.002476.73S1_FT10_R2_Cmax10, 10, 20.62186.002355.872196.002299.101961.002045.67S1_FT20_R2_Cmax20, 5, 20.62678.002829.072692.002782.902490.002572.93S1_LA16_R2_Cmax10, 10, 20.62136.002271.332142.002241.231864.002004.90S1_LA21_R2_Cmax15, 10, 20.62871.002963.772769.002863.102284.002485.43S1_LA26_R2_Cmax20, 10, 20.63440.003592.533380.003485.202843.002982.27S1_LA31_R2_Cmax30, 10, 20.64408.004694.074465.004585.603871.004071.83Average1676.201801.411661.851754.951381.951487.27Figure 1
Violin plots for comparison results in Table1. (a) PDEA vs DEA_UHT. (b) DEA_UHT_O vs DEA_UHT.
(a)(b)Figure 2
Violin plots for comparison results in Table2. (a) PDEA vs DEA_UHT. (b) DEA_UHT_O vs DEA_UHT.
(a)(b)From Tables2 and 3, it is clear that both the BRE values and the ARE values obtained by DEA_UHT are better than those obtained by PDEA, which validates the effectiveness via incorporating OCBAT, HTT, the Insert-based exploitation strategy, and the Interchange-based exploration strategy into PDEA. This also means that DEA_UHT can achieve a better balance between exploration and exploitation than PDEA and DEA_UHT_O. Meanwhile, most of the BRE values and all of the ARE values obtained by DEA_UHT_O are better than those obtained by PDEA, from which it can be concluded that OCBAT is necessary to improve the optimization performance. It is worth noting that the above conclusions can still be drawn when considering the instances in Tables 1 and 2, where ξ=0.1or0.3. In addition, from Figures 1 and 2, it can be seen that DEA_UHT has better statistical distributions and better median lines compared with PDEA and DEA_UHT_O. These violin plots confirm the competitiveness of DEA_UHT.To show the role of OCBAT, the computing budget allocation of OCBAT inDEA_UHT for the middle-size instance S1_LA11_R2_ is provided in Figure 3. In addition, to illustrate the effectiveness of DEA_UHT, the convergence curves of the compared algorithms on the same instance are given in Figure 4, where the curves are formed by connecting the ETmaxπ,ξ’s value of the best individual bestit at each generation of the corresponding algorithm. ETmaxπ,ξ here is calculated by setting ξ=0 (i.e., ETmaxbestit,ξ=Tmaxbestit). The computing budget allocation and the convergence curves for other instances are similar as those in Figures 3 and 4.Figure 3
Computing budget allocation of OCBAT in DEA_UHT for S1_LA11_R2_Tmax (generation t = 20).Figure 4
Convergence curves of the compared algorithms on S1_LA11_R2_Tmax (noise magnitude = 0.6).From Figure3, it is shown that OCBAT can intelligently assign more evaluation times to better individuals. That is to say, OCBAT can enhance the algorithm’s ability to find more reliable high-quality solutions or regions at each generation under the same computing budget. From Figure 4, it can be seen that the convergence speed of DEA_UHT is obviously faster than those of the other compared algorithms. This manifests that DEA_UHT can guide the whole population to move to the bottom of the expected “big valley” (i.e., the bottom of the “big valley” without noise) in solution space faster, and thus has better search performance. Moreover, the ETmaxπ,ξ’s values of DEA_UHT_O are less than those of PEDA in most cases, which verifies that OCBAT helps to guide the search to really promising regions in noisy environment.


## 6. Conclusion and Future Research

This paper proposed a novel DEA_UHT by combining DEA with OCBAT and HTT to address the stochastic RJSSP. This kind of problem has many real-world applications in modern enterprises. To the best of the authors’ knowledge, this is the first time that DEA has been applied to such an important problem. With the help of OCBAT to intelligently allocate limited sampling budgets to perform reliable identification on excellent or good individuals, and with the help of HTT to reserve good individuals with high confidence, as well as with theInsert-based and Interchange-based strategies to effectively execute enhanced exploitation and exploration, DEA_UHT is of good performance for different kinds of stochastic RJSSP. In the future, our work is to extend DEA_UHT to other kinds of stochastic scheduling problems.



---

*Source: 9924163-2022-01-31.xml*