## 4 Genetic Algorithm
### Genetic Operators
#### 4.5.4 Tournament Selection
``` Input :\(Z(i,t)\) for \(i=1,2,...,N\) Output :\(Winner\)
1 for\(j=1\)to\(T\)do
2\(Competitor[j]=\) RandIntBetween(1, N) /* Select \(T\) competitors randomly */
3 end for
6\(Winner=Competitor[1]\)
12\(Competitor[j]=\) RandIntBetween(1, N) /* Select \(T\) competitors randomly */
7 end for
8\(Winner=Competitor[1]\)
9\(Winner=Competitor[1]\)
13 end for
14\(Winner=Competitor[1]\)
15\(Winner=Competitor[1]\)
16\(Winner=Competitor[1]\)
17\(Winner=Competitor[1]\)
18\(Winner=Competitor[1]\)
19\(Winner=Competitor[1]\)

#### 4.5.5 Crossover Operators

Crossover operators are responsible for creating offspring from parent chromosomes via the exchange of genetic materials, thereby, mimicking sexual reproduction in living organisms. Once \(M(t)\) is formed using the selection operator, each individual is paired randomly to create a total of \(N/2\) pairs. Then, a crossover operator is applied on each pair resulting from the creation of offspring. The crossover operators used in this paper are listed below. SSC1, SSC2, JLOSC, SLOSC, and MAC are direct adaptations from [2]. However, in this paper, JLOSC, SLOSC, and MAC are applicable only in the second stage of the search. JLSCS and SLGSC share similarities with JLOSC and SLOSC; however, they are applicable only in the first stage of the genetic search. 1. [label=()]
2. Sublot-Size Crossover-1 (SSC1). 3. Sublot-Size Crossover-2 (SSC2). 4. Job Level Gene Sequence Crossover (JLGSC). 5. Sublot Level Gene Sequence Crossover (SLGSC). 6. Job Level Operation Sequence Crossover (JLOSC). 7. Sublot Level Operation Sequence Crossover (SLOSC). 8. Machine Assignment Crossover (MAC). Figure 5 depicts the first two crossover operators (SSC1 and SSC2). When SSC1 (or SSC2) is applied, an arbitrary crossover point is selected on Segment-1, and the parts of this segment that lie to the left (or right) of the crossover point are exchanged. The step-by-step application of JLGSC is illustrated in Figure 6 where the creation of Child-1 is detailed. In Step-1, one gene is selected arbitrarily. This gene and all the other genes with the same job index, \(j\), are copied from Parent-1 to Child-1. In Step-3, all the missing genes of Child-1 are copied from parent-2 in the order they appeared in this second parent. At the same time, Child-2 is also created by first copying genes from Parent-2 with the same job index as the arbitrarily selected gene. The missing genes of Child-2 will be obtained from Parent-1. SLGSC is applied in a similar manner to JLGSC. However, the gene transfer in SLGSC is limited to the genes that have the same job and sublot index (\(j,\ s\)) as the arbitrarily selected gene in Step-1. JLOSC is applied in four steps as shown in Figure 7. In Step-1, a crossover point (a gene) is selected arbitrarily. All the genes with the same job index as the arbitrarily selected gene are copied from Parent-1 to Child-1 in Step-2. In Step-3, the first three elements \((j,s,o)\) of the missing genes of Child-1 are copied from Parent-2. In the last step, the machine assignments of the incomplete genes that were copied from Parent-2 are completed by the machine assignment obtained from Parent-1. The creation of Child-2 will be performed in a similar manner by starting from Parent-2. SLOSC is a reduced version of JLOSC where the first step is limited to the genes with the same job and sublot indices. Hence, if Figure 7 were for SLOSC, only the genes with job index \(j=3\) and sublot index \(s=2\) would be copied to Child-1 in Step-2. When either JLOSC or SLOSC is applied, Child-1 (Child-2) will have the same machine assigned as Parent-1 (Parent-2) but with a different operation sequence. Thus, JLOSC and SLOSC manipulate only the sequence of operations without altering the machine assignments in Stage-2 of the generic search. The machine assignment crossover (MAC), shown in Figure 8, is responsible for exchanging machine assignment information between parent chromosomes during Stage-2 of the genetic search. As can be seen in the figure, this operator is applied in three steps to create offspring.