## 4 The Proposed GA  
GAs are well-known stochastic search algorithms to solve combinatorial optimization problems. The original idea was developed by [PERSON] [36]. In a GA, a population is maintained by selection, crossover and mutation operators until a stopping criterion is satisfied and an optimal/best solution is obtained. However, it is likely to be trapped in local optima [37]. As a result, immigration strategies, such as random immigrants [38] and elitism-based immigrants [39], have been proposed to enhance the diversity of chromosomes in the population [40]. In this paper, we develop a trajectory-based immigrant scheme to maintain the diversity of chromosomes in each population. Trajectory-based immigration schemes are not like random-based immigrant or elitism-based immigrant schemes. The former (random-based immigrant scheme) randomly generated immigrants. Regarding the latter, it adopted the elite chromosome as a base to generate immigrants with better solution quality in this way. In this paper, we develop a solution-characteristic reserved technology based on solution extraction knowledge matrices to extract the relation between job and position, job and job, and from job to job for each feasible solution. The solution extraction knowledge matrices are called job-position trajectory (_JPT_), job-job trajectory (_JJT_) and from-to trajectory (_FTT_). Based on the information provided by the three matrices, we develop a trajectory-based immigration scheme such that the generated immigrants can gain a balance between randomness and solution quality for the GA. Next, the steps for building three trajectory matrices are described as follows. Step 1. Generate feasible schedules \(\pi_{y}\) randomly and obtain the corresponding _TWT_ value \(x_{y}\), \(y=1,\,2,\,\ldots,\,N\). \(N\) is the number of the population. Step 2. Calculate the mean (\(\overline{x}=\sum x_{y}/N\)) and standard deviation (\(\sigma=\sqrt{\sum\left(x_{y}-\overline{x}\right)^{2}/N-1}\)) for this group. Step 3. Obtain a semaphore value (\(s_{y}\)) for each schedule \(\pi_{y}\) by normalization, i.e., \(s_{y}=(\overline{x}-x_{y})/\sigma\). Note that a larger signal is better to minimize the _TWT_. Step 4. Initialize matrices _CJP_, _CJI_, _CFT_, _SJP_, _SJ_ and _SFT_. Step 5. Complete count matrix (_CJP_) by counting the number of jobs \(i\) occupied at position \(j\) in schedule \(\pi_{y}\), and in a similar fashion to complete matrices (_CJI_ and _CFT_) if job \(i\) is before job \(j\) in schedule \(\pi_{y}\), and if job \(i\) is from to job \(j\) (job \(i\) and \(j\) is adjacent). Step 6. Complete semaphore matrix _SJP_ by accumulating semaphore value (\(s_{y}\)) if job \(i\) occupied position \(j\) in schedule \(\pi_{y}\), and in a similar fashion to complete matrix _SJ_ if job \(i\) is before job \(j\) in schedule \(\pi_{y}\), and matrix _SFT_ if from the job \(i\) is to job \(j\). Step 7. Obtain each element of the job-position trajectory (_JPT_) matrix by the following equation:  
\[JPT_{ij}= \begin{cases}0&if\ CJP_{ij}=0\\ \frac{SJP_{ij}}{CJP_{ij}}&otherwise\end{cases} \forall\quad \begin{cases}i=1,2,3, \ldots,n\\ j=1,2,3,\ldots,n\end{cases} \]  
Step 8. Obtain each element of the job-job trajectory (_JJT_) matrix by the following equation:  
\[JJT_{ij}= \begin{cases}0&if\ CJJ_{ij}=0\\ \frac{SJP_{ij}}{CJP_{ij}}&otherwise\end{cases} \forall\quad \begin{cases}i=1,2,3, \ldots,n\\ j=1,2,3,\ldots,n\end{cases} \]  
Figure 3: Gantt chart obtained by DP method. Step 9. Obtain each element of the from-to trajectory (\(FTT\)) matrix by the following equation:  
\[FTT_{ij}=\left\{ \begin{matrix}0&if\ CFT_{ij}=0\\ \frac{FT_{ij}}{FT_{ij}}&otherwise\end{matrix} \right.\forall\quad\left\{ \begin{matrix} i=0,1,2,\ldots,n\\ j=0,1,2,\ldots,n\end{matrix} \right.\]  
To demonstrate the three types of trajectory forms (job-position, job-job and from-to), we use an 8-job instance in Table 3 and generate 1000 solutions randomly, for example. Applying the above steps, the \(JPT\), \(JIT\) and \(FTT\) matrices are built, as shown in Tables 4-6.