# A Two-Stage Three-Machine Flow Shop Assembly Problem Mixed with a Controllable Number and Sum-of-Processing Times-Based Learning Effect by Simulated Annealing Algorithms

Authors: Shang-Chia Liu
Journal: Discrete Dynamics in Nature and Society
 (2020)

---

## Abstract

The two-stage assembly scheduling problem is widely used in industrial and service industries. This study focuses on the two-stage three-machine flow shop assembly problem mixed with a controllable number and sum-of-processing times-based learning effect, in which the job processing time is considered to be a function of the control of the truncation parameters and learning based on the sum of the processing time. However, the truncation function is very limited in the two-stage flow shop assembly scheduling settings. Thus, this study explores a two-stage three-machine flow shop assembly problem with truncated learning to minimize the makespan criterion. To solve the proposed model, we derive several dominance rules, lemmas, and lower bounds applied in the branch-and-bound method. On the other hand, three simulated annealing algorithms are proposed for finding approximate solutions. In both the small and large size number of job situations, the SA algorithm is better than the JS algorithm in this study. All the experimental results of the proposed algorithm are presented on small and large job sizes, respectively.


---

## Body

## 1. Introduction

For decades, scheduling models usually assumed that the processing time of the job is known and fixed [1]. But, in a real production system, both the efficiency of the machine and the skill of the worker can increase with the working time, thereby reducing the actual work processing time with the development of production. Many researchers indicated certain types of learning effects, such as [2] in the position-based learning effect and [3] in the time-dependent learning effect. This topic continues to attract a lot of research interest [4–6].On the other hand, Biskup, Kuo and Yang [2, 3], and Kuolamas and Kyparisis [7] introduced models that involve a learning effect on two-machine scheduling or flow shop scheduling settings following the same or different learning ideas. There are a multitude of studies related to two-machine scheduling or flow shop scheduling settings with the learning effect consideration, including [8–11] and [12]. Besides, there are some two-stage models also with the learning effect consideration. Wu et al. [13] adopted the learning model developed by Biskup [2] to solve a two-stage flow shop scheduling problem with three machines to minimize the makespan. They devised three simulated annealing (SA) algorithms and three cloud theory-based SA algorithms. Adopting the learning model in [3, 14], a branch-and-bound (B&B) algorithm is devised incorporating six (hybrid) particle swam optimization (PSO) methods to solve the two-stage flow shop assembly scheduling problem to minimize the total job completion time.Most studies using the learning model are applied in the single-machine or flow shop setting. However, the two-stage assembly scheduling problem is relatively unexplored. Recently, Wu et al. and Zou et al. [15, 16] considered position-based learning in connection with a two-stage assembly scheduling problem. They proposed different versions of simulated annealing and cloud theory-based simulated annealing to solve this problem. Moreover, Wu et al. [17] considered this problem with general learning effects. They developed and evaluated the performances of six hybrid particle swarm optimizations (PSO). Wu et al. [18] have conducted the research about a combined approach for two-agent scheduling with a sum-of-processing-times-based learning effect. To the best of our knowledge, no other research considers the two-stage assembly scheduling problem with learning effects. Table 1 presents a comparative study of existing models to solve the considered scheduling problem. Many studies claim that most of the productive items in manufacturing systems may be formulated in a two-stage assembly scheduling model. However, the literature neglects accumulated learning experience in solving a two-stage assembly scheduling problem. In fact, the sum-of-processing times-based learning model is pertinent to process manufacturing in which an initial setup is often followed by a lengthy uninterrupted production process. Motivated by this observation, this study introduces the 2-stage 3-machine assembly problem with a sum-of-processing times of already processed jobs learning to minimize the makespan criterion. This model assumes that there are two machines in the first stage and an assembly machine in the second stage. This study first provides some dominances and a lower bound applied in the branch-and-bound method for an optimal solution. Three heuristics modified from Johnson’s rule with and without improving by an interchange pairwise method are, then, separately applied in three simulated annealing algorithms for finding near-optimal solutions. Finally, the statistical results of the three proposed algorithms are evaluated and reported.Table 1
Small size number of jobs parameters.
Parametern = 10, m = 3Ti10−3Tf10−8cf0.95Nr10β0.2α1−0.1α2−0.1α3−0.2


## 2. Problem Statement

The considered two-stage assembly scheduling problem is formally described in this section. We assume a series ofn given jobs to be processed on three machines. The main idea of the studied problem is executing n given jobs on three machines in two stages. Each job has strictly more than two operations. For the operations of the n job, the first stage is performed in a parallel way in two machines. The operation processing of the second stage only begins when the operations of the first stage are completed. All jobs are available at time zero. Each job j is decomposed on three tasks as follows: the ordinary processing times (without learning effect) of job j are aj, bj, and cj on machines M1, M2, and M3, respectively. Other assumptions are no machine can process more than one job at a time; no idle time is allowed on machines M1 and M2; and once a job has begun processing, it cannot be interrupted.Following the works of Kuo and Yang [3] and Liu et al. [19], the real processing times of Jj, if Jj scheduling on the position r of a job sequence S, are considered as ajmaxα,1+∑k=1r−1aka1, bjmaxα,1+∑k=1r−1bka2, and cjmaxα,1+∑k=1r−1cka3 on machines M1, M2, and M3, respectively, where α denotes the controllable parameter with α<0, and a1,a2,a3 denote the learning indices for M1, M2, and M3. For a schedule S, the finishing time of a job, say Jj, to be scheduled on the rth position (in S) on machine M3 is defined, and denoted, as C3rS:(1)C3rS=maxt1+ajmaxα,1+∑k=1r−1aka1,t2+bjmaxα,1+∑k=1r−1bka2,t3+cjmaxα,1+∑k=1r−1cka3,where t1, t2, and t3 are denoted as the beginning times of Jj on machines M1, M2, and M3 in S, respectively. The optimal criterion of this study is to find a scheduled S to minimize the makespan (or C3nS).


## 3. Lower Bounds and Some Lemmas

