# An Improved Genetic Algorithm with Adaptive Variable Neighborhood Search for FJSP
## 4 Iga-Avns  
### Encoding and Decoding  
Each solution of FJSP consists of two parts [15]: one is to sort the operations assigned on the machine, that is, the operation sequence (OS); the other is to assign each operation to a machine set, that is, machine assignment (MA), which means that the algorithm assigns each operation to the corresponding machine and calculates its start time and end time. The number in the sequence OS is the operation index. The order in which each job j appears in the OS represents the processing order of  
Figure 1: Flow chart of improved genetic algorithm with adaptive variable neighborhood search (IGA-AVNS). GA: genetic algorithm. each operation of the job. See the OS of the chromosome in Figure 2: 1 2 1 1 2. The first 1 represents the operation \(O_{1,1}\) the job \(J_{1}\), the first 2 represents the first operation \(O_{2,1}\) of the job \(J_{2}\), the second 1 represents the second operation \(O_{1,2}\) of the job \(J_{1}\), and so on. The processing order of each operation of this chromosome is:  
\[O_{1,1}\to O_{2,1}\to O_{1,2}\to O_{1,3}\to O_{2,2}\]  
The number in the MA is the machine number. Each number indicates the machine number of the corresponding operation selected in the optional machine set. See Figure 2, where the first 1 in the figure indicates the processing machine number of the corresponding operation \(O_{1,1}\) in the optional machine \(M=\{M_{1},M_{3}\}\), that is, \(M_{1}\). MA and OS have the same length, which is equal to the sum of the operations of all the jobs, that is, L, and the length of the chromosome is 2L. Table 1 is the processing schedule for the \(2\times 4\) problem, and Figure 3 is the Gantt chart for solving the problem. Decoding is the process of converting a chromosome code into feasible scheduling. The steps are as follows:  
Step 1: Read each gene of the OS and convert it to the corresponding operation \(O_{i,j}\);  
Step 2: Read each gene on the MA, obtain the processing machine number \(M_{k}\) corresponding to each operation, and obtain the processing time \(t_{i,j,k}\) of each operation from the processing time matrix;  
Step 2.1: If the operation \(O_{i,j}\) is the first operation of the job \(i\), process directly from the zero time on the machine \(M_{k}\); if the process \(O_{i,j}\) is the first operation of the machine \(M_{k}\), process from the end time \begin{table}
\begin{tabular}{c c c c c c} \hline \hline
**Jobs** & **Operation** & \(M_{1}\) & \(M_{2}\) & \(M_{3}\) & \(M_{4}\) \\ \hline \multirow{3}{*}{\(J_{1}\)} & \(O_{1,1}\) & 2 & 999 & 3 & 999 \\ \cline{2-6}  & \(O_{1,2}\) & 5 & 999 & 999 & 2 \\ \cline{2-6}  & \(O_{1,3}\) & 999 & 3 & 4 & 1 \\ \hline \multirow{3}{*}{\(J_{2}\)} & \(O_{2,1}\) & 7 & 3 & 9 & 999 \\ \cline{2-6}  & \(O_{2,2}\) & 3 & 1 & 999 & 6 \\ \hline \end{tabular}
\end{table} 
Table 1: Processing time on the \(2\times 4\) problem. Figure 3: Gantt chart of the \(2\times 4\) problem. Figure 2: Encoding of the \(2\times 4\) problem. OS: operation sequence; MA: machine assignment. of the previous operation \(O_{i-1,j}\) on the machine, \(M_{k}\). Otherwise, find the idle interval period [\(S_{t}\),\(E_{t}\)] of the machine \(M_{k}\), in which \(S_{t}\) represents the start time of the time interval, and \(E_{t}\) represents the end time of the time interval. Equation (2) obtains the earliest processing time \(EST_{1}\) of the operation \(O_{i,j}\);  
Step 2.2: Determine whether the appropriate idle interval to process the current operation \(O_{i,j}\) is found according to (3), and if yes, insert \(O_{i,j}\) into the current time period, otherwise process the machine \(M_{k}\) at the earliest processing time of \(EST_{2}\) obtained according to Equation (4);  
Step 3: Update the processing information of each machine;  
Step 4: Determine whether all the genes of the chromosome are decoded, and if yes, end, otherwise, go to Step 2.