# An Improved Genetic Algorithm with Adaptive Variable Neighborhood Search for FJSP
## 5 Simulation and Analysis  
The algorithm was written in Python programming language version 3.7.3 and was run on a MacBook Pro with a 2.7 GHz processor and 8 GB RAM of APPLE inc. in 2015. Tested by three international standard examples, each example runs the IGA-AVNS algorithm 10 times to find the minimum value of the completion time. As the difficulty of the FJSP problem is closely related to the scale of the problem, the parameters are selected according to the following rules: n is the number of jobs, m is the number of machines; number of iterations equal \(10\times n\times m\); population size equals to \(n\times m\); the crossover probability \(p_{c}\) is 0.8; the mutation probability \(p_{m}\) is 0.1; the number of neighborhood cycles \(p\) is 10. Initial population generation method: MA--60% GSO, 20% tournament, and 20% random; OS--random generation. The first set of data are selected from a set of three questions proposed by [PERSON] et al. (2016). Problem \(8\times 8\) is a P-FJSP that is composed of 8 jobs with 27 operations which can be processed on 8 machines; problem \(10\times 10\) is a T-FJSP that consists of 10 jobs with 30 operations that can be processed on 10 machines; problem \(15\times 10\) is a T-FJSP that is comprised of 15 jobs with 56 operations which can be performed on 10 machines. The details about Kacem data can be found in ([PERSON] et al., 2013). The test results are compared with the results obtained by the Kacem method ([PERSON] et al., 2016), the Xia method ([PERSON] et al., 2013), the hybrid genetic tabu search (HGTS) proposed by [PERSON] et al. (2014), the proposed varibale neighbourhood search (PVNS) proposed by [PERSON] et al. (2015), and the Heuristic proposed by [PERSON] et al. (2016). The simulation results are shown in Table 2. Figure 6a is a Gantt chart of the optimal solution for the Kacem \(8\times 8\) problem obtained by the IGA-AVNS. Figure 5: The flow chart of the adaptive variable neighborhood search algorithm. The second set of data comes from the BRdata (Brandimarte 1993 ([PERSON], 1993)), which includes 10 problems. The number of jobs is from 10 to 20, the number of machines is from 4 to 15, and the number of operations of each problem ranges from 5 to 15. Table 3 lists the results of the algorithm in this paper:  
Best heuristic solution \(x^{*}\): The minimum value of the completion time obtained after 10 times of operations;  
Average value \(Av(x^{*})\): The average of the completion time obtained after 10 times of operations;  
The relative deviation \(dev_{1}\): The equation of the relative deviation between the best heuristic solution \(x^{*}\) and the best-known lower bound (LB). The calculation method is shown in Equation (8). Figure 6b shows the Gantt chart of the best heuristic solution of the BRdata MK01 problem obtained by the IGA-AVNS algorithm. \begin{table}
\begin{tabular}{c c c c c c c} \hline \hline \(n\times m\) & **Kacem** & **Xia** & **HGTS** & **PVNS** & **Heuristic** & **IGA-AVNS** \\ \hline \(8\times 8\) & 15 & 15 & 14 & 14 & 15 & 14 \\ \hline \(10\times 10\) & 7 & 7 & 7 & 7 & 7 & 7 \\ \hline \(15\times 15\) & 24 & 12 & 11 & 12 & 12 & 11 \\ \hline \hline \end{tabular} HGTS: hybrid genetic tabu search; PVNS: proposed varibale neighbourhood search.  
\end{table} 
Table 2: Comparison with other algorithms on flexible job-shop scheduling problems (FJSPs) from the Kacem data. Figure 6: Gantt chart of the best heuristic solution: (**a**) is the \(8\times 8\) problem from Kacem; (**b**) is MK01 from BRdata. The relative deviation \(dev_{2}\): The equation of relative deviation for the best heuristic solution obtained by IGA-AVNS and the compared algorithms. The calculation method is shown in Equation (9). \(CM_{our}\) represents the optimal result obtained by IGA-AVNS. \(CM_{other}\) represents the best heuristic solution of the compared algorithms. If the value of \(dev_{2}\) is positive, the solution obtained by the compared algorithm is better. If the value of \(dev_{2}\) is negative, the solution obtained by the IGA-AVNS is better.