This section proposes some useful lower bounds used in a branch-and-bound method. Before deriving the lower bounds, we define some notations. Supposet1, t2, and t3 denote the starting time of the first job in sUS on all three machines. Then, we assume that sPS are the partially scheduled k jobs and sUS are the remaining unscheduled n−k jobs. a1≤a2≤⋯≤an−k, b1≤b2≤⋯≤bn−k, and c1≤c2≤⋯≤cn−k denote increasing sequences of a1,a2,…,an−k; b1,b2,…,bn−k; and c1,c2,…,cn−k in σUS, respectively. Notably, ai,bi,ci are not necessarily from the same job, and sspt1, sspt2, and sspt3 are three subsequences of n jobs n increasing sequences of a1,a2,…,an−k; b1,b2,…,bn−k; and c1,c2,…,cn−k in sUS, respectively.Additionally, by using the ideas of Kuo and Yang [3] and Liu et al. [19], a lower bound for a subsequent can be yielded as follows:(2)Ck+1s=maxt1+ak+1maxα,1+∑i=1kaia1,t2+bk+1maxα,1+∑i=1kbia2,t3+ck+1maxα,1+∑i=1kcia3≥t1+ak+1α+1+∑i=1kaia12+ck+1α+1+∑i=1kcia32Ck+2s≥t1+ak+1α+1+∑i=1kaia12+ak+2α+1+∑i=1kaia12+ck+2α+1+∑i=1kcia32⋮Ck+n1s≥t1+∑j=1n1ak+iα+1+∑i=1k+j−1aia12+ck+n1α+1+∑i=1k+n1−1cia32lowerbd1=t1+∑j=1n1an−j+1α+1+∑i=1k+j−1aia12+c1α+1+∑i=1n−1cia32.In a similar way,(3)lowerbd2=t2+∑j=1n1bn−j+1α+1+∑i=1k+j−1bia22+c1α+1+∑i=1n−1cia32,lowerbd3=t3+∑j=1n1cn−j+1α+1+∑i=1k+j−1cia32,lowerbd=maxlowerbd1,lowerbd,lowerbd3.In what follows, we will propose four properties used in a branch-and-bound to improve its search power. Before deriving our properties, we first give four useful lemmas which will be used in the proof of Property1.Lemma 1.
Ify≥x>0, T>0, and e<0, then yT+xe≥xT+ye.Lemma 2.
Ifλ≥1, 0≤t, and e<0, then λ1−1+te≥1−1+λte.Lemmas1 and 2 have been proved by Kuo and Yang and Liu et al. [3, 19], respectively.Lemma 3.
Ify≥x>0, T>0, e<0, and 0<α<1, then y⋅maxα,T+xe≥x⋅maxα,T+ye.Proof.
Note thatT+xe≥T+ye.Case 1.
Asα>T+xe,(4)y⋅maxα,T+xe=y⋅α,x⋅maxα,T+ye=x⋅α.
So, the inequality holds.Case 2.
AsT+xe≥α>T+ye,(5)y⋅maxα,T+xe=y⋅T+xe,x⋅maxα,T+ye=x⋅α.
The inequality holds.Case 3.
AsT+ye≥α,(6)y⋅maxα,T+xe=y⋅T+xe,x⋅maxα,T+ye=x⋅T+ye.
From Lemma1, the inequality holds.Lemma 4.
Ifλ≥1, t≥0, e<0, and 0<β<1, then λmaxβ,1−maxβ,1+te≥maxβ,1−maxβ,1+λte.Proof.
Note that1+λt≥1+t>0; thus, 1+λte≤1+te≤1 because e<0.Case 1.
Asβ≤1+λte≤1,(7)λmaxβ,1−maxβ,1+te=λ1−1+te,maxβ,1−maxβ,1+λte=1−1+λte.
From Lemma2, the inequality holds.Case 2.
As1+λte<β<1+te≤1,(8)λmaxβ,1−maxβ,1+te=λ1−1+te,maxβ,1−maxβ,1+λte=1−β,which is less than 1−1+λte. From Lemma 2, the equality holds.Case 3.
As1+te≤β<1,(9)λmaxβ,1−maxβ,1+te=λ1−β,maxβ,1−maxβ,1+λte=1−β.
The equality holds becauseλ≥1.Case 4.
Asβ≥1,(10)λmaxβ,1−maxβ,1+te=λβ−β=0,maxβ,1−maxβ,1+λte=β−β=0.
In summary, the inequality always holds for the given conditions.
To showmaxβ,1−maxβ,1+λte=β−β=0 is no less than S2, it suffices to show C3jS1≤C3iS2.Property 1.
Ifai<aj,bi<bj,ci>cj,t3>maxt1+ajmaxα,1+∑i=1k−1aie1,t2+bjmaxα,1+∑i=1k−1bie2, and t1+aimaxα,1+∑i=1k−1aie1+ajmaxα,1+∑i=1k−1ai+aie1>maxt2+bimaxα,1+∑i=1k−1bie2+bjmaxα,1+∑i=1k−1bi+bie2,t3+cimaxα,1+∑i=1k−1cie3, then S1 is no less than S2.Proof.
For a job sequenceS, if the job Jj is assigned to the rth position of S, then according to the definition of the completion time of a job,(11)C3rS=maxt1+ajmaxα,1+∑i=1r−1aie1,t2+bjmaxα,1+∑i=1r−1bie2,t3+cjmaxα,1+∑i=1r−1cie3.
To simplify the proof, letTA=1+∑i=1k−1aie1, TB=1+∑i=1k−1bie2, and TC=1+∑i=1k−1cie3. Then,(12)C3jS1=maxt1+aimaxα,TAe1+ajmaxα,TA+aie1,t2+bimaxα,TBe2+bjmaxα,TB+bie2,maxt3,t1+aimaxα,TAe1,bimaxα,TBe2+cimaxα,TCe3+cjmaxα,TC+cie3,C3iS2=maxt1+ajmaxα,TAe1+aimaxα,TA+aje1,t2+bjmaxα,TBe2+bimaxα,TB+bje2,maxt3,t1+ajmaxα,TAe1,bjmaxα,TBe2+cjmaxα,TCe3+cimaxα,TC+cje3.
Using the given conditionsai<aj,bi<bj, and t3>maxt1+ajmaxα,TAe1,t2+bjmaxα,TBe2, one has(13)C3jS1=maxt1+aimaxα,TAe1+ajmaxα,TA+aie1,t2+bimaxα,TBe2+bjmaxα,TB+bie2,t3+cimaxα,TCe3+cjmaxα,TC+cie3,C3iS2=maxt1+ajmaxα,TAe1+aimaxα,TA+aje1,t2+bjmaxα,TBe2+bimaxα,TB+bje2,t3+cjmaxα,TCe3+cimaxα,TC+cje3.
Applying the given condition,(14)t1+aimaxα,TAe1+ajmaxα,TA+aie1>maxt2+bimaxα,TBe2+bjmaxα,TB+bie2,t3+cimaxα,TCe3,and then,(15)C3jS1=t1+aimaxα,TAe1+ajmaxα,TA+aie1+cimaxα,TC+cje3,(16)C3iS2=t1+ajmaxα,TAe1+aimaxα,TA+aje1+cimaxα,TC+cje3.
Equation (16) holds by showing t1+ajmaxα,TAe1+aimaxα,TA+aje1>t1+aimaxα,TAe1+ajmaxα,TA+aie1.(17)ajmaxα,TAe1+aimaxα,TA+aje1−aimaxα,TAe1−ajmaxα,TA+aie1=ajmaxα,TAe1−maxα,TA+aie1−aimaxα,TAe1−maxα,TA+aie1,=aiTAe1⋅ajaimaxαTAe1,1−maxαTAe1,1+aiTAe1e1−maxαTAe1,1−maxαTAe1,1+ajaiaiTAe1e1,=aiTAe1⋅λmaxβ,1−maxβ,1+te1−maxβ,1−maxβ,1+λte1,where λ=aj/ai>1, β=α/TAe1>0, and t=ai/TAe1>0. Applying Lemma 4, t1+ajmaxα,TAe1+aimaxα,TA+aje1>t1+aimaxα,TAe1+ajmaxα,TA+aie1 follows and, thus, completes the claim.
Finally, one needs to show thatC3iS2−C3jS1≥0 to fulfill the proof. From equations (15) and (16), one obtains, applying ai<aj,ci>cj and the fact TA+aje1<TA+aie1 and TC+cje3>TC+cie3, that all three terms of C3iS2−C3jS1 are greater than or equal to 0, i.e., C3iS2−C3jS1≥0.
The details of the proofs of Property2–4 are omitted because they can be obtained in a similar way to Property 1.Property 2.
Ifai<aj,bi<bj,ci>cj,
t3>maxt1+ajmaxα,1+∑i=1k−1aia1,t2+bjmaxα,1+∑i=1k−1bia2, and t2+bimaxα,1+∑i=1k−1bia2+bjmaxα,1+∑i=1k−1bi+bia2>maxt1+aimaxα,1+∑i=1k−1aia1+ajmaxα,1+∑i=1k−1ai+aia1,t3+cimaxα,1+∑i=1k−1cia3, then S1 is no less than S2.Property 3.
Ifai<aj,bi<bj,ci>cj,
t1+aimaxα,1+∑i=1k−1aia1>maxt3,t2+bjmaxα,1+∑i=1k−1bia2, and ajmaxα,1+∑i=1k−1aia1+cjmaxα,1+∑i=1k−1cia3>aimaxα,1+∑i=1k−1aia1+cimaxα,1+∑i=1k−1cia3, then S1 is no less than S2.Property 4.
Ifai<aj,bi<bj,ci>cj,
t2+bimaxα,1+∑i=1k−1bia2>maxt3,t1+ajmaxα,1+∑i=1k−1aia1, and bjmaxα,1+∑i=1k−1bia2+cjmaxα,1+∑i=1k−1cia3>bimaxα,1+∑i=1k−1bia2+cimaxα,1+∑i=1k−1cia3, then S1 is no less than S2.


