# Unified Genetic Algorithm Approach for Solving Flexible Job-Shop Scheduling Problem
## 2 Research Background
### Candidate Order-Based Genetic Algorithm  
The COGA is a type of GA that is based on the candidate order approach (COA). The main idea of the COA is to generate a feasible sequence of given items by appending one item at a time. Moreover, which item to append is chosen from a set of candidates; an item is a candidate if it is not appended to the sequence under construction and no constraints are violated after its appending [34]. COA can be used to develop metaheuristic algorithms for solving the sequencing problem.  
The first example of a COA application is the COGA for solving the classical JSP ([PERSON], 2014). As a result of its flexibility, the COGA is quite effective for solving sequencing problems with additional constraints. [PERSON] [14] applied the COGA to solve the job sequencing problem and the traveling salesman problem with precedence constraints. [PERSON] and [PERSON] [35] developed COGA for solving a variant of shortest path problem. Another important benefit of COA is that it can be integrated with various metaheuristic algorithms. For instance, [PERSON] [34] developed a candidate order-based tabu search (COTS) for solving the job sequencing problem with precedence constraints. [PERSON] and [PERSON] [36] introduced the concept of the latest order constraint and applied COTS to solve the latest order constrained sequencing problem.  
Typically, metaheuristic algorithms for solving sequencing problems have complex structures. However, COA-based metaheuristic algorithms are easier to implement than conventional metaheuristic algorithms. In particular, the COGA provides a distinguishing genetic operator called COGO, which has two important features. First, the COGO enables the application of simple point-based crossover strategies to sequencing problems, including one-point, two-point, and uniform strategies. Thus, both crossover operations for the MS and OS parts in a GA chromosome for the FJSP can be performed using the COGO. Second, the COGO also can be used to mutate a GA chromosome for the sequencing problem. The COGO generates a feasible sequence of given items in a constructive manner, which means a sequence is obtained by iteratively appending one item at a time. The item to be appended is chosen from a set of candidates. The objective of crossover, which is to create offspring similar to the parents, can be achieved by choosing an item with an earlier reference position. Note that the reference position of an item is its order in the parent solution. In contrast, the COGO performs the mutation by choosing an item with a later reference position, since the objective of the mutation is to create offspring dissimilar to the parents [14].  
The main contributions of this paper are as follows. Firstly, we can implement the GA for solving the FJSP with only two genetic operators: the COGO and an additional operator for the mutation of the MS part. In other words, the u-COGA is easier to implement than previous GAs for the FJSP. Secondly, various kinds of crossover strategies, such as one-point, two-point, and uniform strategies, can be applied to the u-COGA. Thirdly, numerical experiments reveal that uniform crossover is the best crossover strategy for the u-COGA for the FJSP.