## 4 Calibration of the Proposed Algorithms  
### Simulation Policy Verification\(\overline{\alpha}\)  
In order to verify the simulation policy mentioned above, a set of instances are generated: \(n\)\(\in\)[20,40,60,80,100], \(s\)\(\in\)[4,6,8]. Ten instances are generated for each combination of \(n\) and \(s\), and a total of 150 instances are obtained. The processing time is generated from the uniform distribution [1], and the number of parallel machines M\({}_{k}\) are generated from the uniform distribution [1,5]. The three simulation policies were constructed in comparison with 4-Rule in Section 3.2.3. The comparison policies are: 4-Rule without continuous expansion (N-Expan), NEH-LPT(\(\lambda\)) and random policy (Random). Simulation threshold: P = 4, taken the combination of expansion and exploration parameters as C = 0.5, D = 10,000. These proposed algorithms were coded in MATLAB 2016a, and run on Intel Core i5-3470 3.2 GHz PC with 4 GB memory. The ISP-MCTS limited their run time to 30 \(n\times s\) ms and ran two fixed replications. The minimum completion time C\({}_{\text{min}}\) is the optimal result of all simulation policies under the current instance. The deviation between the final solution of each simulation policy and C\({}_{\text{min}}\) is as shown in the following Equation (15):  
\[\text{RPI}(\text{C}_{i})=(\text{C}_{i}-\text{C}_{\text{min}})/\text{C}_{\text {min}}\times 100\%, \tag{15}\]  
In Equation (15), C\({}_{i}\) is the solution value of the current simulation policy. The average relative percentage increase (ARPI) of the 10 sets of problems under each \(n\) and \(s\) combination is shown in Table 1. It can be seen that the average deviation of 4-Rule in the four-simulation policy is the smallest, with the average deviation of 0.07%. Meanwhile, the average deviation of the solution of the 4-Rule simulation policy is better than the simulation policy of the comparison. Simulation policies were analyzed using a 40 \(\times\) 6 case instance. Figure 2a shows the relationship between the number of iterations and the node depth. The number of callbacks and average depth of callbacks for each simulation policy are shown in Figure 2b. From Figure 2, NEH-LPT(\(\lambda\)) has the greater heuristic depth than the other three simulation policies throughout the iteration. In the iterative process, the number of NEH-LPT(\(\lambda\)) callbacks are the least, and the average depth of NEH-LPT(\(\lambda\)) callbacks are less than the two algorithms of 4-Rule and N-Expan. Therefore, it can be concluded that the NEH-LPT(\(\lambda\)) can easily fall into local minimum. The evaluation positioning is not accurate, and the N-Expan has a high callback frequency in the heuristic process. Therefore, the search depth of the N-Expan is less than 4-Rule. The Random has the least depth of search. From Figure 2b, since 4-Rule has the largest average callback depth, the 4-Rule can be used to accurately locate the branch area within a limited number of callbacks. \begin{table}
\begin{tabular}{c c c c c} \hline
**Problem** & **4-Rule** & **N-Expan** & **NEH-LPT(\(\lambda\))** & **Random** \\ \hline
20 \(\times\) 4 & 0.01 & 0.02 & 4.92 & 12.23 \\
20 \(\times\) 6 & 0.03 & 0.04 & 4.37 & 13.11 \\
20 \(\times\) 8 & 0.15 & 0.29 & 5.76 & 14.45 \\
40 \(\times\) 4 & 0.08 & 0.12 & 4.11 & 10.17 \\
40 \(\times\) 6 & 0.14 & 0.37 & 4.77 & 13.67 \\
40 \(\times\) 8 & 0.11 & 0.28 & 5.67 & 15.42 \\
60 \(\times\) 4 & 0.04 & 0.16 & 4.52 & 12.83 \\
60 \(\times\) 6 & 0.07 & 0.52 & 4.87 & 14.17 \\
60 \(\times\) 8 & 0.13 & 0.31 & 5.12 & 17.85 \\
80 \(\times\) 4 & 0.02 & 0.47 & 2.31 & 11.77 \\
80 \(\times\) 6 & 0.03 & 0.17 & 7.57 & 13.46 \\
80 \(\times\) 8 & 0.06 & 0.24 & 6.86 & 15.52 \\
100 \(\times\) 4 & 0.03 & 0.23 & 3.18 & 12.83 \\
100 \(\times\) 6 & 0.08 & 0.29 & 3.57 & 17.51 \\
100 \(\times\) 8 & 0.07 & 0.61 & 6.85 & 21.84 \\ Ave. & 0.07 & 0.275 & 4.963 & 14.455 \\ \hline \end{tabular} Notes: RPI: Relative percentage increase. NEH-LPT: the algorithm of [PERSON], Enscore and Ham - longest processing time.  
\end{table}