## 4. Heuristics and Metaheuristics

This section validates the performance levels of nine algorithms, namely, JS_max, JS_min, JS_mean, JS_maxpi, JS_minpi, JS_meanpi, SA_max, SA_min, and SA_mean. Note that all algorithms were developed in FORTRAN and executed on a computer with a 3.00-GHz Intel® Core™i9-10980XE CPU and 16-GB RAM. Our experiments are divided into two parts. The first part is dedicated to the small size instances, and the second is devoted to the large size instances. For the two cases, we randomly generated the normal processing times from uniform distribution U (1, 100) on M1, M2, and M3 by fixing an individual seed for each case. The factorβ would be set at 0.2, 0.4, and 0.6. The learning effect would be set at −0.1, −0.1, and −0.2, and the computational results for each small and large size instances are shown. This section describes the considered two-stage assembly scheduling problem.


### 4.1. Small Size Number of Jobs

The parameters of the small size number of jobs are selected as the number of work pieces (n) at 10, number of machines (m) of 3, and the final temperature (Tf) is fixed to 10−8, β is 0.2, α1 is −0.1, α2 is −0.1, and α3 is −0.2. The selections of other parameters are shown in Table 1.As a result of parameter selection, the starting temperatureTi is 10−3, cooling coefficient is 0.95, and the number of tests Nr of Johnson’s algorithm is 10.Next, the parameter selection process is explained in detail.We select the parameter starting temperatureTi. The range is from 10−4 to 104 at 10 times the interval, and the cooling coefficient cf is fixed at 0.95. The number of tests of Johnson’s algorithm Nr is 5, and there are also generated data and parameters defined before selecting parameters.By observing Figure1, it is obvious that only the initial temperature Ti is changed. In this range, it can be observed that the AEP is relatively low at 10−3, so the initial temperature Ti is 10−3.Figure 1
Parameter selection starting temperatureTi change.After fixing the starting temperatureTi to 10−3, we select the parameter cooling coefficient cf, ranging from 0.05 to 0.95 with 0.05 intervals, and fix the number of tests Nr of the Johnson’s algorithm as 5. There are also generated data and parameters defined before selecting the parameters.By selecting the parameter of the cooling coefficientcf, the overall decline in its value is obvious. It becomes flat after reaching 0.80, so we choose a lower value in this part. The cooling coefficient cf is fixed at 0.95. After fixing the starting temperature Ti to 10−3 and the cooling coefficient (Cf) to 0.95 (please see Figure 2), we select the parameter Johnson’s algorithm test times Nr with a range of 1 to 20 and the interval of 1 and see the difference. The generated data and parameters are fixed and defined before selecting the parameters.Figure 2
Parameter selection cooling coefficientcf change.When selecting the parameter Johnson’s algorithm test timesNr, we can see from Figure 3 that although it fluctuates up and down, its AEP value is actually very low, so we choose a lower value in this part. Johnson’s algorithm test times Nr is 10. It shows when the number of work pieces of the B&B algorithm is 12. The results of finding the best solution in a few cases cannot be found, so only a few values (in the Fs column) are recorded. From the viewpoint of the number of nodes and CPU time, the difference in the number of jobs can also be clearly seen.Figure 3
Parameter selection of Johnson’s algorithm test timesNr change.Table2 uses the β values of 0.2, 0.4, and 0.6 to distinguish the table. It can be seen regardless of whether the number of work pieces is 8, 10, or 12, the smaller the β value, the greater the number of nodes. Also, there is no best solution for the CPU time.Table 2
Differentβ for the mean of nodes and CPU time.
ParameterNodeCPU timeNβMeanMean80.298710.110.444740.050.628250.03100.275149110.330.42624453.890.61967233.13120.251984213978.760.427751022585.760.616943700327.17Table3 is a table distinguished by three different situations of α1,α2,α3. It can be observed that regardless of whether the number of work pieces is 8, 10, or 12, the number of nodes and CPU time for finding the best solution for the second case are all more than the third case, and the third case is more than the first case.Table 3
Differentβ for the mean of nodes and CPU time.
nParameterNodeCPU timeα1α2α3MeanMean8−0.1−0.1−0.144480.06−0.1−0.1−0.278600.08−0.2−0.2−0.148610.0510−0.1−0.1−0.12811333.71−0.1−0.1−0.26081188.73−0.2−0.2−0.13211094.9112−0.1−0.1−0.122327360467.04−0.1−0.1−0.241700559775.61−0.2−0.2−0.132651016649.04The simulation result for the small size number of jobs from the total mean at the bottom shows that the SA-related algorithm performs better in the small size number of jobs.Table4 has β values of 0.2, 0.4, and 0.6, and no obvious features are noted.Table 4
Simulation result forβ values.
ParameterJS_maxJS_minJS_meanJS_maxpiJS_minpiJS_meanpiSA_maxSA_minSA_meanNβMeanMeanMeanMeanMeanMeanMeanMeanMean80.22.926.691.961.814.431.150.100.090.080.42.877.772.501.785.511.610.070.090.050.62.257.212.011.435.071.290.070.080.06100.21.955.941.671.214.181.120.050.060.050.42.096.701.601.334.951.010.060.060.060.61.596.111.381.094.400.930.070.100.08120.21.705.991.361.044.750.880.110.080.100.41.595.931.400.974.590.930.050.090.080.61.326.241.260.924.880.950.100.090.10Mean2.036.511.681.284.751.100.080.080.07Table5 is divided into three different situations of α1,α2,α3. Clearly, in the case of various numbers of jobs, the AEP of the second case is better than the AEP of the first case. The AEP for each case is better than the AEP for the third case.Table 5
Simulation result forα values.
ParameterJS_maxJS_minJS_meanJS_maxpiJS_minpiJS_meanpiSA_maxSA_minSA_meannα1α2α3MeanMeanMeanMeanMeanMeanMeanMeanMean8−0.1−0.1−0.12.107.141.721.265.151.070.060.080.05−0.1−0.1−0.21.895.521.801.323.821.110.050.070.04−0.2−0.2−0.14.049.012.952.436.041.880.130.110.1010−0.1−0.1−0.11.576.131.420.984.530.980.050.060.06−0.1−0.1−0.21.484.521.371.043.200.930.060.060.07−0.2−0.2−0.12.588.101.871.605.791.150.070.100.0612−0.1−0.1−0.11.376.411.230.904.910.850.110.140.10−0.1−0.1−0.21.094.320.990.793.550.760.030.020.02−0.2−0.2−0.12.157.431.801.245.761.150.120.090.15Mean2.036.511.681.284.751.100.080.080.07Table6 compares nine algorithms in total. There are three changes in the number of jobs (n) and β and 2 changes in α1,α2,α3.Table 6
Small size number of jobs analysis variable.
Class level informationClassLevelsValuesAlgorithm9JS_max, JS_maxpi, JS_mean, JS_meanpi, JS_min, JS_minpi, SA_max, SA_mean, and SA_minN38 10 12β30.2 0.4 0.6α12−0.1 −0.2α22−0.1 −0.2α32−0.1 −0.2Before comparing algorithms, normality verification is carried out on the data. If the data is normal, you can use the average of the algorithm to compare pairwise.The residuals are not in line with the normal state, so they cannot be compared using means. We instead use the Kruskal–Wallis test to observe whether the medians of the data are the same (please see Table7). If they are not the same, we can use the median of the algorithm to make pairwise comparisons and observe the calculations for the difference in the median between methods.Table 7
Normality test of residual error of the GLM model in the small size number of jobs.
Normality testTestStatisticsP valueShapiro–WilkW0.936652Pr <W<0.0001Kolmogorov–SmirnovD0.086882Pr <D<0.0100Cramer–von MisesW-Sq0.532874Pr <W-Sq<0.0050Anderson–DarlingA-Sq3.734124PR <A-Sq<0.0050The null hypothesis is that the median of each group is the same, where theP value <0.05, so the null hypothesis is rejected, meaning the median of each group is not the same and multiple comparative analysis can be performed to show the difference between each group (please see Table 8).Table 8
Kruskal–Wallis verification of the small size number of jobs.
Kruskal–Wallis testChi-squareDFPr > ChiSq214.55118<0.0001Figure4 is a box diagram of the nine algorithms scored by nonparametric statistics. Clearly, the results of the SA-related algorithms under the small size number of jobs are superior.Figure 4
Scoring box of the nine algorithms.Table9 shows the results of the pairwise comparison. We take the significance level of 0.05 as the standard. The JS_max algorithm and the JS_mean algorithm are grouped into one group, the JS_mean algorithm is divided into a group with the JS_maxpi algorithm, and the JS_maxpi algorithm is divided into a group with the JS_meanpi algorithm. Finally, the SA-related algorithms are all divided into a group. From this, it can be seen that the SA algorithm is a relatively better group for the small size number of jobs, followed by the JS_meanpi Algorithm, JS_maxpi algorithm, JS_mean algorithm, JS_max algorithm, and finally, the JS_minpi algorithm and JS_min algorithm. There are two key points clearly observed in the grouping. First, the JS algorithm with pi is better. Second, the result obtained by mean is better than max, and max is better than min.Table 9
Pairwise comparison of nine algorithms for the small size number of jobs.
SmallnAlgorithmStatisticP valueJS_max vs. JS_min8.5999<0.0001JS_max vs. JS_mean1.88430.9218JS_max vs. JS_maxpi5.30950.0054JS_max vs. JS_minpi7.7925<0.0001JS_max vs. JS_meanpi6.9494<0.0001JS_max vs. SA_max8.9241<0.0001JS_max vs. SA_min8.9268<0.0001JS_max vs. SA_mean8.9231<0.0001JS_min vs. JS_mean8.7717<0.0001JS_min vs. JS_maxpi8.8692<0.0001JS_min vs. JS_minpi5.06450.0103JS_min vs. JS_meanpi8.8938<0.0001JS_min vs. SA_max8.9239<0.0001JS_min vs. SA_min8.9267<0.0001JS_min vs. SA_mean8.9229<0.0001JS_mean vs. JS_maxpi4.34350.0547JS_mean vs. JS_minpi8.6249<0.0001JS_mean vs. JS_meanpi5.95890.0008JS_mean vs. SA_max8.9246<0.0001JS_mean vs. SA_min8.9273<0.0001JS_mean vs. SA_mean8.9236<0.0001JS_maxpi vs. JS_minpi8.7224<0.0001JS_maxpi vs. JS_meanpi1.78660.9418JS_maxpi vs. SA_max8.9243<0.0001JS_maxpi vs. SA_min8.9270<0.0001JS_maxpi vs. SA_mean8.9233<0.0001JS_minpi vs. JS_meanpi8.8449<0.0001JS_minpi vs. SA_max8.9239<0.0001JS_minpi vs. SA_min8.9267<0.0001JS_minpi vs. SA_mean8.9229<0.0001JS_meanpi vs. SA_max8.9244<0.0001JS_meanpi vs. SA_min8.9272<0.0001JS_meanpi vs. SA_mean8.9234<0.0001SA_max vs. SA_min0.62781.0000SA_max vs. SA_mean0.47901.0000SA_min vs. SA_mean1.17950.9959


