# Unified Genetic Algorithm Approach for Solving Flexible Job-Shop Scheduling Problem
## 3 Unified Candidate Order-Based Genetic Algorithm
### Crossover of Unified COGA  
This section outlines crossover procedure of the u-COGA. The COGO enables the application of simple crossover strategies to sequencing problems, such as one-point, two-point, and uniform crossovers. Thus, a solution of the FJSP is converted into a sequence of operations in order to apply the COGO, as shown in Figure 3. Note that an operation in the FJSP has an additional attribute, \(MS\left(o_{ij}\right)\), as shown in panel (b) in Figure 3.  
The COGO generates a solution in a constructive manner, which means that one operation is appended to a new solution at a time. An operation to be appended to a specific position is chosen with consideration of the reference solution, one of the parent solutions. Thus, the COGO determines the reference solution for each position in a sequence before generating a new solution. An important feature of the COGO is that simple crossover strategies can be used to determine reference solutions. In panel (b) in Figure 3, each sequence is divided into two parts, i.e., the earlier part with the first two operations and later part with the other four operations, by adopting the conventional one-point crossover  
Figure 3: Reference set assignment for parent solutions in the form of a sequence. strategy. We can see that \(P_{1}\) (\(P_{2}\)) and \(P_{2}\) (\(P_{2}\)) are used as reference solutions for the earlier part and later part of \(C_{1}\) (\(C_{2}\)), respectively. An operation to be used as the \(p\)th position of a new solution is determined after the \(p-1\)th operation is appended. An operation to be the \(p\)th operation is chosen from a set of candidates; an operation is a candidate if and only if it has not been appended to the new solution under construction and no constraints are violated by appending the operation to the \(p\)th position. The main idea of the COGO is that the objectives of crossover and mutation can be achieved by choosing the appropriate operation from the set of candidates. Figure 4 illustrates a procedure for generating the earlier part of \(C_{1}\), an offspring of \(P_{1}\) and \(P_{2}\) in Figure 3. Let \(RP(o_{ij},~{}X)\) denote the reference position of an operation \(o_{ij}\) in a solution \(X\). In other words, \(o_{ij}\) is the \(RP(o_{ij},~{}X)\)th operation in \(X\). The main idea of the COGO is that the objectives of crossover and mutation can be achieved by choosing candidates with the smallest and the largest reference position values, respectively. For the first position in \(C_{1}\), all operations are candidates, since no operation is appended to \(C_{1}\), yet. Among the candidates, an operation with the smallest reference position regarding \(P_{1}\), \(o_{31}\) is chosen as the first operation. Similarly, \(o_{11}\) is appended to the second position in \(C_{1}\). Note that \(MS(o_{ij})\)s of the offspring are inherited from the associated reference solution. That is, \(MS(o_{31})\) and \(MS(o_{11})\) of \(C_{1}\) are the same as those of \(P_{1}\). Figure 5 shows the crossover procedure for the later part of \(C_{1}\), where \(P_{2}\) is used as the reference solution. We can see that the positions of \(o_{12}\), \(o_{21}\), \(o_{22}\), and \(o_{32}\) in the later part of \(C_{1}\) are different from those of \(P_{2}\). Nevertheless, the precedence relationships among them in \(P_{2}\) are also maintained in \(C_{1}\). Moreover, \(MS(o_{ij})\)s of the operations in the later part are inherited from \(P_{2}\). Consequently, \(C_{1}\) inherits from both \(P_{1}\) and \(P_{2}\). Since the \(MS(o_{ij})\) value of the reference solution is maintained in the offspring solution, the crossover procedure described in Figures 3-5 helps to preserve a combination of the OS and MS genes. In contrast, the mutation operation for the \(p\)th position of a new solution is performed by choosing a candidate with the largest reference position in the COGO procedure. That is, crossover and mutation are integrated in the COGO.