### 4.2. Large Size Number of Jobs

The parameters of the large size number of jobs are selected when the number of work pieces (n) is 10, the number of machines (m) is 3, and the final temperature Tf is fixed to 10−8, β is 0.2, α1 is −0.1, α2 is −0.1, and α3 is −0.2. The selections of other parameters are shown in Table 10.Table 10
Parameter selection of the large size number of jobs.
Parametern = 90, m = 3Ti10−3Tf10−8cf0.95Nr90β0.2α1−0.1α2−0.1α3−0.2From the summary of Tables11 and 12, the SA algorithm is the best in calculating the RPD. However, the CPU_time shows that the SA algorithm takes a relatively long time. With pi or without pi, the JS algorithm clearly shows that the solution with pi to the run out of RPD is slightly inferior to the solution without pi. The JS algorithm with pi for the CPU_time is the fastest.Table 11
RPD summary of the large size number of jobs.
ParameterJS_maxJS_minJS_meanJS_maxpiJS_minpiJS_meanpiSA_maxSA_minSA_meanNβα1α2α3MeanMaxMeanMaxMeanMaxMeanMaxMeanMaxMeanMaxMeanMaxMeanMaxMeanMax600.2−0.1−0.1−0.10.221.612.077.920.241.760.261.702.197.920.261.760.111.560.101.450.101.00−0.1−0.1−0.20.170.971.736.500.212.310.211.041.837.780.232.330.080.770.101.350.060.80−0.2−0.2-0.10.201.731.746.410.221.910.241.971.886.500.251.940.060.600.090.830.070.680.4−0.1−0.1−0.10.191.131.847.150.221.470.231.201.957.400.251.480.081.110.061.060.050.28−0.1−0.1−0.20.181.111.686.180.181.420.221.141.807.110.211.440.070.670.071.910.070.65−0.2−0.2−0.10.150.961.836.740.161.490.191.021.957.020.191.530.070.640.081.440.071.170.6−0.1−0.1−0.10.161.342.016.790.191.360.201.382.157.300.211.390.070.530.121.900.050.34−0.1−0.1−0.20.181.402.096.770.201.490.231.502.228.560.221.500.090.680.111.840.060.58−0.2−0.2−0.10.160.951.997.170.191.180.201.022.1211.540.211.190.080.510.061.060.070.57Mean0.181.890.200.222.010.230.080.090.07900.2−0.1−0.1−0.10.130.971.486.350.130.990.151.031.536.770.141.020.060.670.081.000.050.41−0.1−0.1−0.20.121.021.105.010.121.030.141.041.155.020.141.040.060.460.070.980.070.77−0.2−0.2−0.10.141.011.406.470.161.180.171.091.446.480.181.210.080.680.101.610.070.630.4−0.1−0.1−0.10.140.881.394.970.150.870.160.921.455.010.170.880.070.710.081.010.080.78−0.1−0.1−0.20.140.961.355.110.141.030.160.981.405.340.151.070.070.880.070.860.050.17−0.2−0.2−0.10.110.891.515.610.110.850.130.901.565.610.130.870.050.470.070.890.050.660.6−0.1−0.1−0.10.100.661.414.870.120.970.130.731.464.870.140.990.060.400.100.690.060.61−0.1−0.1−0.20.160.981.524.880.171.220.180.991.564.890.181.240.060.650.080.870.080.93−0.2−0.2−0.10.140.871.445.230.171.260.170.881.505.520.191.300.070.760.090.900.080.78Mean0.131.400.140.151.450.160.070.080.071200.2−0.1−0.1−0.10.110.601.093.840.120.580.120.621.123.950.130.630.060.500.090.880.060.56−0.1−0.1−0.20.100.701.123.580.100.750.110.711.163.710.110.760.040.510.100.610.050.58−0.2−0.2−0.10.070.491.143.660.080.500.090.531.184.270.090.510.050.480.070.760.050.490.4−0.1−0.1−0.10.070.611.114.310.080.580.090.651.154.400.090.590.040.390.070.850.050.40−0.1−0.1−0.20.090.711.154.410.101.060.110.791.184.410.111.080.060.760.090.880.050.42−0.2−0.2−0.10.120.701.133.860.140.930.130.731.173.870.150.940.070.670.101.010.070.680.6−0.1−0.1−0.10.080.611.013.610.100.880.100.621.063.610.110.880.050.470.081.180.050.25−0.1−0.1−0.20.090.711.043.820.100.670.110.741.063.830.110.680.040.640.100.750.040.23−0.2−0.2−0.10.090.641.153.540.100.570.110.671.183.550.110.590.060.620.080.610.050.39Mean0.091.100.100.111.140.110.050.090.05Total mean0.131.460.150.161.530.160.070.090.06Table 12
CPU_time summary of the large size number of jobs.
ParameterJS_maxJS_minJS_meanJS_maxpiJS_minpiJS_meanpiSA_maxSA_minSA_meannβα1α2α3MeanMaxMeanMaxMeanMaxMeanMaxMeanMaxMeanMaxMeanMaxMeanMaxMeanMax600.2−0.1−0.1−0.10.020.030.020.030.020.030.000.000.000.000.000.000.190.200.190.200.190.22−0.1−0.1−0.20.020.030.020.030.020.030.000.020.000.000.000.000.190.200.190.200.190.22−0.2−0.2−0.10.020.030.020.030.020.030.000.000.000.020.000.000.190.200.190.220.190.200.4−0.1−0.1−0.10.020.030.020.030.020.030.000.020.000.020.000.000.190.200.190.220.190.20−0.1−0.1−0.20.020.030.020.030.020.030.000.000.000.000.000.020.190.200.190.200.190.20−0.2−0.2−0.10.020.030.020.030.020.030.000.000.000.000.000.000.190.200.190.200.190.200.6−0.1−0.1−0.10.020.030.020.030.020.030.000.020.000.000.000.000.190.200.190.220.190.20−0.1−0.1−0.20.020.030.020.030.020.030.000.000.000.000.000.000.190.200.190.200.190.20−0.2−0.2−0.10.020.030.020.030.020.030.000.000.000.020.000.020.190.200.190.200.190.20Mean0.020.020.020.000.000.000.190.190.19900.2−0.1−0.1−0.10.060.080.060.080.060.060.000.000.000.000.000.000.280.300.280.300.280.30−0.1−0.1−0.20.060.060.060.080.060.060.000.020.000.020.000.000.280.300.290.310.280.30−0.20.2−0.10.060.080.060.060.060.080.000.000.000.020.000.000.280.300.280.300.280.300.4−0.1−0.1−0.10.060.060.060.080.060.060.000.020.000.020.000.000.280.300.290.310.280.30−0.1−0.1−0.20.060.060.060.080.060.060.000.000.000.000.000.020.280.300.280.300.280.30−0.2−0.2−0.10.060.060.060.080.060.080.000.020.000.000.000.000.280.300.290.310.280.300.6−0.1−0.1−0.10.060.080.060.060.060.060.000.020.000.020.000.020.280.300.280.300.280.31−0.1−0.1−0.20.060.060.060.060.060.080.000.020.000.020.000.020.280.300.280.310.280.30−0.2−0.2−0.10.060.080.060.080.060.080.000.000.000.000.000.000.280.300.280.330.280.30Mean0.060.060.060.000.000.000.280.280.281200.2−0.1−0.1−0.10.130.140.130.140.130.140.000.020.000.000.000.020.380.390.380.410.380.41−0.1−0.1−0.20.130.140.130.140.130.140.000.000.000.000.000.020.380.390.380.410.380.39−0.2−0.2−0.10.130.140.130.140.130.140.000.020.000.000.000.020.380.410.380.390.380.390.4−0.1−0.1−0.10.130.140.130.140.130.140.000.000.000.020.000.000.380.390.380.410.380.41−0.1−0.1−0.20.140.140.140.140.140.140.000.000.000.020.000.020.390.410.390.420.390.42−0.2−0.2−0.10.140.160.140.140.140.140.000.000.000.020.000.020.390.410.390.420.390.410.6−0.1−0.1−0.10.140.160.140.140.140.140.000.000.000.020.000.020.390.410.390.390.390.41−0.1−0.1−0.20.140.140.140.140.140.160.000.020.000.020.000.000.390.410.390.440.390.42−0.2−0.2−0.10.140.160.140.160.140.160.000.000.000.020.000.000.390.420.390.420.390.41Mean0.140.130.130.000.000.000.380.380.38Total mean0.070.070.070.000.000.000.280.290.29Table13 shows the residual error in the large size number of jobs is not in line with the normal state, so we also use the same method as the small size number of jobs to compare the relationship between the algorithms.Table 13
Normality test of residual error of the GLM model with the large size number of jobs.
Normality testHypothesis testStatisticsP valueShapiro–WilkW0.916964Pr < W<0.0001Kolmogorov–SmirnovD0.120337Pr < D<0.0100Cramer–von MisesW-Sq0.862822Pr < W-Sq<0.0050Anderson–DarlingA-Sq5.519845PR < A-Sq<0.0050In the Kruskal–Wallis test, the null hypothesis is rejected as with the small size number of jobs, meaning the median of each group is not the same and multiple comparison analysis can be performed to show the differences between each group (please see Table14).Table 14
Kruskal–Wallis test of the small size number of jobs.
Kruskal–Wallis testChi-squareDFPr > ChiSq204.18738<0.0001Figure5 is a box diagram of nine algorithms scored by nonparametric statistics. The figure shows clear differences among SAs and others under the large size number of jobs.Figure 5
Scoring box of nine algorithms.Table15 shows the results of the pairwise comparison. If the P value value is greater than 0.05, it means the effect between the pair is not significant, but they are correlative. In the pairwise comparison, JS_max and JS_mean are in the same group, JS_max and JS_maxpi are in the same group, JS_max and JS_meanpi are in the same group, JS_min and JS_minpi are in the same group, JS_mean and JS_meanpi are in the same group, JS_maxpi and JS_meanpi are in the same group, and SA_max and the SA_mean are in the same group. The results of the SA algorithm and JS algorithms are also significant, so they would not be divided into the same group. The RPD summary of the large size number of jobs shows the solution of the SA algorithm is comparatively better. The SA algorithm is better than the JS algorithm in this case.Table 15
Pairwise comparison of nine algorithms for the large size number of jobs.
BignAlgorithmStatisticP valueJS_max vs. JS_min8.9219<0.0001JS_max JS_mean1.54620.9754JS_max JS_maxpi2.68570.6144JS_max JS_minpi8.9231<0.0001JS_max JS_meanpi3.03130.4434JS_max SA_max8.2129<0.0001JS_max vs. SA_min6.31660.0003JS_max SA_mean8.4541<0.0001JS_min JS_mean8.9231<0.0001JS_min JS_maxpi8.9212<0.0001JS_min JS_minpi1.45630.9831JS_min JS_meanpi8.9238<0.0001JS_min vs. SA_max8.9450<0.0001JS_min vs. SA_min8.9414<0.0001JS_min SA_mean8.9677<0.0001JS_mean JS_maxpi1.29960.9920JS_mean JS_minpi8.9243<0.0001JS_mean JS_meanpi1.70440.9556JS_mean SA_max8.6226<0.0001JS_mean SA_min7.4503<0.0001JS_mean SA_mean8.7932<0.0001JS_maxpi JS_minpi8.9224<0.0001JS_maxpi JS_meanpi0.45431.0000JS_maxpi SA_ma8.8029<0.0001JS_maxpi SA_min8.1199<0.0001JS_maxpi SA_mean8.9094<0.0001JS_minpi JS_meanpi8.9250<0.0001JS_minpi SA_max8.9462<0.0001JS_minpi SA_min8.9426<0.0001JS_minpi SA_mean8.9689<0.0001JS_meanpi SA_max8.8186<0.0001JS_meanpi SA_min8.2291<0.0001JS_meanpi SA_mean8.9242<0.0001SA_max SA_min5.86160.0011SA_max SA_mean1.40430.9866SA_min SA_mean6.7381<0.0001


## 4.1. Small Size Number of Jobs

The parameters of the small size number of jobs are selected as the number of work pieces (n) at 10, number of machines (m) of 3, and the final temperature (Tf) is fixed to 10−8, β is 0.2, α1 is −0.1, α2 is −0.1, and α3 is −0.2. The selections of other parameters are shown in Table 1.As a result of parameter selection, the starting temperatureTi is 10−3, cooling coefficient is 0.95, and the number of tests Nr of Johnson’s algorithm is 10.Next, the parameter selection process is explained in detail.We select the parameter starting temperatureTi. The range is from 10−4 to 104 at 10 times the interval, and the cooling coefficient cf is fixed at 0.95. The number of tests of Johnson’s algorithm Nr is 5, and there are also generated data and parameters defined before selecting parameters.By observing Figure1, it is obvious that only the initial temperature Ti is changed. In this range, it can be observed that the AEP is relatively low at 10−3, so the initial temperature Ti is 10−3.Figure 1
Parameter selection starting temperatureTi change.After fixing the starting temperatureTi to 10−3, we select the parameter cooling coefficient cf, ranging from 0.05 to 0.95 with 0.05 intervals, and fix the number of tests Nr of the Johnson’s algorithm as 5. There are also generated data and parameters defined before selecting the parameters.By selecting the parameter of the cooling coefficientcf, the overall decline in its value is obvious. It becomes flat after reaching 0.80, so we choose a lower value in this part. The cooling coefficient cf is fixed at 0.95. After fixing the starting temperature Ti to 10−3 and the cooling coefficient (Cf) to 0.95 (please see Figure 2), we select the parameter Johnson’s algorithm test times Nr with a range of 1 to 20 and the interval of 1 and see the difference. The generated data and parameters are fixed and defined before selecting the parameters.Figure 2
Parameter selection cooling coefficientcf change.When selecting the parameter Johnson’s algorithm test timesNr, we can see from Figure 3 that although it fluctuates up and down, its AEP value is actually very low, so we choose a lower value in this part. Johnson’s algorithm test times Nr is 10. It shows when the number of work pieces of the B&B algorithm is 12. The results of finding the best solution in a few cases cannot be found, so only a few values (in the Fs column) are recorded. From the viewpoint of the number of nodes and CPU time, the difference in the number of jobs can also be clearly seen.Figure 3
Parameter selection of Johnson’s algorithm test timesNr change.Table2 uses the β values of 0.2, 0.4, and 0.6 to distinguish the table. It can be seen regardless of whether the number of work pieces is 8, 10, or 12, the smaller the β value, the greater the number of nodes. Also, there is no best solution for the CPU time.Table 2
Differentβ for the mean of nodes and CPU time.
ParameterNodeCPU timeNβMeanMean80.298710.110.444740.050.628250.03100.275149110.330.42624453.890.61967233.13120.251984213978.760.427751022585.760.616943700327.17Table3 is a table distinguished by three different situations of α1,α2,α3. It can be observed that regardless of whether the number of work pieces is 8, 10, or 12, the number of nodes and CPU time for finding the best solution for the second case are all more than the third case, and the third case is more than the first case.Table 3
Differentβ for the mean of nodes and CPU time.
nParameterNodeCPU timeα1α2α3MeanMean8−0.1−0.1−0.144480.06−0.1−0.1−0.278600.08−0.2−0.2−0.148610.0510−0.1−0.1−0.12811333.71−0.1−0.1−0.26081188.73−0.2−0.2−0.13211094.9112−0.1−0.1−0.122327360467.04−0.1−0.1−0.241700559775.61−0.2−0.2−0.132651016649.04The simulation result for the small size number of jobs from the total mean at the bottom shows that the SA-related algorithm performs better in the small size number of jobs.Table4 has β values of 0.2, 0.4, and 0.6, and no obvious features are noted.Table 4
Simulation result forβ values.
ParameterJS_maxJS_minJS_meanJS_maxpiJS_minpiJS_meanpiSA_maxSA_minSA_meanNβMeanMeanMeanMeanMeanMeanMeanMeanMean80.22.926.691.961.814.431.150.100.090.080.42.877.772.501.785.511.610.070.090.050.62.257.212.011.435.071.290.070.080.06100.21.955.941.671.214.181.120.050.060.050.42.096.701.601.334.951.010.060.060.060.61.596.111.381.094.400.930.070.100.08120.21.705.991.361.044.750.880.110.080.100.41.595.931.400.974.590.930.050.090.080.61.326.241.260.924.880.950.100.090.10Mean2.036.511.681.284.751.100.080.080.07Table5 is divided into three different situations of α1,α2,α3. Clearly, in the case of various numbers of jobs, the AEP of the second case is better than the AEP of the first case. The AEP for each case is better than the AEP for the third case.Table 5
Simulation result forα values.
ParameterJS_maxJS_minJS_meanJS_maxpiJS_minpiJS_meanpiSA_maxSA_minSA_meannα1α2α3MeanMeanMeanMeanMeanMeanMeanMeanMean8−0.1−0.1−0.12.107.141.721.265.151.070.060.080.05−0.1−0.1−0.21.895.521.801.323.821.110.050.070.04−0.2−0.2−0.14.049.012.952.436.041.880.130.110.1010−0.1−0.1−0.11.576.131.420.984.530.980.050.060.06−0.1−0.1−0.21.484.521.371.043.200.930.060.060.07−0.2−0.2−0.12.588.101.871.605.791.150.070.100.0612−0.1−0.1−0.11.376.411.230.904.910.850.110.140.10−0.1−0.1−0.21.094.320.990.793.550.760.030.020.02−0.2−0.2−0.12.157.431.801.245.761.150.120.090.15Mean2.036.511.681.284.751.100.080.080.07Table6 compares nine algorithms in total. There are three changes in the number of jobs (n) and β and 2 changes in α1,α2,α3.Table 6
Small size number of jobs analysis variable.
Class level informationClassLevelsValuesAlgorithm9JS_max, JS_maxpi, JS_mean, JS_meanpi, JS_min, JS_minpi, SA_max, SA_mean, and SA_minN38 10 12β30.2 0.4 0.6α12−0.1 −0.2α22−0.1 −0.2α32−0.1 −0.2Before comparing algorithms, normality verification is carried out on the data. If the data is normal, you can use the average of the algorithm to compare pairwise.The residuals are not in line with the normal state, so they cannot be compared using means. We instead use the Kruskal–Wallis test to observe whether the medians of the data are the same (please see Table7). If they are not the same, we can use the median of the algorithm to make pairwise comparisons and observe the calculations for the difference in the median between methods.Table 7
Normality test of residual error of the GLM model in the small size number of jobs.
Normality testTestStatisticsP valueShapiro–WilkW0.936652Pr <W<0.0001Kolmogorov–SmirnovD0.086882Pr <D<0.0100Cramer–von MisesW-Sq0.532874Pr <W-Sq<0.0050Anderson–DarlingA-Sq3.734124PR <A-Sq<0.0050The null hypothesis is that the median of each group is the same, where theP value <0.05, so the null hypothesis is rejected, meaning the median of each group is not the same and multiple comparative analysis can be performed to show the difference between each group (please see Table 8).Table 8
Kruskal–Wallis verification of the small size number of jobs.
Kruskal–Wallis testChi-squareDFPr > ChiSq214.55118<0.0001Figure4 is a box diagram of the nine algorithms scored by nonparametric statistics. Clearly, the results of the SA-related algorithms under the small size number of jobs are superior.Figure 4
Scoring box of the nine algorithms.Table9 shows the results of the pairwise comparison. We take the significance level of 0.05 as the standard. The JS_max algorithm and the JS_mean algorithm are grouped into one group, the JS_mean algorithm is divided into a group with the JS_maxpi algorithm, and the JS_maxpi algorithm is divided into a group with the JS_meanpi algorithm. Finally, the SA-related algorithms are all divided into a group. From this, it can be seen that the SA algorithm is a relatively better group for the small size number of jobs, followed by the JS_meanpi Algorithm, JS_maxpi algorithm, JS_mean algorithm, JS_max algorithm, and finally, the JS_minpi algorithm and JS_min algorithm. There are two key points clearly observed in the grouping. First, the JS algorithm with pi is better. Second, the result obtained by mean is better than max, and max is better than min.Table 9
Pairwise comparison of nine algorithms for the small size number of jobs.
SmallnAlgorithmStatisticP valueJS_max vs. JS_min8.5999<0.0001JS_max vs. JS_mean1.88430.9218JS_max vs. JS_maxpi5.30950.0054JS_max vs. JS_minpi7.7925<0.0001JS_max vs. JS_meanpi6.9494<0.0001JS_max vs. SA_max8.9241<0.0001JS_max vs. SA_min8.9268<0.0001JS_max vs. SA_mean8.9231<0.0001JS_min vs. JS_mean8.7717<0.0001JS_min vs. JS_maxpi8.8692<0.0001JS_min vs. JS_minpi5.06450.0103JS_min vs. JS_meanpi8.8938<0.0001JS_min vs. SA_max8.9239<0.0001JS_min vs. SA_min8.9267<0.0001JS_min vs. SA_mean8.9229<0.0001JS_mean vs. JS_maxpi4.34350.0547JS_mean vs. JS_minpi8.6249<0.0001JS_mean vs. JS_meanpi5.95890.0008JS_mean vs. SA_max8.9246<0.0001JS_mean vs. SA_min8.9273<0.0001JS_mean vs. SA_mean8.9236<0.0001JS_maxpi vs. JS_minpi8.7224<0.0001JS_maxpi vs. JS_meanpi1.78660.9418JS_maxpi vs. SA_max8.9243<0.0001JS_maxpi vs. SA_min8.9270<0.0001JS_maxpi vs. SA_mean8.9233<0.0001JS_minpi vs. JS_meanpi8.8449<0.0001JS_minpi vs. SA_max8.9239<0.0001JS_minpi vs. SA_min8.9267<0.0001JS_minpi vs. SA_mean8.9229<0.0001JS_meanpi vs. SA_max8.9244<0.0001JS_meanpi vs. SA_min8.9272<0.0001JS_meanpi vs. SA_mean8.9234<0.0001SA_max vs. SA_min0.62781.0000SA_max vs. SA_mean0.47901.0000SA_min vs. SA_mean1.17950.9959


## 4.2. Large Size Number of Jobs

The parameters of the large size number of jobs are selected when the number of work pieces (n) is 10, the number of machines (m) is 3, and the final temperature Tf is fixed to 10−8, β is 0.2, α1 is −0.1, α2 is −0.1, and α3 is −0.2. The selections of other parameters are shown in Table 10.Table 10
Parameter selection of the large size number of jobs.
Parametern = 90, m = 3Ti10−3Tf10−8cf0.95Nr90β0.2α1−0.1α2−0.1α3−0.2From the summary of Tables11 and 12, the SA algorithm is the best in calculating the RPD. However, the CPU_time shows that the SA algorithm takes a relatively long time. With pi or without pi, the JS algorithm clearly shows that the solution with pi to the run out of RPD is slightly inferior to the solution without pi. The JS algorithm with pi for the CPU_time is the fastest.Table 11
RPD summary of the large size number of jobs.
ParameterJS_maxJS_minJS_meanJS_maxpiJS_minpiJS_meanpiSA_maxSA_minSA_meanNβα1α2α3MeanMaxMeanMaxMeanMaxMeanMaxMeanMaxMeanMaxMeanMaxMeanMaxMeanMax600.2−0.1−0.1−0.10.221.612.077.920.241.760.261.702.197.920.261.760.111.560.101.450.101.00−0.1−0.1−0.20.170.971.736.500.212.310.211.041.837.780.232.330.080.770.101.350.060.80−0.2−0.2-0.10.201.731.746.410.221.910.241.971.886.500.251.940.060.600.090.830.070.680.4−0.1−0.1−0.10.191.131.847.150.221.470.231.201.957.400.251.480.081.110.061.060.050.28−0.1−0.1−0.20.181.111.686.180.181.420.221.141.807.110.211.440.070.670.071.910.070.65−0.2−0.2−0.10.150.961.836.740.161.490.191.021.957.020.191.530.070.640.081.440.071.170.6−0.1−0.1−0.10.161.342.016.790.191.360.201.382.157.300.211.390.070.530.121.900.050.34−0.1−0.1−0.20.181.402.096.770.201.490.231.502.228.560.221.500.090.680.111.840.060.58−0.2−0.2−0.10.160.951.997.170.191.180.201.022.1211.540.211.190.080.510.061.060.070.57Mean0.181.890.200.222.010.230.080.090.07900.2−0.1−0.1−0.10.130.971.486.350.130.990.151.031.536.770.141.020.060.670.081.000.050.41−0.1−0.1−0.20.121.021.105.010.121.030.141.041.155.020.141.040.060.460.070.980.070.77−0.2−0.2−0.10.141.011.406.470.161.180.171.091.446.480.181.210.080.680.101.610.070.630.4−0.1−0.1−0.10.140.881.394.970.150.870.160.921.455.010.170.880.070.710.081.010.080.78−0.1−0.1−0.20.140.961.355.110.141.030.160.981.405.340.151.070.070.880.070.860.050.17−0.2−0.2−0.10.110.891.515.610.110.850.130.901.565.610.130.870.050.470.070.890.050.660.6−0.1−0.1−0.10.100.661.414.870.120.970.130.731.464.870.140.990.060.400.100.690.060.61−0.1−0.1−0.20.160.981.524.880.171.220.180.991.564.890.181.240.060.650.080.870.080.93−0.2−0.2−0.10.140.871.445.230.171.260.170.881.505.520.191.300.070.760.090.900.080.78Mean0.131.400.140.151.450.160.070.080.071200.2−0.1−0.1−0.10.110.601.093.840.120.580.120.621.123.950.130.630.060.500.090.880.060.56−0.1−0.1−0.20.100.701.123.580.100.750.110.711.163.710.110.760.040.510.100.610.050.58−0.2−0.2−0.10.070.491.143.660.080.500.090.531.184.270.090.510.050.480.070.760.050.490.4−0.1−0.1−0.10.070.611.114.310.080.580.090.651.154.400.090.590.040.390.070.850.050.40−0.1−0.1−0.20.090.711.154.410.101.060.110.791.184.410.111.080.060.760.090.880.050.42−0.2−0.2−0.10.120.701.133.860.140.930.130.731.173.870.150.940.070.670.101.010.070.680.6−0.1−0.1−0.10.080.611.013.610.100.880.100.621.063.610.110.880.050.470.081.180.050.25−0.1−0.1−0.20.090.711.043.820.100.670.110.741.063.830.110.680.040.640.100.750.040.23−0.2−0.2−0.10.090.641.153.540.100.570.110.671.183.550.110.590.060.620.080.610.050.39Mean0.091.100.100.111.140.110.050.090.05Total mean0.131.460.150.161.530.160.070.090.06Table 12
CPU_time summary of the large size number of jobs.
ParameterJS_maxJS_minJS_meanJS_maxpiJS_minpiJS_meanpiSA_maxSA_minSA_meannβα1α2α3MeanMaxMeanMaxMeanMaxMeanMaxMeanMaxMeanMaxMeanMaxMeanMaxMeanMax600.2−0.1−0.1−0.10.020.030.020.030.020.030.000.000.000.000.000.000.190.200.190.200.190.22−0.1−0.1−0.20.020.030.020.030.020.030.000.020.000.000.000.000.190.200.190.200.190.22−0.2−0.2−0.10.020.030.020.030.020.030.000.000.000.020.000.000.190.200.190.220.190.200.4−0.1−0.1−0.10.020.030.020.030.020.030.000.020.000.020.000.000.190.200.190.220.190.20−0.1−0.1−0.20.020.030.020.030.020.030.000.000.000.000.000.020.190.200.190.200.190.20−0.2−0.2−0.10.020.030.020.030.020.030.000.000.000.000.000.000.190.200.190.200.190.200.6−0.1−0.1−0.10.020.030.020.030.020.030.000.020.000.000.000.000.190.200.190.220.190.20−0.1−0.1−0.20.020.030.020.030.020.030.000.000.000.000.000.000.190.200.190.200.190.20−0.2−0.2−0.10.020.030.020.030.020.030.000.000.000.020.000.020.190.200.190.200.190.20Mean0.020.020.020.000.000.000.190.190.19900.2−0.1−0.1−0.10.060.080.060.080.060.060.000.000.000.000.000.000.280.300.280.300.280.30−0.1−0.1−0.20.060.060.060.080.060.060.000.020.000.020.000.000.280.300.290.310.280.30−0.20.2−0.10.060.080.060.060.060.080.000.000.000.020.000.000.280.300.280.300.280.300.4−0.1−0.1−0.10.060.060.060.080.060.060.000.020.000.020.000.000.280.300.290.310.280.30−0.1−0.1−0.20.060.060.060.080.060.060.000.000.000.000.000.020.280.300.280.300.280.30−0.2−0.2−0.10.060.060.060.080.060.080.000.020.000.000.000.000.280.300.290.310.280.300.6−0.1−0.1−0.10.060.080.060.060.060.060.000.020.000.020.000.020.280.300.280.300.280.31−0.1−0.1−0.20.060.060.060.060.060.080.000.020.000.020.000.020.280.300.280.310.280.30−0.2−0.2−0.10.060.080.060.080.060.080.000.000.000.000.000.000.280.300.280.330.280.30Mean0.060.060.060.000.000.000.280.280.281200.2−0.1−0.1−0.10.130.140.130.140.130.140.000.020.000.000.000.020.380.390.380.410.380.41−0.1−0.1−0.20.130.140.130.140.130.140.000.000.000.000.000.020.380.390.380.410.380.39−0.2−0.2−0.10.130.140.130.140.130.140.000.020.000.000.000.020.380.410.380.390.380.390.4−0.1−0.1−0.10.130.140.130.140.130.140.000.000.000.020.000.000.380.390.380.410.380.41−0.1−0.1−0.20.140.140.140.140.140.140.000.000.000.020.000.020.390.410.390.420.390.42−0.2−0.2−0.10.140.160.140.140.140.140.000.000.000.020.000.020.390.410.390.420.390.410.6−0.1−0.1−0.10.140.160.140.140.140.140.000.000.000.020.000.020.390.410.390.390.390.41−0.1−0.1−0.20.140.140.140.140.140.160.000.020.000.020.000.000.390.410.390.440.390.42−0.2−0.2−0.10.140.160.140.160.140.160.000.000.000.020.000.000.390.420.390.420.390.41Mean0.140.130.130.000.000.000.380.380.38Total mean0.070.070.070.000.000.000.280.290.29Table13 shows the residual error in the large size number of jobs is not in line with the normal state, so we also use the same method as the small size number of jobs to compare the relationship between the algorithms.Table 13
Normality test of residual error of the GLM model with the large size number of jobs.
Normality testHypothesis testStatisticsP valueShapiro–WilkW0.916964Pr < W<0.0001Kolmogorov–SmirnovD0.120337Pr < D<0.0100Cramer–von MisesW-Sq0.862822Pr < W-Sq<0.0050Anderson–DarlingA-Sq5.519845PR < A-Sq<0.0050In the Kruskal–Wallis test, the null hypothesis is rejected as with the small size number of jobs, meaning the median of each group is not the same and multiple comparison analysis can be performed to show the differences between each group (please see Table14).Table 14
Kruskal–Wallis test of the small size number of jobs.
Kruskal–Wallis testChi-squareDFPr > ChiSq204.18738<0.0001Figure5 is a box diagram of nine algorithms scored by nonparametric statistics. The figure shows clear differences among SAs and others under the large size number of jobs.Figure 5
Scoring box of nine algorithms.Table15 shows the results of the pairwise comparison. If the P value value is greater than 0.05, it means the effect between the pair is not significant, but they are correlative. In the pairwise comparison, JS_max and JS_mean are in the same group, JS_max and JS_maxpi are in the same group, JS_max and JS_meanpi are in the same group, JS_min and JS_minpi are in the same group, JS_mean and JS_meanpi are in the same group, JS_maxpi and JS_meanpi are in the same group, and SA_max and the SA_mean are in the same group. The results of the SA algorithm and JS algorithms are also significant, so they would not be divided into the same group. The RPD summary of the large size number of jobs shows the solution of the SA algorithm is comparatively better. The SA algorithm is better than the JS algorithm in this case.Table 15
Pairwise comparison of nine algorithms for the large size number of jobs.
BignAlgorithmStatisticP valueJS_max vs. JS_min8.9219<0.0001JS_max JS_mean1.54620.9754JS_max JS_maxpi2.68570.6144JS_max JS_minpi8.9231<0.0001JS_max JS_meanpi3.03130.4434JS_max SA_max8.2129<0.0001JS_max vs. SA_min6.31660.0003JS_max SA_mean8.4541<0.0001JS_min JS_mean8.9231<0.0001JS_min JS_maxpi8.9212<0.0001JS_min JS_minpi1.45630.9831JS_min JS_meanpi8.9238<0.0001JS_min vs. SA_max8.9450<0.0001JS_min vs. SA_min8.9414<0.0001JS_min SA_mean8.9677<0.0001JS_mean JS_maxpi1.29960.9920JS_mean JS_minpi8.9243<0.0001JS_mean JS_meanpi1.70440.9556JS_mean SA_max8.6226<0.0001JS_mean SA_min7.4503<0.0001JS_mean SA_mean8.7932<0.0001JS_maxpi JS_minpi8.9224<0.0001JS_maxpi JS_meanpi0.45431.0000JS_maxpi SA_ma8.8029<0.0001JS_maxpi SA_min8.1199<0.0001JS_maxpi SA_mean8.9094<0.0001JS_minpi JS_meanpi8.9250<0.0001JS_minpi SA_max8.9462<0.0001JS_minpi SA_min8.9426<0.0001JS_minpi SA_mean8.9689<0.0001JS_meanpi SA_max8.8186<0.0001JS_meanpi SA_min8.2291<0.0001JS_meanpi SA_mean8.9242<0.0001SA_max SA_min5.86160.0011SA_max SA_mean1.40430.9866SA_min SA_mean6.7381<0.0001


## 5. Conclusions

This study focuses on two-stage three-machine flow shop assembly problems mixed with a controllable number and sum-of-processing times-based learning effect, in which job processing time is considered to be a function of the control of the truncation parameter and learning based on the sum of the processing time. We derive several dominance rules, lemmas, and lower bounds applied in the branch-and-bound method. On the other hand, three simulated annealing algorithms are proposed for finding approximate solutions. Computational results show that the SA algorithm is relatively better for the small size number of jobs. In the large size number of jobs, the solution of the SA algorithm is comparatively better. Both in the small and large size number of jobs situation, the SA algorithm is better than the JS algorithm in this study. For future research, it would be interesting to develop more powerful dominance rules and a sharper lower bound on the optimal solution for medium-size instances.



---

*Source: 4085718-2020-10-10.xml*